Dynamic R-tree indexing axis-aligned rectangles by payload. More...

#include <tpl_r_tree.H>

Inheritance diagram for Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >:

Collaboration diagram for Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >:

Classes
struct	Child
	Internal-node entry: a child subtree plus its tight bounding box. More...

struct	DebugNode
	One node of a debug_snapshot, independent of `Payload`. More...

struct	DebugSnapshot
	Full tree structure captured for visualization/debugging. More...

struct	Entry
	A stored (bounding box, payload) pair. More...

struct	Node
	A node is a leaf holding data or an internal node holding children. More...

Public Member Functions
	RTree () noexcept=default
	Construct an empty R-tree.

	RTree (RTree &&other) noexcept
	Move-construct from `other`, leaving it empty and valid.

RTree &	operator= (RTree &&other) noexcept
	Move-assign from `other`, leaving it empty and valid.

	RTree (const RTree &other)
	Deep-copy `other` (requires copy-constructible, movable `Payload`).

RTree &	operator= (const RTree &other)
	Deep-copy assign from `other` (requires copy-constructible, movable `Payload`).

bool	is_empty () const noexcept
	Return true when the tree has no entries.

size_t	size () const noexcept
	Return the number of stored entries.

size_t	height () const noexcept
	Return the number of node levels (0 when empty, 1 for a lone leaf).

void	clear () noexcept
	Remove all entries.

void	insert (const Rectangle &bbox, const Payload &value)
	Insert a (bbox, value) entry, copying `value`.

void	insert (const Rectangle &bbox, Payload &&value)
	Insert a (bbox, value) entry, moving `value`.

bool	erase (const Rectangle &bbox, const Payload &value)
	Remove one entry equal to (`bbox`, `value`).

template<typename F >
void	for_each_intersecting (const Rectangle &rect, F &&f) const
	Invoke `f` for every entry whose bbox intersects `rect`.

Array< Payload >	search_intersects (const Rectangle &rect) const
	Return the payloads of every entry whose bbox intersects `rect`.

Array< Payload >	search_contains (const Point &p) const
	Return the payloads of every entry whose bbox contains `p`.

bool	verify () const
	Verify the R-tree structural invariants.

DebugSnapshot	debug_snapshot () const
	Capture the full tree structure for visualization/debugging.

Private Member Functions
void	clear_rstar_reinsert_state () noexcept
	Drop R*-tree transient insertion state.

void	reinsert_farthest (Node &node)
	Move the R*-tree forced-reinsert candidates (the entries farthest from the node centre) out of the overflowed leaf `node` and into rstar_reinsert_buffer_, leaving `node` validly sized.

std::unique_ptr< Node >	insert_descend (Node &node, Entry entry)
	Insert `entry` at the leaf level of `node`.

void	insert_one (Entry entry)
	Insert one data entry into the tree (no size_ change, no reinsert-buffer management).

void	add_entry (Entry entry)
	Add a data entry without touching size_ (shared by `insert` and by erase-time reinsertion).

void	erase_descend (Node &node, const Rectangle &bbox, const Payload &value, Array< Entry > &orphans, bool &removed)
	Remove one entry equal to (`bbox`, `value`) from `node's` subtree.

template<typename F >
void	for_each_intersecting_rec (const Node &node, const Rectangle &rect, F &f) const

template<typename F >
void	for_each_containing_rec (const Node &node, const Point &p, F &f) const

bool	verify_rec (const Node &node, const size_t depth, const bool is_root, size_t &leaf_depth, size_t &count, Rectangle &out_mbr) const

Static Private Member Functions
static Rectangle	union_bbox (const Rectangle &a, const Rectangle &b)

static Geom_Number	enlargement (const Rectangle &base, const Rectangle &added)
	Area added to `base` by growing it to also cover `added`.

static Geom_Number	overlap_area (const Rectangle &a, const Rectangle &b)
	Area of the overlap between two rectangles (0 if disjoint).

static size_t	entry_count (const Node &node)

static Rectangle	compute_mbr (const Node &node)
	Tight bounding box covering every entry of `node`.

static size_t	choose_subtree (const Node &node, const Rectangle &bbox)
	Choose the child of `node` into which `bbox` should be inserted.

static size_t	rstar_choose_overlap (const Node &node, const Rectangle &bbox)
	R*-tree ChooseSubtree for a node whose children are leaves: pick the child whose growth adds the least overlap with its siblings (ties: least area enlargement, then least area).

template<typename EntryT >
static Array< EntryT >	quadratic_split (Array< EntryT > &entries)
	Split an overflowed entry array in two using the quadratic heuristic.

template<typename EntryT >
static Array< EntryT >	rstar_split (Array< EntryT > &entries)
	R*-tree split: choose the split axis minimizing the total margin of the two groups, then the distribution minimizing their overlap area (ties: minimum total area).

template<typename EntryT >
static Array< EntryT >	split_entries (Array< EntryT > &entries)
	Split the entry array of `node` according to the active variant.

static void	collect_data_entries (Node &node, Array< Entry > &out)
	Move every data entry in `node's` subtree into `out`.

static size_t	data_entry_count (const Node &node)

static bool	box_contains_box (const Rectangle &outer, const Rectangle &inner)
	True iff `outer` fully covers `inner`.

static std::unique_ptr< Node >	clone_node (const Node &node)

Private Attributes
std::unique_ptr< Node >	root_

size_t	size_ = 0
	Number of stored data entries.

size_t	height_ = 0
	Number of node levels (0 when empty).

bool	rstar_reinsert_available_ = false
	Leaf-level reinsert not yet used this insert.

Array< Entry >	rstar_reinsert_buffer_
	Entries pending forced reinsertion.

Detailed Description

template<typename Payload, size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>
class Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >

Dynamic R-tree indexing axis-aligned rectangles by payload.

Template Parameters

Payload	Value associated with each stored bounding box. Must be default-initializable and movable. Copying APIs additionally require copy construction.
MaxEntries	Maximum number of entries per node. Must be at least 2.
MinEntries	Minimum number of entries per non-root node. Must be at least 1 and satisfy `2 * MinEntries <= MaxEntries + 1`. Defaults to `MaxEntries / 2`.
Variant	Node-split/insertion strategy (RTreeVariant). Defaults to Guttman's quadratic split; `RStar` selects the R*-tree heuristics.

Definition at line 117 of file tpl_r_tree.H.

Constructor & Destructor Documentation

◆ RTree() [1/3]

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::RTree ( )

defaultnoexcept

Construct an empty R-tree.

Exceptions

Nothing.

◆ RTree() [2/3]

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::RTree ( RTree< Payload, MaxEntries, MinEntries, Variant > && other )

inlinenoexcept

Move-construct from other, leaving it empty and valid.

Parameters

other Tree to move from.

Postcondition: other.is_empty() is true and other remains a valid, usable tree (not merely moved-from).

Complexity O(1).

Exceptions

Nothing.

Definition at line 863 of file tpl_r_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size_.

◆ RTree() [3/3]

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::RTree ( const RTree< Payload, MaxEntries, MinEntries, Variant > & other )

inline

Deep-copy other (requires copy-constructible, movable Payload).

Parameters

other Tree to clone.

Exceptions

std::bad_alloc or whatever copying Payload throws.

Definition at line 897 of file tpl_r_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::clone_node(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::root_.

Member Function Documentation

◆ add_entry()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

void Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::add_entry ( Entry entry )

inlineprivate

Add a data entry without touching size_ (shared by insert and by erase-time reinsertion).

For the R*-tree variant this also drives one round of leaf-level forced reinsertion.

Definition at line 651 of file tpl_r_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::clear_rstar_reinsert_state(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert_one(), Aleph::RStar, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::rstar_reinsert_available_, and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::rstar_reinsert_buffer_.

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::erase(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert().

◆ box_contains_box()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

static bool Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::box_contains_box	(	const Rectangle &	outer,
		const Rectangle &	inner
	)

inlinestaticprivate

True iff outer fully covers inner.

Definition at line 749 of file tpl_r_tree.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::Rectangle::get_xmax(), Aleph::Rectangle::get_xmin(), Aleph::Rectangle::get_ymax(), and Aleph::Rectangle::get_ymin().

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::erase_descend().

◆ choose_subtree()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

static size_t Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::choose_subtree	(	const Node &	node,
		const Rectangle &	bbox
	)

inlinestaticprivate

Choose the child of node into which bbox should be inserted.

R*-tree minimizes overlap enlargement when the children are leaves.

Definition at line 246 of file tpl_r_tree.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node::children, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::enlargement(), Aleph::RStar, and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::rstar_choose_overlap().

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert_descend().

◆ clear()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

void Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::clear ( )

inlinenoexcept

Remove all entries.

Exceptions

Nothing.

Definition at line 954 of file tpl_r_tree.H.

References Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::clear_rstar_reinsert_state(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::height_, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::root_, and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size_.

Referenced by TEST().

◆ clear_rstar_reinsert_state()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

void Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::clear_rstar_reinsert_state ( )

inlineprivatenoexcept

Drop R*-tree transient insertion state.

Definition at line 186 of file tpl_r_tree.H.

References Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::rstar_reinsert_available_, and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::rstar_reinsert_buffer_.

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::add_entry(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::clear(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::operator=().

◆ clone_node()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

static std::unique_ptr< Node > Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::clone_node ( const Node & node )

inlinestaticprivate

Definition at line 789 of file tpl_r_tree.H.

References Aleph::copy().

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::RTree(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::operator=().

◆ collect_data_entries()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

static void Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::collect_data_entries	(	Node &	node,
		Array< Entry > &	out
	)

inlinestaticprivate

Move every data entry in node's subtree into out.

Definition at line 668 of file tpl_r_tree.H.

References Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node::children, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::collect_data_entries(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node::data, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node::leaf, and out.

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::collect_data_entries(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::erase_descend().

◆ compute_mbr()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

static Rectangle Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::compute_mbr ( const Node & node )

inlinestaticprivate

Tight bounding box covering every entry of node.

Definition at line 229 of file tpl_r_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node::children, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node::data, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node::leaf, and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::union_bbox().

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::debug_snapshot(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::erase_descend(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert_descend(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert_one(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::reinsert_farthest(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::verify_rec().

◆ data_entry_count()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

static size_t Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::data_entry_count ( const Node & node )

inlinestaticprivate

Definition at line 680 of file tpl_r_tree.H.

References ah_overflow_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node::children, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node::data, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::data_entry_count(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node::leaf.

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::data_entry_count(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::erase_descend().

◆ debug_snapshot()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

DebugSnapshot Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::debug_snapshot ( ) const

inline

Capture the full tree structure for visualization/debugging.

Returns: A DebugSnapshot with every node in preorder; empty (nodes empty, root unset) when the tree is_empty().

Complexity: O(n) time; O(height_) recursive call-stack depth.

Thread safety: Concurrent read-only calls are safe only while no thread mutates the tree. Concurrent mutation requires external synchronization.

Exceptions

std::bad_alloc if node allocation fails.

Definition at line 1114 of file tpl_r_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::compute_mbr(), Aleph::Array< T >::reserve(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::root_.

Referenced by TEST(), TEST(), TEST(), TEST(), Aleph::visualize_rtree(), and Aleph::visualize_rtree_query().

◆ enlargement()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

static Geom_Number Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::enlargement	(	const Rectangle &	base,
		const Rectangle &	added
	)

inlinestaticprivate

Area added to base by growing it to also cover added.

Definition at line 204 of file tpl_r_tree.H.

References Aleph::Rectangle::area(), Aleph::blossom_maximum_cardinality_matching(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::union_bbox().

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::choose_subtree(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::quadratic_split().

◆ entry_count()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

static size_t Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::entry_count ( const Node & node )

inlinestaticprivate

Definition at line 223 of file tpl_r_tree.H.

References Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node::children, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node::data, and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node::leaf.

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::erase_descend(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::verify_rec().

◆ erase()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

bool Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::erase	(	const Rectangle &	bbox,
		const Payload &	value
	)

inline

Remove one entry equal to (bbox, value).

Parameters

bbox	Bounding box of the entry to remove.
value	Payload to match (by `==`).

Returns: true if an entry was removed, false if none matched.

Exceptions

std::bad_alloc if reinsertion of condensed entries allocates.

Note: Requires Payload to be equality-comparable. Uses a CondenseTree variant that reinserts the data entries of any underflowing node.

Definition at line 1000 of file tpl_r_tree.H.

References Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::add_entry(), Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::erase_descend(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::height_, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::root_, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size_, and value.

Referenced by main(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ erase_descend()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

void Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::erase_descend	(	Node &	node,
		const Rectangle &	bbox,
		const Payload &	value,
		Array< Entry > &	orphans,
		bool &	removed
	)

inlineprivate

Remove one entry equal to (bbox, value) from node's subtree.

On success sets removed and moves the data entries of any underflowing descendant into orphans (for reinsertion).

Definition at line 698 of file tpl_r_tree.H.

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::erase(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::erase_descend().

◆ for_each_containing_rec()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

template<typename F >

void Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::for_each_containing_rec	(	const Node &	node,
		const Point &	p,
		F &	f
	)		const

inlineprivate

Definition at line 773 of file tpl_r_tree.H.

References Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node::children, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node::data, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::for_each_containing_rec(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node::leaf.

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::for_each_containing_rec(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::search_contains().

◆ for_each_intersecting()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

template<typename F >

void Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::for_each_intersecting	(	const Rectangle &	rect,
		F &&	f
	)		const

inline

Invoke f for every entry whose bbox intersects rect.

Template Parameters

F	Callable as `f(const Rectangle &bbox, const Payload &value)`.

Parameters

rect	Query rectangle.
f	Visitor invoked for each intersecting entry.

Exceptions

Whatever f throws.

Note: Works for move-only Payload: it passes references, never copies.

Definition at line 1042 of file tpl_r_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::for_each_intersecting_rec(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::root_.

Referenced by main(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::search_intersects(), TEST(), TEST(), and Aleph::visualize_rtree_query().

◆ for_each_intersecting_rec()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

template<typename F >

void Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::for_each_intersecting_rec	(	const Node &	node,
		const Rectangle &	rect,
		F &	f
	)		const

inlineprivate

Definition at line 758 of file tpl_r_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node::children, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node::data, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::for_each_intersecting_rec(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node::leaf.

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::for_each_intersecting(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::for_each_intersecting_rec().

◆ height()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

size_t Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::height ( ) const

inlinenoexcept

Return the number of node levels (0 when empty, 1 for a lone leaf).

Returns: Tree height in levels.

Exceptions

Nothing.

Definition at line 946 of file tpl_r_tree.H.

References Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::height_.

Referenced by main(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ insert() [1/2]

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

void Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert	(	const Rectangle &	bbox,
		const Payload &	value
	)

inline

Insert a (bbox, value) entry, copying value.

Parameters

bbox	Bounding box of the entry.
value	Payload to store.

Exceptions

std::bad_alloc	if node allocation fails.
std::overflow_error	if the stored-entry count would overflow.
Whatever	copying `Payload` throws.

Definition at line 969 of file tpl_r_tree.H.

References Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::add_entry(), ah_overflow_error_if, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size_, and value.

Referenced by main(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ insert() [2/2]

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

void Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert	(	const Rectangle &	bbox,
		Payload &&	value
	)

inline

Insert a (bbox, value) entry, moving value.

Parameters

bbox	Bounding box of the entry.
value	Payload to move into the tree.

Exceptions

std::bad_alloc	if node allocation fails.
std::overflow_error	if the stored-entry count would overflow.
Whatever	moving `Payload` throws.

Definition at line 984 of file tpl_r_tree.H.

References Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::add_entry(), ah_overflow_error_if, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size_, and value.

◆ insert_descend()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

std::unique_ptr< Node > Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert_descend	(	Node &	node,
		Entry	entry
	)

inlineprivate

Insert entry at the leaf level of node.

Returns a new sibling node when node overflowed and had to be split, else nullptr.

Definition at line 577 of file tpl_r_tree.H.

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert_descend(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert_one().

◆ insert_one()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

void Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert_one ( Entry entry )

inlineprivate

Insert one data entry into the tree (no size_ change, no reinsert-buffer management).

Definition at line 622 of file tpl_r_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::compute_mbr(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::height_, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert_descend(), root(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::root_, and Aleph::split().

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::add_entry().

◆ is_empty()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

bool Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::is_empty ( ) const

inlinenoexcept

Return true when the tree has no entries.

Returns: true iff size() == 0.

Exceptions

Nothing.

Definition at line 928 of file tpl_r_tree.H.

References Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size_.

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ operator=() [1/2]

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

RTree & Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::operator= ( const RTree< Payload, MaxEntries, MinEntries, Variant > & other )

inline

Deep-copy assign from other (requires copy-constructible, movable Payload).

Parameters

other Tree to clone.

Returns: Reference to this tree.

Exceptions

std::bad_alloc or whatever copying Payload throws.

Definition at line 910 of file tpl_r_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::clone_node(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::height_, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::root_, and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size_.

◆ operator=() [2/2]

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

RTree & Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::operator= ( RTree< Payload, MaxEntries, MinEntries, Variant > && other )

inlinenoexcept

Move-assign from other, leaving it empty and valid.

Parameters

other Tree to move from.

Returns: Reference to this tree.

Postcondition: other.is_empty() is true and other remains a valid, usable tree (not merely moved-from).

Complexity O(1).

Exceptions

Nothing.

Definition at line 879 of file tpl_r_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::clear_rstar_reinsert_state(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::height_, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::root_, and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size_.

◆ overlap_area()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

static Geom_Number Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::overlap_area	(	const Rectangle &	a,
		const Rectangle &	b
	)

inlinestaticprivate

Area of the overlap between two rectangles (0 if disjoint).

Definition at line 210 of file tpl_r_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Rectangle::get_xmax(), Aleph::Rectangle::get_xmin(), Aleph::Rectangle::get_ymax(), and Aleph::Rectangle::get_ymin().

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::rstar_choose_overlap(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::rstar_split().

◆ quadratic_split()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

template<typename EntryT >

static Array< EntryT > Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::quadratic_split ( Array< EntryT > & entries )

inlinestaticprivate

Split an overflowed entry array in two using the quadratic heuristic.

entries keeps the first group; the second group is returned.

Template Parameters

EntryT is either Entry or Child.

Definition at line 309 of file tpl_r_tree.H.

References Aleph::Array< T >::append(), Aleph::Rectangle::area(), Aleph::blossom_maximum_cardinality_matching(), Aleph::diff(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::enlargement(), k, Aleph::Array< T >::size(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::union_bbox().

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::split_entries().

◆ reinsert_farthest()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

void Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::reinsert_farthest ( Node & node )

inlineprivate

Move the R*-tree forced-reinsert candidates (the entries farthest from the node centre) out of the overflowed leaf node and into rstar_reinsert_buffer_, leaving node validly sized.

Definition at line 546 of file tpl_r_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Rectangle::center(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::compute_mbr(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node::data, k, and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::rstar_reinsert_buffer_.

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert_descend().

◆ rstar_choose_overlap()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

static size_t Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::rstar_choose_overlap	(	const Node &	node,
		const Rectangle &	bbox
	)

inlinestaticprivate

R*-tree ChooseSubtree for a node whose children are leaves: pick the child whose growth adds the least overlap with its siblings (ties: least area enlargement, then least area).

Definition at line 272 of file tpl_r_tree.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node::children, k, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::overlap_area(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::union_bbox().

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::choose_subtree().

◆ rstar_split()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

template<typename EntryT >

static Array< EntryT > Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::rstar_split ( Array< EntryT > & entries )

inlinestaticprivate

R*-tree split: choose the split axis minimizing the total margin of the two groups, then the distribution minimizing their overlap area (ties: minimum total area).

entries keeps the first group; the second group is returned.

Definition at line 426 of file tpl_r_tree.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), k, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::overlap_area(), Aleph::prefix(), Aleph::Array< T >::size(), Aleph::suffix(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::union_bbox().

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::split_entries().

◆ search_contains()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

Array< Payload > Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::search_contains ( const Point & p ) const

inline

Return the payloads of every entry whose bbox contains p.

Parameters

p	Query point.

Returns: Array with a copy of each matching payload.

Exceptions

std::bad_alloc or whatever copying Payload throws.

Definition at line 1069 of file tpl_r_tree.H.

References Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::for_each_containing_rec(), out, and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::root_.

Referenced by main(), and TEST().

◆ search_intersects()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

Array< Payload > Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::search_intersects ( const Rectangle & rect ) const

inline

Return the payloads of every entry whose bbox intersects rect.

Parameters

rect	Query rectangle.

Returns: Array with a copy of each matching payload.

Exceptions

std::bad_alloc or whatever copying Payload throws.

Definition at line 1053 of file tpl_r_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::for_each_intersecting(), and out.

Referenced by main(), and TEST().

◆ size()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

size_t Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size ( ) const

inlinenoexcept

Return the number of stored entries.

Returns: Entry count.

Exceptions

Nothing.

Definition at line 937 of file tpl_r_tree.H.

References Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size_.

Referenced by main(), main(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ split_entries()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

template<typename EntryT >

static Array< EntryT > Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::split_entries ( Array< EntryT > & entries )

inlinestaticprivate

Split the entry array of node according to the active variant.

Definition at line 535 of file tpl_r_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::quadratic_split(), Aleph::RStar, and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::rstar_split().

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert_descend().

◆ union_bbox()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

static Rectangle Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::union_bbox	(	const Rectangle &	a,
		const Rectangle &	b
	)

inlinestaticprivate

Definition at line 194 of file tpl_r_tree.H.

References Aleph::Rectangle::get_xmax(), Aleph::Rectangle::get_xmin(), Aleph::Rectangle::get_ymax(), and Aleph::Rectangle::get_ymin().

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::compute_mbr(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::enlargement(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::quadratic_split(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::rstar_choose_overlap(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::rstar_split(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::verify_rec().

◆ verify()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

bool Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::verify ( ) const

inline

Verify the R-tree structural invariants.

Returns: true iff parent boxes are tight unions of their children, node occupancy is within [MinEntries, MaxEntries] (root exempt from the lower bound), all leaves share one depth, and the counted entries match size().

Exceptions

Exceptions propagated by rectangle coordinate operations while recomputing bounding boxes; Payload is not inspected.

Note: Intended for tests and diagnostics; it is O(n).

Definition at line 1091 of file tpl_r_tree.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::count(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::height_, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::root_, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size_, and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::verify_rec().

Referenced by main(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ verify_rec()

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

bool Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::verify_rec	(	const Node &	node,
		const size_t	depth,
		const bool	is_root,
		size_t &	leaf_depth,
		size_t &	count,
		Rectangle &	out_mbr
	)		const

inlineprivate

Definition at line 809 of file tpl_r_tree.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node::children, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::compute_mbr(), Aleph::count(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::entry_count(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::Node::leaf, Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::union_bbox(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::verify_rec().

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::verify(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::verify_rec().

Member Data Documentation

◆ height_

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

size_t Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::height_ = 0

private

Number of node levels (0 when empty).

Definition at line 179 of file tpl_r_tree.H.

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::clear(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::erase(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::height(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert_one(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::operator=(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::operator=(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::verify().

◆ root_

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

std::unique_ptr<Node> Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::root_

private

Definition at line 177 of file tpl_r_tree.H.

◆ rstar_reinsert_available_

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

bool Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::rstar_reinsert_available_ = false

private

Leaf-level reinsert not yet used this insert.

Definition at line 182 of file tpl_r_tree.H.

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::add_entry(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::clear_rstar_reinsert_state(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::insert_descend().

◆ rstar_reinsert_buffer_

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

Array<Entry> Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::rstar_reinsert_buffer_

private

Entries pending forced reinsertion.

Definition at line 183 of file tpl_r_tree.H.

Referenced by Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::add_entry(), Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::clear_rstar_reinsert_state(), and Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::reinsert_farthest().

◆ size_

template<typename Payload , size_t MaxEntries = 16, size_t MinEntries = MaxEntries / 2, RTreeVariant Variant = RTreeVariant::Guttman>

size_t Aleph::RTree< Payload, MaxEntries, MinEntries, Variant >::size_ = 0

private

Number of stored data entries.

Definition at line 178 of file tpl_r_tree.H.

The documentation for this class was generated from the following file:

tpl_r_tree.H

Classes

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ RTree() [1/3]

◆ RTree() [2/3]

◆ RTree() [3/3]

Member Function Documentation

◆ add_entry()

◆ box_contains_box()

◆ choose_subtree()

◆ clear()

◆ clear_rstar_reinsert_state()

◆ clone_node()

◆ collect_data_entries()

◆ compute_mbr()

◆ data_entry_count()

◆ debug_snapshot()

◆ enlargement()

◆ entry_count()

◆ erase()

◆ erase_descend()

◆ for_each_containing_rec()

◆ for_each_intersecting()

◆ for_each_intersecting_rec()

◆ height()

◆ insert() [1/2]

◆ insert() [2/2]

◆ insert_descend()

◆ insert_one()

◆ is_empty()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ overlap_area()

◆ quadratic_split()

◆ reinsert_farthest()

◆ rstar_choose_overlap()

◆ rstar_split()

◆ search_contains()

◆ search_intersects()

◆ size()

◆ split_entries()

◆ union_bbox()

◆ verify()

◆ verify_rec()

Member Data Documentation

◆ height_

◆ root_

◆ rstar_reinsert_available_

◆ rstar_reinsert_buffer_

◆ size_