GEOS 3.9.1
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
37namespace geos {
38namespace index {
39namespace strtree {
40class Boundable;
41}
42}
43}
44
45namespace geos {
46namespace index { // geos::index
47namespace strtree { // geos::index::strtree
48
64class GEOS_DLL STRtree: public AbstractSTRtree, public SpatialIndex {
65 using AbstractSTRtree::insert;
66 using AbstractSTRtree::query;
67
68private:
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> sortBoundablesY(const BoundableList* input);
89 std::unique_ptr<BoundableList> sortBoundablesX(const BoundableList* input);
90
91 std::unique_ptr<BoundableList> createParentBoundablesFromVerticalSlice(
92 BoundableList* childBoundables,
93 int newLevel);
94
100 std::vector<BoundableList*>* verticalSlices(
101 BoundableList* childBoundables,
102 size_t sliceCount);
103
104 bool isWithinDistance(BoundablePair* initBndPair, double maxDistance);
105
106protected:
107
108 AbstractNode* createNode(int level) override;
109
112 {
113 return &intersectsOp;
114 }
115
116public:
117
118 ~STRtree() override = default;
119
124 STRtree(std::size_t nodeCapacity = 10);
125
126 void insert(const geom::Envelope* itemEnv, void* item) override;
127
128 //static double centreX(const geom::Envelope *e);
129
130 static double
131 avg(double a, double b)
132 {
133 return (a + b) / 2.0;
134 }
135
136 static double
137 centreY(const geom::Envelope* e)
138 {
139 return STRtree::avg(e->getMinY(), e->getMaxY());
140 }
141
142 void
143 query(const geom::Envelope* searchEnv, std::vector<void*>& matches) override
144 {
145 AbstractSTRtree::query(searchEnv, matches);
146 }
147
148 void
149 query(const geom::Envelope* searchEnv, ItemVisitor& visitor) override
150 {
151 return AbstractSTRtree::query(searchEnv, visitor);
152 }
153
154 std::pair<const void*, const void*> nearestNeighbour(ItemDistance* itemDist);
155 const void* nearestNeighbour(const geom::Envelope* env, const void* item, ItemDistance* itemDist);
156 std::pair<const void*, const void*> nearestNeighbour(STRtree* tree, ItemDistance* itemDist);
157 std::pair<const void*, const void*> nearestNeighbour(BoundablePair* initBndPair);
158 std::pair<const void*, const void*> nearestNeighbour(BoundablePair* initBndPair, double maxDistance);
159
160 bool
161 remove(const geom::Envelope* itemEnv, void* item) override
162 {
163 return AbstractSTRtree::remove(itemEnv, item);
164 }
165
166 bool isWithinDistance(STRtree* tree, ItemDistance* itemDist, double maxDistance);
167
168};
169
170} // namespace geos::index::strtree
171} // namespace geos::index
172} // namespace geos
173
174
175#ifdef _MSC_VER
176#pragma warning(pop)
177#endif
178
179#endif // GEOS_INDEX_STRTREE_STRTREE_H
An Envelope defines a rectangulare region of the 2D coordinate plane.
Definition Envelope.h:58
double getMaxY() const
Returns the Envelope maximum y-value. min y > max y indicates that this is a null Envelope.
double getMinY() const
Returns the Envelope minimum y-value. min y > max y indicates that this is a null Envelope.
A visitor for items in an index.
Definition ItemVisitor.h:29
Abstract class defines basic insertion and query operations supported by classes implementing spatial...
Definition SpatialIndex.h:47
A node of the STR tree.
Definition AbstractNode.h:44
A test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have diff...
Definition AbstractSTRtree.h:176
Base class for STRtree and SIRtree.
Definition AbstractSTRtree.h:139
A pair of Boundables, whose leaf items support a distance metric between them.
Definition BoundablePair.h:44
A function method which computes the distance between two ItemBoundables in an STRtree....
Definition ItemDistance.h:34
A query-only R-tree created using the Sort-Tile-Recursive (STR) algorithm. For two-dimensional spatia...
Definition STRtree.h:64
STRtree(std::size_t nodeCapacity=10)
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:149
IntersectsOp * getIntersectsOp() override
Definition STRtree.h:111
void insert(const geom::Envelope *itemEnv, void *item) override
Adds a spatial item with an extent specified by the given Envelope to the index.
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:143
bool remove(const geom::Envelope *itemEnv, void *item) override
Removes a single item from the tree.
Definition STRtree.h:161
std::vector< Boundable * > BoundableList
A list of boundables. TODO: use a list.
Definition AbstractSTRtree.h:44
Basic namespace for all GEOS functionalities.
Definition IndexedNestedRingTester.h:26