30 namespace triangulate {
59 static constexpr std::size_t NODE_CAPACITY = 16;
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;
83 std::vector<std::size_t> computeLevelOffsets();
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);
88 std::size_t levelNodeCount(std::size_t numNodes);
90 std::vector<Envelope> createBounds();
92 void fillItemBounds(std::vector<Envelope>& bounds);
93 void fillLevelBounds(std::size_t lvl, std::vector<Envelope>& bounds);
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);
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;
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);
124 std::vector<Envelope> getBounds();
131 void remove(std::size_t index);
142 void query(
const Envelope& queryEnv, std::vector<std::size_t>& result)
const;
An Envelope defines a rectangulare region of the 2D coordinate plane.
Definition: Envelope.h:58
Coordinate is the lightweight class used to store coordinates.
Definition: Coordinate.h:60
Basic namespace for all GEOS functionalities.
Definition: Angle.h:26
Definition: VertexSequencePackedRtree.h:50