tpl_r_tree.H File Reference

Dynamic R-tree spatial index over axis-aligned rectangles. More...

#include <algorithm>
#include <array>
#include <concepts>
#include <cstddef>
#include <limits>
#include <memory>
#include <type_traits>
#include <utility>
#include <ah-errors.H>
#include <point.H>
#include <tpl_array.H>

Include dependency graph for tpl_r_tree.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >
	Dynamic R-tree indexing axis-aligned rectangles by payload. More...
struct	Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Entry
	A stored (bounding box, payload) pair. More...
struct	Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::DebugNode
	One node of a debug_snapshot, independent of Payload. More...
struct	Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::DebugSnapshot
	Full tree structure captured for visualization/debugging. More...
struct	Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Child
	Internal-node entry: a child subtree plus its tight bounding box. More...
struct	Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node
	A node is a leaf holding data or an internal node holding children. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Enumerations
enum class	Aleph::RTreeVariant { Aleph::Guttman , Aleph::RStar }
	Node-split / insertion strategy for RTree. More...

Detailed Description

Dynamic R-tree spatial index over axis-aligned rectangles.

RTree<Payload, MaxEntries, MinEntries> is a dynamic spatial index that associates axis-aligned bounding boxes (Aleph::Rectangle) with user payloads and supports incremental insert / erase plus intersection and point-containment queries. It is Guttman's R-tree with the quadratic node split heuristic.

Unlike the static AABBTree (in geom_algorithms.H), which is built once from a fixed batch of boxes, RTree may be updated in place after construction. AABBTree is likely faster for immutable batches; RTree targets workloads that insert and delete over time.

Complexity

With well-distributed data, insert, erase and point queries are expected O(log n). Overlapping-region queries cost O(log n + k) for k reported entries, degrading to O(n) when many node bounding boxes overlap the query. height() and size() are O(1).

Exception safety

All operations use exact rational coordinates (Aleph::Geom_Number), so no floating-point rounding affects the structure. Allocation failure throws std::bad_alloc; size overflow throws std::overflow_error. Mutating operations are not transactional: they do not provide the strong guarantee after tree mutation has started, and exceptions from Payload operations propagate according to the payload type's own guarantees. Public preconditions are checked with the macros of ah-errors.H.

Thread safety

RTree is a sequential container: it is not internally synchronized. Concurrent read-only queries on a tree that no one is mutating are safe; any concurrent mutation requires external synchronization.

Reference/iterator invalidation

The tree exposes no live iterators. search_intersects and search_contains return independent Array copies. References passed to for_each_intersecting are valid only during the callback invocation. Any insert, erase or clear invalidates every previously obtained reference into the tree.

Definition in file tpl_r_tree.H.