GEOS  3.11.0
VertexSequencePackedRtree.h
1 /**********************************************************************
2  *
3  * GEOS - Geometry Engine Open Source
4  * http://geos.osgeo.org
5  *
6  * Copyright (C) 2020 Paul Ramsey <pramsey@cleverelephant.ca>
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 #pragma once
16 
17 // Forward declarations
18 namespace geos {
19 namespace geom {
20 class Coordinate;
21 class Envelope;
22 }
23 }
24 
27 
28 
29 namespace geos {
30 namespace index {
31 
32 
49 class GEOS_DLL VertexSequencePackedRtree {
50 
51 private:
52 
53 
58  static constexpr std::size_t NODE_CAPACITY = 16;
59 
60  // Members
61  const std::vector<Coordinate>& items;
62  std::vector<bool> removedItems;
63  std::vector<std::size_t> levelOffset;
64  std::size_t nodeCapacity = NODE_CAPACITY;
65  std::vector<Envelope> bounds;
66 
67 
68  // Methods
69 
70  void build();
71 
82  std::vector<std::size_t> computeLevelOffsets();
83 
84  static std::size_t ceilDivisor(std::size_t num, std::size_t denom);
85  static std::size_t clampMax(std::size_t x, std::size_t max);
86 
87  std::size_t levelNodeCount(std::size_t numNodes);
88 
89  std::vector<Envelope> createBounds();
90 
91  void fillItemBounds(std::vector<Envelope>& bounds);
92  void fillLevelBounds(std::size_t lvl, std::vector<Envelope>& bounds);
93 
94  static Envelope computeNodeEnvelope(const std::vector<Envelope>& bounds,
95  std::size_t start, std::size_t end);
96  static Envelope computeItemEnvelope(const std::vector<Coordinate>& items,
97  std::size_t start, std::size_t end);
98 
99  void queryNode(const Envelope& queryEnv,
100  std::size_t level, std::size_t nodeIndex,
101  std::vector<std::size_t>& result) const;
102  void queryNodeRange(const Envelope& queryEnv,
103  std::size_t level, std::size_t nodeStartIndex,
104  std::vector<std::size_t>& result) const;
105  void queryItemRange(const Envelope& queryEnv, std::size_t itemIndex,
106  std::vector<std::size_t>& result) const;
107 
108  std::size_t levelSize(std::size_t level) const;
109  bool isNodeEmpty(std::size_t level, std::size_t index);
110  bool isItemsNodeEmpty(std::size_t nodeIndex);
111 
112 
113 public:
114 
121  VertexSequencePackedRtree(const std::vector<Coordinate>& pts);
122 
123  std::vector<Envelope> getBounds();
124 
130  void remove(std::size_t index);
131 
141  void query(const Envelope& queryEnv, std::vector<std::size_t>& result) const;
142 
143 };
144 
145 
146 
147 } // namespace geos.index
148 } // namespace geos
149 
Coordinate is the lightweight class used to store coordinates.
Definition: Coordinate.h:58
An Envelope defines a rectangulare region of the 2D coordinate plane.
Definition: Envelope.h:58
Definition: VertexSequencePackedRtree.h:49
void query(const Envelope &queryEnv, std::vector< std::size_t > &result) const
VertexSequencePackedRtree(const std::vector< Coordinate > &pts)
Basic namespace for all GEOS functionalities.
Definition: Angle.h:25