|
| | IntervalTree ()=default |
| template<class Container> |
| | IntervalTree (const Container &shapes) |
| | Builds a tree by inserting every shape in shapes.
|
| std::size_t | size () const |
| | Returns the number of stored shapes.
|
| bool | empty () const |
| | Returns whether no shape is stored.
|
| const std::vector< ShapeType > & | shapes () const |
| | Returns the stored shapes in internal storage order.
|
| const_iterator | begin () const |
| | Returns a constant iterator to the first stored shape.
|
| const_iterator | end () const |
| | Returns a constant iterator past the last stored shape.
|
| const_iterator | cbegin () const |
| | Returns a constant iterator to the first stored shape.
|
| const_iterator | cend () const |
| | Returns a constant iterator past the last stored shape.
|
| void | insert (const ShapeType &shape) |
| | Inserts shape and its selected closed bounding-box interval.
|
| bool | erase (const ShapeType &shape) |
| | Removes one stored shape equal to shape.
|
| bool | has (const ShapeType &shape) const |
| | Returns whether a shape equal to shape is stored.
|
| template<class Q> |
| std::size_t | countProjectionsIntersecting (const Q &q) const |
| | Counts shapes whose projected interval intersects the projection of q.
|
| template<class Q> |
| std::vector< ShapeType > | reportProjectionsIntersecting (const Q &q) const |
| | Returns copies of shapes whose projected interval intersects that of q.
|
| template<class Q, class Fn> |
| bool | visitProjectionsIntersecting (const Q &q, Fn fn) const |
| | Visits projected-interval intersections, stopping early if fn returns true.
|
| template<class Q> |
| bool | emptyProjectionsIntersecting (const Q &q) const |
| | Returns whether no stored projected interval intersects the projection of q.
|
| template<class Q> |
| std::size_t | countProjectionsContainedIn (const Q &q) const |
| | Counts shapes whose projected interval is contained in the projection of q.
|
| template<class Q> |
| std::vector< ShapeType > | reportProjectionsContainedIn (const Q &q) const |
| | Returns copies of shapes whose projected interval is contained in that of q.
|
| template<class Q, class Fn> |
| bool | visitProjectionsContainedIn (const Q &q, Fn fn) const |
| | Visits projected intervals contained in q, stopping early if fn returns true.
|
| template<class Q> |
| bool | emptyProjectionsContainedIn (const Q &q) const |
| | Returns whether no stored projected interval is contained in that of q.
|
| template<class Q> |
| std::size_t | countIntersecting (const Q &q) const |
| | Counts stored shapes that geometrically intersect q.
|
| template<class Q> |
| std::vector< ShapeType > | reportIntersecting (const Q &q) const |
| | Returns copies of stored shapes that geometrically intersect q.
|
| template<class Q, class Fn> |
| bool | visitIntersecting (const Q &q, Fn fn) const |
| | Visits stored shapes that geometrically intersect q.
|
| template<class Q> |
| bool | emptyIntersecting (const Q &q) const |
| | Returns whether no stored shape geometrically intersects q.
|
| template<class Q> |
| std::size_t | countContainedIn (const Q &q) const |
| | Counts stored shapes geometrically contained in q.
|
| template<class Q> |
| std::vector< ShapeType > | reportContainedIn (const Q &q) const |
| | Returns copies of stored shapes geometrically contained in q.
|
| template<class Q, class Fn> |
| bool | visitContainedIn (const Q &q, Fn fn) const |
| | Visits stored shapes geometrically contained in q.
|
| template<class Q> |
| bool | emptyContainedIn (const Q &q) const |
| | Returns whether no stored shape is geometrically contained in q.
|
template<class S,
ProjectionAxis Axis = ProjectionAxis::x>
class pgl::IntervalTree< S, Axis >
Mutable interval tree over the projection of bounded shapes.
Each stored shape owns one closed interval: the x or y extent of its bounding box, selected by Axis. Queries apply the same projection to their argument, so this is intentionally a one-dimensional index: matching does not imply that the original two-dimensional shapes meet or contain one another.
Nodes form a red-black tree ordered by (low endpoint, high endpoint, node
ID). The ID keeps equal projected intervals distinct. Every node caches the extrema of both endpoints in its subtree. In particular, maxHigh is the standard augmented interval-tree value used to prune subtrees lying completely before an intersection query. Query fields are stored separately from insertion-only parent/color state, and 32-bit node IDs keep the hot representation compact.
Removal tombstones a node rather than unlinking it: the node keeps its place in the tree but owns no shape, so it stops matching queries, and the whole index is rebuilt only once tombstones outnumber live nodes. Removals are therefore logarithmic on average, and the node array never exceeds twice the number of stored shapes. A node ID still indexes the stored shapes directly: the live nodes are exactly the first size() slots, so a removal moves the last live node into the freed slot and the tombstone to the end. One tree can hold at most 2^32 - 2 nodes, shapes and tombstones together, so at least 2^31 - 1 shapes always fit.
- Template Parameters
-
| S | Shape type exposing a finite bbox(). |
| Axis | Coordinate used for the one-dimensional projection. |
Removes one stored shape equal to shape.
The owning node is located through the projected interval and then tombstoned: it stays in the tree, keeping it balanced, but owns no shape and is counted by nothing, so every query ignores it. The shape itself is swap-removed from storage, so shapes() stays compact and only the element order may change; the last live node moves into the freed slot so that a node ID keeps being the index of the shape it owns.
Once tombstones outnumber the live nodes, the index is rebuilt from the surviving shapes, yielding a structure with the same red-black and augmentation invariants as a freshly constructed tree. A rebuild costs O(n log n) but follows at least n / 2 removals, so a removal costs O(log n + k) amortized, where k is the number of stored intervals sharing the projected endpoints of shape.
- Parameters
-
- Returns
- true if a matching shape was found and removed, false otherwise.
1.17.0