GEOS  3.8.0dev
STRtree.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/strtree/STRtree.java rev. 1.11
16  *
17  **********************************************************************/
18 
19 #ifndef GEOS_INDEX_STRTREE_STRTREE_H
20 #define GEOS_INDEX_STRTREE_STRTREE_H
21 
22 #include <geos/export.h>
23 #include <geos/index/strtree/ItemDistance.h>
24 #include <geos/index/strtree/BoundablePair.h>
25 #include <geos/index/strtree/AbstractSTRtree.h> // for inheritance
26 #include <geos/index/SpatialIndex.h> // for inheritance
27 #include <geos/geom/Envelope.h> // for inlines
28 
29 #include <vector>
30 
31 #ifdef _MSC_VER
32 #pragma warning(push)
33 #pragma warning(disable: 4251) // warning C4251: needs to have dll-interface to be used by clients of class
34 #endif
35 
36 // Forward declarations
37 namespace geos {
38 namespace index {
39 namespace strtree {
40 class Boundable;
41 }
42 }
43 }
44 
45 namespace geos {
46 namespace index { // geos::index
47 namespace strtree { // geos::index::strtree
48 
64 class GEOS_DLL STRtree: public AbstractSTRtree, public SpatialIndex {
67 
68 private:
69  class GEOS_DLL STRIntersectsOp: public AbstractSTRtree::IntersectsOp {
70  public:
71  bool intersects(const void* aBounds, const void* bBounds) override;
72  };
73 
81  std::unique_ptr<BoundableList> createParentBoundables(BoundableList* childBoundables, int newLevel) override;
82 
83  std::unique_ptr<BoundableList> createParentBoundablesFromVerticalSlices(std::vector<BoundableList*>* verticalSlices,
84  int newLevel);
85 
86  STRIntersectsOp intersectsOp;
87 
88  std::unique_ptr<BoundableList> sortBoundables(const BoundableList* input) override;
89 
90  std::unique_ptr<BoundableList> createParentBoundablesFromVerticalSlice(
91  BoundableList* childBoundables,
92  int newLevel);
93 
99  std::vector<BoundableList*>* verticalSlices(
100  BoundableList* childBoundables,
101  size_t sliceCount);
102 
103  bool isWithinDistance(BoundablePair* initBndPair, double maxDistance);
104 
105 protected:
106 
107  AbstractNode* createNode(int level) override;
108 
109  IntersectsOp*
110  getIntersectsOp() override
111  {
112  return &intersectsOp;
113  }
114 
115 public:
116 
117  ~STRtree() override;
118 
123  STRtree(std::size_t nodeCapacity = 10);
124 
125  void insert(const geom::Envelope* itemEnv, void* item) override;
126 
127  //static double centreX(const geom::Envelope *e);
128 
129  static double
130  avg(double a, double b)
131  {
132  return (a + b) / 2.0;
133  }
134 
135  static double
136  centreY(const geom::Envelope* e)
137  {
138  return STRtree::avg(e->getMinY(), e->getMaxY());
139  }
140 
141  void
142  query(const geom::Envelope* searchEnv, std::vector<void*>& matches) override
143  {
144  AbstractSTRtree::query(searchEnv, matches);
145  }
146 
147  void
148  query(const geom::Envelope* searchEnv, ItemVisitor& visitor) override
149  {
150  return AbstractSTRtree::query(searchEnv, visitor);
151  }
152 
153  std::pair<const void*, const void*> nearestNeighbour(ItemDistance* itemDist);
154  const void* nearestNeighbour(const geom::Envelope* env, const void* item, ItemDistance* itemDist);
155  std::pair<const void*, const void*> nearestNeighbour(STRtree* tree, ItemDistance* itemDist);
156  std::pair<const void*, const void*> nearestNeighbour(BoundablePair* initBndPair);
157  std::pair<const void*, const void*> nearestNeighbour(BoundablePair* initBndPair, double maxDistance);
158 
159  bool
160  remove(const geom::Envelope* itemEnv, void* item) override
161  {
162  return AbstractSTRtree::remove(itemEnv, item);
163  }
164 
165  bool isWithinDistance(STRtree* tree, ItemDistance* itemDist, double maxDistance);
166 
167 };
168 
169 } // namespace geos::index::strtree
170 } // namespace geos::index
171 } // namespace geos
172 
173 
174 #ifdef _MSC_VER
175 #pragma warning(pop)
176 #endif
177 
178 #endif // GEOS_INDEX_STRTREE_STRTREE_H
An Envelope defines a rectangulare region of the 2D coordinate plane.
Definition: Envelope.h:58
Base class for STRtree and SIRtree.
Definition: AbstractSTRtree.h:140
void query(const void *searchBounds, std::vector< void * > &foundItems)
Also builds the tree, if necessary.
void query(const geom::Envelope *searchEnv, std::vector< void * > &matches) override
Queries the index for all items whose extents intersect the given search Envelope.
Definition: STRtree.h:142
void query(const geom::Envelope *searchEnv, ItemVisitor &visitor) override
Queries the index for all items whose extents intersect the given search Envelope and applies an Item...
Definition: STRtree.h:148
double getMinY() const
Returns the Envelope minimum y-value. min y > max y indicates that this is a null Envelope...
A query-only R-tree created using the Sort-Tile-Recursive (STR) algorithm. For two-dimensional spatia...
Definition: STRtree.h:64
Abstract class defines basic insertion and query operations supported by classes implementing spatial...
Definition: SpatialIndex.h:47
A function method which computes the distance between two ItemBoundables in an STRtree. Used for Nearest Neighbour searches.
Definition: ItemDistance.h:34
A test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have diff...
Definition: AbstractSTRtree.h:174
A visitor for items in an index.
Definition: ItemVisitor.h:29
virtual void insert(const void *bounds, void *item)
Also builds the tree, if necessary.
double getMaxY() const
Returns the Envelope maximum y-value. min y > max y indicates that this is a null Envelope...
Basic namespace for all GEOS functionalities.
Definition: IndexedNestedRingTester.h:25
A node of the STR tree.
Definition: AbstractNode.h:43
std::vector< Boundable * > BoundableList
A list of boundables. TODO: use a list.
Definition: AbstractSTRtree.h:44
IntersectsOp * getIntersectsOp() override
Definition: STRtree.h:110
A pair of Boundables, whose leaf items support a distance metric between them.
Definition: BoundablePair.h:44