GEOS  3.10.2
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 triangulate {
31 namespace polygon {
32 
33 
50 class GEOS_DLL VertexSequencePackedRtree {
51 
52 private:
53 
54 
59  static constexpr std::size_t NODE_CAPACITY = 16;
60 
61  // Members
62  const std::vector<Coordinate>& items;
63  std::vector<bool> removedItems;
64  std::vector<std::size_t> levelOffset;
65  std::size_t nodeCapacity = NODE_CAPACITY;
66  std::vector<Envelope> bounds;
67 
68 
69  // Methods
70 
71  void build();
72 
83  std::vector<std::size_t> computeLevelOffsets();
84 
85  static std::size_t ceilDivisor(std::size_t num, std::size_t denom);
86  static std::size_t clampMax(std::size_t x, std::size_t max);
87 
88  std::size_t levelNodeCount(std::size_t numNodes);
89 
90  std::vector<Envelope> createBounds();
91 
92  void fillItemBounds(std::vector<Envelope>& bounds);
93  void fillLevelBounds(std::size_t lvl, std::vector<Envelope>& bounds);
94 
95  static Envelope computeNodeEnvelope(const std::vector<Envelope>& bounds,
96  std::size_t start, std::size_t end);
97  static Envelope computeItemEnvelope(const std::vector<Coordinate>& items,
98  std::size_t start, std::size_t end);
99 
100  void queryNode(const Envelope& queryEnv,
101  std::size_t level, std::size_t nodeIndex,
102  std::vector<std::size_t>& result) const;
103  void queryNodeRange(const Envelope& queryEnv,
104  std::size_t level, std::size_t nodeStartIndex,
105  std::vector<std::size_t>& result) const;
106  void queryItemRange(const Envelope& queryEnv, std::size_t itemIndex,
107  std::vector<std::size_t>& result) const;
108 
109  std::size_t levelSize(std::size_t level) const;
110  bool isNodeEmpty(std::size_t level, std::size_t index);
111  bool isItemsNodeEmpty(std::size_t nodeIndex);
112 
113 
114 public:
115 
122  VertexSequencePackedRtree(const std::vector<Coordinate>& pts);
123 
124  std::vector<Envelope> getBounds();
125 
131  void remove(std::size_t index);
132 
142  void query(const Envelope& queryEnv, std::vector<std::size_t>& result) const;
143 
144 };
145 
146 
147 
148 } // namespace geos.triangulate.polygon
149 } // namespace geos.triangulate
150 } // namespace geos
151 
Coordinate is the lightweight class used to store coordinates.
Definition: Coordinate.h:60
An Envelope defines a rectangulare region of the 2D coordinate plane.
Definition: Envelope.h:58
Definition: VertexSequencePackedRtree.h:50
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:26