00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
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
00080
00081
00082 class Boundable {
00083 public:
00097 virtual const void* getBounds()=0;
00098 virtual ~Boundable() {};
00099 };
00100
00101
00102
00103
00104
00105
00106
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
00122
00123
00124
00125
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
00142
00143
00144
00145
00146
00147
00148
00149
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
00183
00184
00185
00186
00187
00188
00189
00190
00191
00192
00193
00194
00195
00196 class AbstractSTRtree {
00197 protected:
00198
00199
00200
00201
00202
00203
00204
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
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
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
00260
00261
00262
00263
00264
00265
00266
00267
00268
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
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
00299
00300
00301
00302
00303
00304
00305
00306
00307
00308
00309
00310
00311
00312
00313
00314 class STRtree: public AbstractSTRtree,public SpatialIndex {
00315 private:
00316
00317
00318
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
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