indexQuadtree.h

00001 /**********************************************************************
00002  * $Id: indexQuadtree.h,v 1.9 2004/11/17 08:13:16 strk Exp $
00003  *
00004  * GEOS - Geometry Engine Open Source
00005  * http://geos.refractions.net
00006  *
00007  * Copyright (C) 2001-2002 Vivid Solutions Inc.
00008  *
00009  * This is free software; you can redistribute and/or modify it under
00010  * the terms of the GNU Lesser General Public Licence as published
00011  * by the Free Software Foundation. 
00012  * See the COPYING file for more information.
00013  *
00014  **********************************************************************/
00015 
00016 #ifndef GEOS_INDEXQUADTREE_H
00017 #define GEOS_INDEXQUADTREE_H
00018 
00019 #include <memory>
00020 #include <vector>
00021 #include <geos/platform.h>
00022 #include <geos/geom.h>
00023 #include <geos/spatialIndex.h>
00024 
00025 #if __STDC_IEC_559__
00026 #define ASSUME_IEEE_DOUBLE 1
00027 #else
00028 #define ASSUME_IEEE_DOUBLE 0
00029 #endif
00030 
00031 
00032 using namespace std;
00033 
00034 namespace geos {
00035 
00036 /*
00037  * \class IntervalSize indexQuadtree.h geos/indexQuadtree.h
00038  *
00039  * \brief
00040  * Provides a test for whether an interval is
00041  * so small it should be considered as zero for the purposes of
00042  * inserting it into a binary tree.
00043  *
00044  * The reason this check is necessary is that round-off error can
00045  * cause the algorithm used to subdivide an interval to fail, by
00046  * computing a midpoint value which does not lie strictly between the
00047  * endpoints.
00048  */
00049 class IntervalSize {
00050 public:
00058         static const int MIN_BINARY_EXPONENT=-50;
00059         static bool isZeroWidth(double min, double max);
00060 };
00061 
00062 class DoubleBits {
00063 public:
00064         static const int EXPONENT_BIAS=1023;
00065         static double powerOf2(int exp);
00066         static int exponent(double d);
00067         static double truncateToPowerOfTwo(double d);
00068         static string toBinaryString(double d);
00069         static double maximumCommonMantissa(double d1, double d2);
00070         DoubleBits(double nx);
00071         double getDouble();
00072         int64 biasedExponent();
00073         int getExponent();
00074         void zeroLowerBits(int nBits);
00075         int getBit(int i);
00076         int numCommonMantissaBits(DoubleBits *db);
00077         string toString();
00078 private:
00079         double x;
00080 //      long long xBits;
00081 //      long xBits;
00082         int64 xBits;
00083 };
00084 
00085 /*
00086  * \class QuadTreeKey indexQuadtree.h geos/indexQuadtree.h
00087  *
00088  * \brief
00089  * A QuadTreeKey is a unique identifier for a node in a quadtree.
00090  *
00091  * It contains a lower-left point and a level number. The level number
00092  * is the power of two for the size of the node envelope
00093  */
00094 class QuadTreeKey {
00095 public:
00096         static int computeQuadLevel(Envelope *env);
00097         QuadTreeKey(Envelope *itemEnv);
00098         virtual ~QuadTreeKey();
00099         Coordinate* getPoint();
00100         int getLevel();
00101         Envelope* getEnvelope();
00102         Coordinate* getCentre();
00103         void computeKey(Envelope *itemEnv);
00104 private:        
00105         // the fields which make up the key
00106         Coordinate *pt;
00107         int level;
00108         // auxiliary data which is derived from the key for use in computation
00109         Envelope *env;
00110         void computeKey(int level,Envelope *itemEnv);
00111 };
00112 
00113 class QuadTreeNode;
00114 
00115 /*
00116  * \class QuadTreeNodeBase indexQuadtree.h geos/indexQuadtree.h
00117  *
00118  * \brief
00119  * The base class for nodes in a Quadtree.
00120  *
00121  */
00122 class QuadTreeNodeBase {
00123 public:
00124         static int getSubnodeIndex(const Envelope *env, const Coordinate *centre);
00125         QuadTreeNodeBase();
00126         virtual ~QuadTreeNodeBase();
00127         virtual vector<void*>* getItems();
00128         virtual void add(void* item);
00129         virtual vector<void*>* addAllItems(vector<void*> *resultItems);
00130         virtual void addAllItemsFromOverlapping(const Envelope *searchEnv,vector<void*> *resultItems);
00131         virtual int depth();
00132         virtual int size();
00133         virtual int nodeCount();
00134         virtual string toString() const;
00135 protected:
00136         vector<void*> *items;
00137 
00146         QuadTreeNode* subnode[4];
00147         virtual bool isSearchMatch(const Envelope *searchEnv)=0;
00148 };
00149 
00150 /*
00151  * \class QuadTreeNode indexQuadtree.h geos/indexQuadtree.h
00152  *
00153  * \brief
00154  * Represents a node of a Quadtree.
00155  *
00156  * Nodes contain items which have a spatial extent corresponding to
00157  * the node's position in the quadtree.
00158  *
00159  */
00160 class QuadTreeNode: public QuadTreeNodeBase {
00161 public:
00162         static QuadTreeNode* createNode(Envelope *env);
00163         static QuadTreeNode* createExpanded(QuadTreeNode *node, const Envelope *addEnv);
00164         QuadTreeNode(Envelope *nenv,int nlevel);
00165         virtual ~QuadTreeNode();
00166         Envelope* getEnvelope();
00167         QuadTreeNode* getNode(const Envelope *searchEnv);
00168         QuadTreeNodeBase* find(const Envelope *searchEnv);
00169         void insertNode(QuadTreeNode *node);
00170         string toString() const;
00171 private:
00172         Envelope *env;
00173         Coordinate *centre;
00174         int level;
00175         QuadTreeNode* getSubnode(int index);
00176         QuadTreeNode* createSubnode(int index);
00177 
00178 protected:
00179         bool isSearchMatch(const Envelope *searchEnv);
00180 };
00181 
00182 /*
00183  * \class QuadTreeRoot indexQuadtree.h geos/indexQuadtree.h
00184  *
00185  * \brief
00186  * QuadRoot is the root of a single Quadtree.  It is centred at the origin,
00187  * and does not have a defined extent.
00188  */
00189 class QuadTreeRoot: public QuadTreeNodeBase {
00190 friend class Unload;
00191 private:
00192         static Coordinate *origin;
00193         void insertContained(QuadTreeNode *tree, const Envelope *itemEnv, void* item);
00194 public:
00195         QuadTreeRoot();
00196         virtual ~QuadTreeRoot();
00197         void insert(const Envelope *itemEnv,void* item);
00198 protected:
00199         bool isSearchMatch(const Envelope *searchEnv);
00200 };
00201 
00202 /*
00203  * \class Quadtree indexQuadtree.h geos/indexQuadtree.h
00204  *
00205  * \brief
00206  * A Quadtree is a spatial index structure for efficient querying
00207  * of 2D rectangles.  If other kinds of spatial objects
00208  * need to be indexed they can be represented by their
00209  * envelopes
00210  * 
00211  * The quadtree structure is used to provide a primary filter
00212  * for range rectangle queries.  The query() method returns a list of
00213  * all objects which <i>may</i> intersect the query rectangle.  Note that
00214  * it may return objects which do not in fact intersect.
00215  * A secondary filter is required to test for exact intersection.
00216  * Of course, this secondary filter may consist of other tests besides
00217  * intersection, such as testing other kinds of spatial relationships.
00218  *
00219  * This implementation does not require specifying the extent of the inserted
00220  * items beforehand.  It will automatically expand to accomodate any extent
00221  * of dataset.
00222  * 
00223  * This data structure is also known as an <i>MX-CIF quadtree</i>
00224  * following the usage of Samet and others.
00225  */
00226 class Quadtree: public SpatialIndex {
00227 public:
00234         static Envelope* ensureExtent(const Envelope *itemEnv, double minExtent);
00239         Quadtree();
00240 
00241         virtual ~Quadtree();
00242 
00247         int depth();
00248 
00253         int size();
00254         
00255         void insert(const Envelope *itemEnv, void *item);
00256 
00257         vector<void*>* query(const Envelope *searchEnv);
00258         vector<void*>* queryAll();
00259 
00260         string toString() const;
00261 
00262 private:
00263         vector<Envelope *>newEnvelopes;
00264         void collectStats(const Envelope *itemEnv);
00265         QuadTreeRoot *root;
00277         double minExtent;
00278 };
00279 
00280 } // namespace geos
00281 #endif
00282 
00283 /**********************************************************************
00284  * $Log: indexQuadtree.h,v $
00285  * Revision 1.9  2004/11/17 08:13:16  strk
00286  * Indentation changes.
00287  * Some Z_COMPUTATION activated by default.
00288  *
00289  * Revision 1.8  2004/11/04 08:49:13  strk
00290  * Unlinked new documentation.
00291  *
00292  * Revision 1.7  2004/11/02 16:38:45  strk
00293  * Fixed ieee-754 detection switch
00294  *
00295  * Revision 1.6  2004/11/02 16:05:49  strk
00296  * Autodetect availability of IEEE-754 FP
00297  *
00298  * Revision 1.5  2004/11/02 15:49:59  strk
00299  *
00300  * Moved ASSUME_IEEE_DOUBLE define from DoubleBits.cpp to indexQuadtree.h.
00301  * Fixed a bug in powerOf2(). Made the !IEEE version less prone to
00302  * round-offs (still has approximation errors).
00303  *
00304  * Revision 1.4  2004/11/01 16:43:04  strk
00305  * Added Profiler code.
00306  * Temporarly patched a bug in DoubleBits (must check drawbacks).
00307  * Various cleanups and speedups.
00308  *
00309  * Revision 1.3  2004/07/27 16:35:46  strk
00310  * Geometry::getEnvelopeInternal() changed to return a const Envelope *.
00311  * This should reduce object copies as once computed the envelope of a
00312  * geometry remains the same.
00313  *
00314  * Revision 1.2  2004/07/19 13:19:31  strk
00315  * Documentation fixes
00316  *
00317  * Revision 1.1  2004/07/02 13:20:42  strk
00318  * Header files moved under geos/ dir.
00319  *
00320  * Revision 1.16  2004/05/06 16:30:58  strk
00321  * Kept track of newly allocated objects by ensureExtent for Bintree and Quadtree,
00322  * deleted at destruction time. doc/example.cpp runs with no leaks.
00323  *
00324  * Revision 1.15  2004/04/19 15:14:45  strk
00325  * Added missing virtual destructor in SpatialIndex class.
00326  * Memory leaks fixes. Const and throw specifications added.
00327  *
00328  * Revision 1.14  2004/03/25 02:23:55  ybychkov
00329  * All "index/" packages upgraded to JTS 1.4
00330  *
00331  * Revision 1.13  2003/11/07 01:23:42  pramsey
00332  * Add standard CVS headers licence notices and copyrights to all cpp and h
00333  * files.
00334  *
00335  *
00336  **********************************************************************/
00337 

Generated on Wed Jan 10 23:34:00 2007 for GEOS by  doxygen 1.4.6