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

Generated on Sun Aug 5 23:04:38 2007 for GEOS by  doxygen 1.3.9.1