// -------------------------------------------------------------------- // Compressed Guarding Quadtree: // Ipelet for creating a compressed quadtree of guarding points // Shripad Thite (sthite@win.tue.nl) 25-Feb-2007 // -------------------------------------------------------------------- /* -------------------------------------------------------------------- Compressed Guarding Quadtree: Ipelet for creating a compressed quadtree of guarding points Copyright (C) 2007 Shripad Thite This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. Modification history: Created 25-Feb-2007 by Shripad Thite -------------------------------------------------------------------- */ /* -------------------------------------------------------------------- Ipe is an extensible drawing editor by Otfried Cheong, available for download from http://ipe.compgeom.org/ See the Ipe manual at the above page for information on how to compile and use ipelets. -------------------------------------------------------------------- */ /* -------------------------------------------------------------------- HOW TO USE THIS IPELET: In a document being edited in Ipe, select one or more objects. Then select this ipelet from the Ipelets menu. A set of guarding points together with a set of canonical boxes representing the nodes of the compressed guarding quadtree will be created in a new layer of the current page. To see the quadtree on top of the selected objects, you may have to select the new layer to be visible in your current view. -------------------------------------------------------------------- */ /* -------------------------------------------------------------------- DEFINITIONS: A "box" is the interior of an axis-aligned square together with its boundary. A "bounding box" of an object K is the smallest box containing K. The "guarding points", or "guards", of an object K are the four vertices of the bounding box of K. The "guards" of a set S of objects is the union of guards of the objects in S. A "canonical box" is a box whose sides have x- and y-coordinates that are integral powers of two. A "quadtree" is a hierarchical decomposition of the plane (or a bounded subset of the plane) obtained by recursively decomposing, or splitting, a canonical box into four by bisecting each dimension of the original box. A "canonical bounding box" of a set of objects is the smallest canonical box containing all objects in the set. A "quadtree" of set of objects is a quadtree of the canonical bounding box of the set. A "compressed quadtree" is a quadtree obtained by eliminating redundant splits in the quadtree construction, i.e., a split which results in all the objects belonging to only one subtree. A "compressed guarding quadtree" of a set S of objects is the compressed quadtree of the guards of S. The following paper (manuscript available at the following URL) describes an algorithm to construct the compressed guarding quadtree of the edges of a polygonal subdivision in the plane (a map), and its use for point location and map overlay, two important problems in Computational Geometry with applications in Geographic Information Systems (GIS): "I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions" Mark de Berg, Herman Haverkort, Shripad Thite, Laura Toma http://www.win.tue.nl/~sthite/pubs/ -------------------------------------------------------------------- */ #include #include #include "ipelet.h" #include "ipepath.h" #include "ipepage.h" #include "ipevisitor.h" #include "ipemark.h" using namespace std; const char * LabelString = "Compressed guarding quadtree"; const char * AboutString = "Quadtree Ipelet by Shripad Thite (sthite@win.tue.nl), 25-Feb-2007"; // ==================================================================== // ==================================================================== static const int m_numBits = 8*sizeof(int); void makeBitString( char * dest, int x, const int numBits ) { for( int i = numBits; i > 0; ) { i--; dest[i] = ( x % 2 == 0 ? '0' : '1' ); x >>= 1; } return; } int makeInteger( const char * src, const int numBits ) { int z = 0; for( int i = 0; i < numBits; i++ ) { z <<= 1; z += ( src[i] == '0' ? 0 : 1 ); } return z; } // ==================================================================== // ==================================================================== class MyPoint { private: int m_x; int m_y; char m_xstr[ m_numBits ]; char m_ystr[ m_numBits ]; char m_zstr[ 2*m_numBits ]; int m_z; void makeZindex( void ) { makeBitString( m_xstr, m_x, m_numBits ); makeBitString( m_ystr, m_y, m_numBits ); int j = 0; for( int i = 0; i < m_numBits; i++ ) { m_zstr[j++] = m_xstr[i]; m_zstr[j++] = m_ystr[i]; } m_z = makeInteger( m_zstr, 2*m_numBits ); return; } public: MyPoint( int x, int y ) { m_x = x; m_y = y; makeZindex(); return; } const int getX( void ) const { return m_x; } const int getY( void ) const { return m_y; } const int getZ( void ) const { return m_z; } const char * getXString( void ) const { return m_xstr; } const char * getYString( void ) const { return m_ystr; } }; // -------------------------------------------------------------------- /* Compare two points in Z-order, i.e., the order in which the Z- space-filling curve visits them. */ bool operator < ( const MyPoint & p, const MyPoint & q ) { return p.getZ() < q.getZ(); } // -------------------------------------------------------------------- void computeLCA( const MyPoint & p, const MyPoint & q, int & left, int & right, int & top, int & bottom, int numBits ) { const char * pxstr = p.getXString(); const char * pystr = p.getYString(); const char * qxstr = q.getXString(); const char * qystr = q.getYString(); char xprefix[ numBits ]; char yprefix[ numBits ]; int prefixLen = 0; bool inPrefix = true; for( int i = 0; i < numBits; i++ ) { if( inPrefix && (pxstr[i] == qxstr[i]) && (pystr[i] == qystr[i]) ) { xprefix[i] = pxstr[i]; yprefix[i] = pystr[i]; prefixLen++; } else { inPrefix = false; xprefix[i] = '0'; yprefix[i] = '0'; } } const int size = (1 << (numBits - prefixLen)); left = makeInteger( xprefix, numBits ); bottom = makeInteger( yprefix, numBits ); right = left + size; top = bottom + size; return; } // ==================================================================== // ==================================================================== class QuadtreeIpelet : public Ipelet { private: vector guardList; public: virtual int IpelibVersion() const { return IPELIB_VERSION; } virtual const char *Label() const { return LabelString; } virtual const char *About() const { return AboutString; } virtual void Run(int, IpePage *page, IpeletHelper *helper); }; // -------------------------------------------------------------------- void QuadtreeIpelet::Run(int, IpePage *page, IpeletHelper *helper) { for( IpePage::iterator iter = page->begin(); iter != page->end(); iter++ ) { if( iter->Select() && iter->Object() ) { // Retrieve the bounding box of every selected object IpeRect box = iter->BBox(); IpeVector topRight = box.Max(); IpeVector bottomLeft = box.Min(); IpeVector topLeft = box.TopLeft(); IpeVector bottomRight = box.BottomRight(); // Create bounding box vertices, i.e., "guards" guardList.push_back( MyPoint(int(topLeft.iX), int(topLeft.iY)) ); guardList.push_back( MyPoint(int(topRight.iX), int(topRight.iY)) ); guardList.push_back( MyPoint(int(bottomLeft.iX), int(bottomLeft.iY)) ); guardList.push_back( MyPoint(int(bottomRight.iX), int(bottomRight.iY)) ); } } if( guardList.size() < 2 ) { helper->Message("Please select at least one object"); return; } #if 1 // Make a new layer int layer = page->NewLayer(-1); #else // Draw on current layet int layer = helper->CurrentLayer(); #endif // Mark bounding box vertices for( vector::iterator iter = guardList.begin(); iter < guardList.end(); iter++ ) { const int x = iter->getX(); const int y = iter->getY(); page->push_back(IpePgObject(IpePgObject::EPrimary, layer, new IpeMark(helper->Attributes(), IpeVector(x,y)))); } // Sort the list of guarding points in order along the Z-curve sort(guardList.begin(), guardList.end()); //... // Create a local quadtree for each pair (p,q) of consecutive points // in sorted order. The local quadtree of (p,q) consists of five // canonical boxes: LCA(p,q) and its four children. Here, LCA(p,q) // denotes the lowest common ancestor of p and q, i.e., the canonical // bounding box of p and q. // Since this ipelet is intended for drawing only, we output only two // of the four children of LCA(p,q)---diagonally opposite cells whose // edges produce all the lines necessary for illustrating the local // quadtree. //... for( vector::iterator iter = guardList.begin(); iter < guardList.end() - 1; iter++ ) { MyPoint & p = *iter; MyPoint & q = *(iter+1); // Compute LCA(p,q) = canonical bounding box int left, right, top, bottom; computeLCA(p, q, left, right, top, bottom, m_numBits); IpeVector topLeft( left, top ); IpeVector bottomRight( right, bottom ); IpeVector middle( (left+right)>>1, (top+bottom)>>1 ); page->push_back(IpePgObject(IpePgObject::EPrimary, layer, new IpePath(helper->Attributes(), IpeRect(topLeft,bottomRight)))); page->push_back(IpePgObject(IpePgObject::EPrimary, layer, new IpePath(helper->Attributes(), IpeRect(topLeft,middle)))); page->push_back(IpePgObject(IpePgObject::EPrimary, layer, new IpePath(helper->Attributes(), IpeRect(middle,bottomRight)))); } // Report success helper->Message("Built compressed guarding quadtree in new layer"); return; } // ==================================================================== IPELET_DECLARE Ipelet * NewIpelet() { return new QuadtreeIpelet; } // ==================================================================== // ====================================================================