00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
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
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
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
00081
00082 int64 xBits;
00083 };
00084
00085
00086
00087
00088
00089
00090
00091
00092
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
00106 Coordinate *pt;
00107 int level;
00108
00109 Envelope *env;
00110 void computeKey(int level,Envelope *itemEnv);
00111 };
00112
00113 class QuadTreeNode;
00114
00115
00116
00117
00118
00119
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
00152
00153
00154
00155
00156
00157
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
00184
00185
00186
00187
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
00204
00205
00206
00207
00208
00209
00210
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
00224
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 }
00281 #endif
00282
00283
00284
00285
00286
00287
00288
00289
00290
00291
00292
00293
00294
00295
00296
00297
00298
00299
00300
00301
00302
00303
00304
00305
00306
00307
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