GEOS  3.4.2
Quadtree.h
1 /**********************************************************************
2  *
3  * GEOS - Geometry Engine Open Source
4  * http://geos.osgeo.org
5  *
6  * Copyright (C) 2006 Refractions Research Inc.
7  *
8  * This is free software; you can redistribute and/or modify it under
9  * the terms of the GNU Lesser General Public Licence as published
10  * by the Free Software Foundation.
11  * See the COPYING file for more information.
12  *
13  **********************************************************************
14  *
15  * Last port: index/quadtree/Quadtree.java rev. 1.16 (JTS-1.10)
16  *
17  **********************************************************************/
18 
19 #ifndef GEOS_IDX_QUADTREE_QUADTREE_H
20 #define GEOS_IDX_QUADTREE_QUADTREE_H
21 
22 #include <geos/export.h>
23 #include <geos/index/SpatialIndex.h> // for inheritance
24 #include <geos/index/quadtree/Root.h> // for composition
25 
26 #include <vector>
27 #include <string>
28 
29 #ifdef _MSC_VER
30 #pragma warning(push)
31 #pragma warning(disable: 4251) // warning C4251: needs to have dll-interface to be used by clients of class
32 #endif
33 
34 // Forward declarations
35 namespace geos {
36  namespace geom {
37  class Envelope;
38  }
39  namespace index {
40  namespace quadtree {
41  // class Root;
42  }
43  }
44 }
45 
46 namespace geos {
47 namespace index { // geos::index
48 namespace quadtree { // geos::index::quadtree
49 
72 class GEOS_DLL Quadtree: public SpatialIndex {
73 
74 private:
75 
76  std::vector<geom::Envelope *> newEnvelopes;
77 
78  void collectStats(const geom::Envelope& itemEnv);
79 
80  Root root;
81 
93  double minExtent;
94 
95 public:
103  static geom::Envelope* ensureExtent(const geom::Envelope *itemEnv,
104  double minExtent);
105 
111  :
112  root(),
113  minExtent(1.0)
114  {}
115 
116  ~Quadtree();
117 
119  int depth();
120 
122  int size();
123 
124  void insert(const geom::Envelope *itemEnv, void *item);
125 
143  void query(const geom::Envelope *searchEnv, std::vector<void*>& ret);
144 
145 
162  void query(const geom::Envelope *searchEnv, ItemVisitor& visitor)
163  {
164  /*
165  * the items that are matched are the items in quads which
166  * overlap the search envelope
167  */
168  root.visit(searchEnv, visitor);
169  }
170 
178  bool remove(const geom::Envelope* itemEnv, void* item);
179 
181  std::vector<void*>* queryAll();
182 
183  std::string toString() const;
184 
185 };
186 
187 } // namespace geos::index::quadtree
188 } // namespace geos::index
189 } // namespace geos
190 
191 #ifdef _MSC_VER
192 #pragma warning(pop)
193 #endif
194 
195 #endif // GEOS_IDX_QUADTREE_QUADTREE_H
An Envelope defines a rectangulare region of the 2D coordinate plane.
Definition: Envelope.h:53
A Quadtree is a spatial index structure for efficient querying of 2D rectangles. If other kinds of sp...
Definition: Quadtree.h:72
QuadRoot is the root of a single Quadtree. It is centred at the origin, and does not have a defined e...
Definition: quadtree/Root.h:49
void query(const geom::Envelope *searchEnv, ItemVisitor &visitor)
Queries the tree and visits items which may lie in the given search envelope.
Definition: Quadtree.h:162
Abstract class defines basic insertion and query operations supported by classes implementing spatial...
Definition: SpatialIndex.h:47
A visitor for items in an index.
Definition: ItemVisitor.h:29
Quadtree()
Constructs a Quadtree with zero items.
Definition: Quadtree.h:110