GEOS 3.9.1
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/geom/Envelope.h>
24#include <geos/index/SpatialIndex.h> // for inheritance
25#include <geos/index/quadtree/Root.h> // for composition
26
27#include <memory>
28#include <vector>
29#include <string>
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 quadtree {
40// class Root;
41}
42}
43}
44
45namespace geos {
46namespace index { // geos::index
47namespace quadtree { // geos::index::quadtree
48
71class GEOS_DLL Quadtree: public SpatialIndex {
72
73private:
74
75 std::vector<std::unique_ptr<geom::Envelope>> newEnvelopes;
76
77 void collectStats(const geom::Envelope& itemEnv);
78
79 Root root;
80
92 double minExtent;
93
94public:
103 double minExtent);
104
110 :
111 root(),
112 minExtent(1.0)
113 {}
114
115 ~Quadtree() override = default;
116
118 int depth();
119
121 size_t size();
122
123 void insert(const geom::Envelope* itemEnv, void* item) override;
124
142 void query(const geom::Envelope* searchEnv, std::vector<void*>& ret) override;
143
144
161 void
162 query(const geom::Envelope* searchEnv, ItemVisitor& visitor) override
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) override;
179
181 std::vector<void*>* queryAll();
182
183 std::string toString() const;
184
189 Quadtree(const Quadtree&) = delete;
190 Quadtree& operator=(const Quadtree&) = delete;
191
192};
193
194} // namespace geos::index::quadtree
195} // namespace geos::index
196} // namespace geos
197
198#ifdef _MSC_VER
199#pragma warning(pop)
200#endif
201
202#endif // GEOS_IDX_QUADTREE_QUADTREE_H
An Envelope defines a rectangulare region of the 2D coordinate plane.
Definition: Envelope.h:58
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 Quadtree is a spatial index structure for efficient querying of 2D rectangles. If other kinds of sp...
Definition: Quadtree.h:71
Quadtree(const Quadtree &)=delete
bool remove(const geom::Envelope *itemEnv, void *item) override
void query(const geom::Envelope *searchEnv, ItemVisitor &visitor) override
Queries the tree and visits items which may lie in the given search envelope.
Definition: Quadtree.h:162
int depth()
Returns the number of levels in the tree.
static geom::Envelope * ensureExtent(const geom::Envelope *itemEnv, double minExtent)
Ensure that the envelope for the inserted item has non-zero extents.
size_t size()
Returns the number of items in the tree.
void insert(const geom::Envelope *itemEnv, void *item) override
Adds a spatial item with an extent specified by the given Envelope to the index.
Quadtree()
Constructs a Quadtree with zero items.
Definition: Quadtree.h:109
void query(const geom::Envelope *searchEnv, std::vector< void * > &ret) override
Queries the tree and returns items which may lie in the given search envelope.
std::vector< void * > * queryAll()
Return a list of all items in the Quadtree.
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
Basic namespace for all GEOS functionalities.
Definition: IndexedNestedRingTester.h:26