00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
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
00031
00032
00033 class Boundable {
00034 public:
00048 virtual const void* getBounds()=0;
00049 virtual ~Boundable() {};
00050 };
00051
00052
00053
00054
00055
00056
00057
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
00073
00074
00075
00076
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
00093
00094
00095
00096
00097
00098
00099
00100
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
00134
00135
00136
00137
00138
00139
00140
00141
00142
00143
00144
00145
00146
00147 class AbstractSTRtree {
00148 protected:
00149
00150
00151
00152
00153
00154
00155
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
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
00213
00214
00215
00216
00217
00218
00219
00220
00221
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
00257
00258
00259
00260
00261
00262
00263
00264
00265
00266
00267
00268
00269
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 }
00306
00307 #endif
00308
00309
00310
00311
00312
00313
00314
00315
00316
00317
00318
00319
00320
00321
00322
00323
00324
00325
00326
00327
00328
00329
00330
00331
00332
00333
00334
00335
00336
00337
00338
00339
00340
00341
00342
00343
00344
00345
00346
00347
00348
00349
00350
00351
00352
00353
00354
00355
00356
00357
00358
00359
00360
00361
00362
00363
00364
00365
00366
00367