Main Page | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | Related Pages

indexStrtree.h

00001 /**********************************************************************
00002  * $Id: indexStrtree.h,v 1.4 2004/07/27 16:35:46 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  * $Log: indexStrtree.h,v $
00016  * Revision 1.4  2004/07/27 16:35:46  strk
00017  * Geometry::getEnvelopeInternal() changed to return a const Envelope *.
00018  * This should reduce object copies as once computed the envelope of a
00019  * geometry remains the same.
00020  *
00021  * Revision 1.3  2004/07/19 13:19:31  strk
00022  * Documentation fixes
00023  *
00024  * Revision 1.2  2004/07/13 08:33:52  strk
00025  * Added missing virtual destructor to virtual classes.
00026  * Fixed implicit unsigned int -> int casts
00027  *
00028  * Revision 1.1  2004/07/02 13:20:42  strk
00029  * Header files moved under geos/ dir.
00030  *
00031  * Revision 1.14  2004/05/06 15:00:59  strk
00032  * Boundable destructor made virtual.
00033  * Added vector <AbstractNode *> *nodes member in AbstractSTRTree,
00034  * used to keep track of created node to cleanly delete them at
00035  * destruction time.
00036  *
00037  * Revision 1.13  2004/05/05 17:42:06  strk
00038  * AbstractNode destructor made virtual. AbstractNode::bounds made protected.
00039  * SIRAbstractNode and STRAbstractNode destructors added to get rid of
00040  * AbstractNode::bounds in the right way (is a void * casted to appropriate
00041  * Class in the subClasses).
00042  *
00043  * Revision 1.12  2004/05/03 16:29:21  strk
00044  * Added sortBoundables(const vector<Boundable *>) pure virtual in AbstractSTRtree,
00045  * implemented in SIRtree and STRtree. Comparator funx made static in STRtree.cpp
00046  * and SIRtree.cpp.
00047  *
00048  * Revision 1.11  2004/05/03 13:17:55  strk
00049  * Fixed comparator function to express StrictWeakOrdering.
00050  *
00051  * Revision 1.10  2004/04/05 06:35:14  ybychkov
00052  * "operation/distance" upgraded to JTS 1.4
00053  *
00054  * Revision 1.9  2004/03/25 02:23:55  ybychkov
00055  * All "index/*" packages upgraded to JTS 1.4
00056  *
00057  * Revision 1.8  2003/11/07 01:23:42  pramsey
00058  * Add standard CVS headers licence notices and copyrights to all cpp and h
00059  * files.
00060  *
00061  *
00062  **********************************************************************/
00063 
00064 
00065 #ifndef GEOS_INDEXSTRTREE_H
00066 #define GEOS_INDEXSTRTREE_H
00067 
00068 #include <memory>
00069 #include <vector>
00070 #include <geos/platform.h>
00071 #include <geos/spatialIndex.h>
00072 #include <geos/geom.h>
00073 
00074 using namespace std;
00075 
00076 namespace geos {
00077 
00078 /*
00079  * \class Boundable indexStrtree.h geos/indexStrtree.h
00080  * \brief  A spatial object in an AbstractSTRtree.
00081  */
00082 class Boundable {
00083 public:
00097         virtual const void* getBounds()=0;
00098         virtual ~Boundable() {};
00099 };
00100 
00101 /*
00102  * \class ItemBoundable indexStrtree.h geos/indexStrtree.h
00103  *
00104  * \brief
00105  * Boundable wrapper for a non-Boundable spatial object.
00106  * Used internally by AbstractSTRtree.
00107  *
00108  */
00109 class ItemBoundable: public Boundable {
00110 private:
00111         const void* bounds;
00112         void* item;
00113 public:
00114         ItemBoundable(const void* newBounds,void* newItem);
00115         virtual ~ItemBoundable();
00116         const void* getBounds();
00117         void* getItem();
00118 };
00119 
00120 /*
00121  * \class Interval indexStrtree.h geos/indexStrtree.h
00122  * \brief
00123  * A contiguous portion of 1D-space. Used internally by SIRtree.
00124  *
00125  * @see SIRtree
00126  */
00127 class Interval {
00128 public:
00129         Interval(Interval *other);
00130         Interval(double newMin,double newMax);
00131         double getCentre();
00132         Interval* expandToInclude(Interval *other);
00133         bool intersects(Interval *other);
00134         bool equals(void *o);
00135 private:
00136         double imin;
00137         double imax;
00138 };
00139 
00140 /*
00141  * \class AbstractNode indexStrtree.h geos/indexStrtree.h
00142  * \brief
00143  * A node of the STR tree.
00144  * 
00145  * The children of this node are either more nodes
00146  * (AbstractNodes) or real data (ItemBoundables).
00147  *
00148  * If this node contains real data (rather than nodes),
00149  * then we say that this node is a "leaf node".  
00150  *
00151  */
00152 class AbstractNode: public Boundable {
00153 private:
00154         vector<Boundable*> *childBoundables;
00155         int level;
00156 public:
00157         AbstractNode(int newLevel);
00158         virtual ~AbstractNode();
00159         vector<Boundable*>* getChildBoundables();
00160 
00173         const void* getBounds();
00174         int getLevel();
00175         void addChildBoundable(Boundable *childBoundable);
00176 protected:
00177         virtual void* computeBounds()=0;
00178         const void* bounds;
00179 };
00180 
00181 /*
00182  * \class AbstractSTRtree indexStrtree.h geos/indexStrtree.h
00183  *
00184  * \brief
00185  * Base class for STRtree and SIRtree.
00186  *
00187  * STR-packed R-trees are described in:
00188  * P. Rigaux, Michel Scholl and Agnes Voisard. Spatial Databases With
00189  * Application To GIS. Morgan Kaufmann, San Francisco, 2002.
00190  * 
00191  * This implementation is based on Boundables rather than just AbstractNodes, 
00192  * because the STR algorithm operates on both nodes and 
00193  * data, both of which are treated here as Boundables.
00194  * 
00195  */
00196 class AbstractSTRtree {
00197 protected:
00198         /*
00199          * \class IntersectsOp indexStrtree.h geos/indexStrtree.h
00200          *
00201          * \brief
00202          * A test for intersection between two bounds, necessary because
00203          * subclasses of AbstractSTRtree have different implementations of
00204          * bounds. 
00205          */
00206         class IntersectsOp {
00207                 public:
00215                         virtual bool intersects(const void* aBounds, const void* bBounds)=0;
00216         };
00217         AbstractNode *root;
00218         vector <AbstractNode *> *nodes;
00219         virtual AbstractNode* createNode(int level)=0;
00220         virtual vector<Boundable*>* createParentBoundables(vector<Boundable*> *childBoundables, int newLevel);
00221         virtual AbstractNode* lastNode(vector<Boundable*> *nodes);
00222         virtual AbstractNode* getRoot();
00223         virtual void insert(const void* bounds,void* item);
00224         virtual vector<void*>* query(const void* searchBounds);
00230 //      virtual IntersectsOp* getIntersectsOp()=0;
00231         virtual vector<Boundable*>* boundablesAtLevel(int level);
00232         int nodeCapacity;
00233 private:
00234         bool built;
00235         vector<Boundable*> *itemBoundables;
00236         virtual AbstractNode* createHigherLevels(vector<Boundable*> *boundablesOfALevel, int level);
00237         virtual vector<Boundable*> *sortBoundables(const vector<Boundable*> *input)=0;
00238 public:
00239         IntersectsOp *intersectsOp;
00240         AbstractSTRtree(int newNodeCapacity);
00241         static bool compareDoubles(double a, double b);
00242         virtual ~AbstractSTRtree();
00243         virtual void build();
00244 //      virtual void checkConsistency();
00245         virtual int getNodeCapacity();
00246         virtual void query(const void* searchBounds, AbstractNode* node, vector<void*>* matches);
00247         virtual void boundablesAtLevel(int level,AbstractNode* top,vector<Boundable*> *boundables);
00248 };
00249 
00250 class SIRAbstractNode: public AbstractNode{
00251 public:
00252         SIRAbstractNode(int level);
00253         ~SIRAbstractNode();
00254 protected:
00255         void* computeBounds();
00256 };
00257 
00258 /*
00259  * \class SIRtree indexStrtree.h geos/indexStrtree.h
00260  * \brief One-dimensional version of an STR-packed R-tree.
00261  *
00262  * SIR stands for "Sort-Interval-Recursive".
00263  *
00264  * STR-packed R-trees are described in:
00265  * P. Rigaux, Michel Scholl and Agnes Voisard. Spatial Databases With
00266  * Application To GIS. Morgan Kaufmann, San Francisco, 2002.
00267  *
00268  * @see STRtree
00269  */
00270 class SIRtree: public AbstractSTRtree {
00271 public:
00272         SIRtree();
00273         SIRtree(int nodeCapacity);
00274         virtual ~SIRtree();
00275         void insert(double x1,double x2,void* item);
00276         vector<void*>* query(double x);
00277         vector<void*>* query(double x1, double x2);
00278 protected:
00279         class SIRIntersectsOp:public AbstractSTRtree::IntersectsOp {
00280                 public:
00281                         bool intersects(const void* aBounds, const void* bBounds);
00282         };
00283         vector<Boundable*>* createParentBoundables(vector<Boundable*> *childBoundables,int newLevel);
00284         AbstractNode* createNode(int level);
00285 //      IntersectsOp* getIntersectsOp(){return NULL;};
00286         vector<Boundable*> *sortBoundables(const vector<Boundable*> *input);
00287 };
00288         
00289 class STRAbstractNode: public AbstractNode{
00290 public:
00291         STRAbstractNode(int level);
00292         ~STRAbstractNode();
00293 protected:
00294         void* computeBounds();
00295 };
00296 
00297 /*
00298  * \class STRtree indexStrtree.h geos/indexStrtree.h
00299  *
00300  * \brief
00301  * A query-only R-tree created using the Sort-Tile-Recursive (STR) algorithm. 
00302  * For two-dimensional spatial data. 
00303  *
00304  * The STR packed R-tree is simple to implement and maximizes space
00305  * utilization; that is, as many leaves as possible are filled to capacity.
00306  * Overlap between nodes is far less than in a basic R-tree. However, once the
00307  * tree has been built (explicitly or on the first call to #query), items may
00308  * not be added or removed. 
00309  * 
00310  * Described in: P. Rigaux, Michel Scholl and Agnes Voisard. Spatial
00311  * Databases With Application To GIS. Morgan Kaufmann, San Francisco, 2002. 
00312  *
00313  */
00314 class STRtree: public AbstractSTRtree,public SpatialIndex {
00315 private:
00316 //      Comparator* xComparator;
00317 //      Comparator* yComparator;
00318 //      IntersectsOp* intersectsOp;
00319 
00320         vector<Boundable*>* createParentBoundables(vector<Boundable*> *childBoundables, int newLevel);
00321         vector<Boundable*>* createParentBoundablesFromVerticalSlices(vector<vector<Boundable*>*>* verticalSlices, int newLevel);
00322 protected:
00323         vector<Boundable*> *sortBoundables(const vector<Boundable*> *input);
00324         vector<Boundable*>* createParentBoundablesFromVerticalSlice(vector<Boundable*> *childBoundables, int newLevel);
00325         vector<vector<Boundable*>*>* verticalSlices(vector<Boundable*> *childBoundables, int sliceCount);
00326         AbstractNode* createNode(int level);
00327 //      IntersectsOp* getIntersectsOp();
00328         class STRIntersectsOp:public AbstractSTRtree::IntersectsOp {
00329                 public:
00330                         bool intersects(const void* aBounds, const void* bBounds);
00331         };
00332 public:
00333         STRtree();
00334         ~STRtree();
00335         STRtree(int nodeCapacity);
00336         void insert(const Envelope *itemEnv,void* item);
00337         vector<void*>* query(const Envelope *searchEnv);
00338         static double centreX(Envelope *e);
00339         static double avg(double a, double b);
00340         static double centreY(Envelope *e);
00341 };
00342 }
00343 #endif
00344 

Generated on Fri Nov 26 21:30:45 2004 for GEOS by  doxygen 1.3.9.1