Axis-aligned bounding box tree for spatial queries. More...

#include <geom_algorithms.H>

Collaboration diagram for Aleph::AABBTree:

Classes
struct	DebugNode
	Structure used for debugging and visualizing the tree structure. More...

struct	DebugSnapshot
	A snapshot of the entire tree for debugging. More...

struct	Entry
	An entry in the tree, consisting of a bounding box and a user-defined index. More...

struct	Node
	Internal tree node structure. More...

Public Member Functions
	AABBTree ()=default

void	build (const Array< Entry > &entries)
	Build the AABB tree from an array of entries.

Array< size_t >	query (const Rectangle &query) const
	Find all entries whose bounding box overlaps the query rectangle.

Array< size_t >	query_point (const Point &p) const
	Find all entries whose bounding box contains the query point.

Rectangle	root_bbox () const
	Return the root bounding box (union of all entries).

size_t	size () const
	Number of entries.

bool	is_empty () const
	Whether the tree is empty.

DebugSnapshot	debug_snapshot () const
	Return the full tree structure for visualization/debug.

Private Member Functions
Geom_Number	center_coord (const size_t entry_idx, const bool split_x) const

void	insertion_sort_by_center (Array< size_t > &idx, const size_t lo, const size_t hi, const bool split_x) const

void	select_kth_by_center (Array< size_t > &idx, size_t lo, size_t hi, const size_t kth, const bool split_x) const

size_t	build (Array< size_t > &idx, const size_t lo, const size_t hi)

void	query_impl (const size_t ni, const Rectangle &q, Array< size_t > &results) const

void	query_point_impl (const size_t ni, const Point &p, Array< size_t > &results) const

Static Private Member Functions
static Rectangle	union_bbox (const Rectangle &a, const Rectangle &b)
	Computes the union of two axis-aligned bounding boxes.

static bool	boxes_overlap (const Rectangle &a, const Rectangle &b)
	Checks if two rectangles overlap.

static bool	box_contains_point (const Rectangle &r, const Point &p)
	Checks if a rectangle contains a point.

Private Attributes
Array< Node >	nodes_
	Internal array storing tree nodes.

Array< Entry >	entries_
	Original entries stored in the tree.

size_t	root_ = NONE

Static Private Attributes
static constexpr size_t	NONE = ~static_cast<size_t>(0)

Detailed Description

Axis-aligned bounding box tree for spatial queries.

An AABB tree organizes a collection of axis-aligned bounding boxes (rectangles) in a binary tree to accelerate spatial queries such as:

Point-in-box queries.
Box-box intersection queries.
Range queries (find all boxes overlapping a query box).

Construction

The tree is built top-down by splitting the input boxes along the longest axis of the enclosing bounding box. Each internal node stores the union bounding box of its children.

Complexity

Build: O(n log n)
Query: O(log n + k) for k results, worst case O(n).

Example: Array<AABBTree::Entry> entries;

entries.append({Rectangle(0,0,1,1), 0});

entries.append({Rectangle(2,2,3,3), 1});

AABBTree tree;

tree.build(entries);

auto hits = tree.query(Rectangle(0,0,2,2));

Aleph::AABBTree::AABBTree
AABBTree()=default

Aleph::Array
Simple dynamic array with automatic resizing and functional operations.
Definition tpl_array.H:138

Aleph::Array::append
T & append(const T &data)
Append a copy of data
Definition tpl_array.H:250

Aleph::Rectangle
An axis-aligned rectangle.
Definition point.H:1789

Author: Leandro Rabindranath León; Alejandro J. Mujica

Definition at line 12035 of file geom_algorithms.H.

Constructor & Destructor Documentation

◆ AABBTree()

Aleph::AABBTree::AABBTree ( )

default

Member Function Documentation

◆ box_contains_point()

static bool Aleph::AABBTree::box_contains_point	(	const Rectangle &	r,
		const Point &	p
	)

inlinestaticprivate

Checks if a rectangle contains a point.

Definition at line 12120 of file geom_algorithms.H.

References Aleph::and, Aleph::Point::get_x(), Aleph::Point::get_y(), and r.

Referenced by query_point_impl().

◆ boxes_overlap()

static bool Aleph::AABBTree::boxes_overlap	(	const Rectangle &	a,
		const Rectangle &	b
	)

inlinestaticprivate

Checks if two rectangles overlap.

Definition at line 12111 of file geom_algorithms.H.

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

Referenced by query_impl().

◆ build() [1/2]

size_t Aleph::AABBTree::build	(	Array< size_t > &	idx,
		const size_t	lo,
		const size_t	hi
	)

inlineprivate

Definition at line 12200 of file geom_algorithms.H.

References Aleph::AABBTree::Node::bbox, Aleph::blossom_maximum_cardinality_matching(), build(), entries_, Aleph::AABBTree::Node::entry_idx, Aleph::AABBTree::Node::left, nodes_, Aleph::AABBTree::Node::right, select_kth_by_center(), and union_bbox().

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

◆ build() [2/2]

void Aleph::AABBTree::build ( const Array< Entry > & entries )

inline

Build the AABB tree from an array of entries.

Parameters

entries Array of (bounding box, index) pairs.

Definition at line 12284 of file geom_algorithms.H.

References Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), build(), entries_, nodes_, NONE, Aleph::Array< T >::reserve(), root_, and Aleph::Array< T >::size().

◆ center_coord()

Geom_Number Aleph::AABBTree::center_coord	(	const size_t	entry_idx,
		const bool	split_x
	)		const

inlineprivate

Definition at line 12126 of file geom_algorithms.H.

References entries_.

Referenced by insertion_sort_by_center(), and select_kth_by_center().

◆ debug_snapshot()

DebugSnapshot Aleph::AABBTree::debug_snapshot ( ) const

inline

Return the full tree structure for visualization/debug.

Definition at line 12350 of file geom_algorithms.H.

References Aleph::AABBTree::Node::bbox, Aleph::blossom_maximum_cardinality_matching(), entries_, Aleph::AABBTree::Node::entry_idx, Aleph::AABBTree::Node::is_leaf(), Aleph::AABBTree::Node::left, Aleph::AABBTree::DebugSnapshot::nodes, nodes_, NONE, Aleph::AABBTree::Node::right, and root_.

Referenced by TEST_F(), TEST_F(), Aleph::visualize_aabb_tree(), and Aleph::visualize_aabb_tree_query().

◆ insertion_sort_by_center()

void Aleph::AABBTree::insertion_sort_by_center	(	Array< size_t > &	idx,
		const size_t	lo,
		const size_t	hi,
		const bool	split_x
	)		const

inlineprivate

Definition at line 12132 of file geom_algorithms.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), and center_coord().

Referenced by select_kth_by_center().

◆ is_empty()

bool Aleph::AABBTree::is_empty ( ) const

inline

Whether the tree is empty.

Definition at line 12344 of file geom_algorithms.H.

References entries_.

Referenced by TEST_F(), and TEST_F().

◆ query()

Array< size_t > Aleph::AABBTree::query ( const Rectangle & query ) const

inline

Find all entries whose bounding box overlaps the query rectangle.

Parameters

query The query bounding box.

Returns: Array of user-defined indices of overlapping entries.

Definition at line 12308 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), NONE, query(), query_impl(), and root_.

Referenced by query(), TEST_F(), and Aleph::visualize_aabb_tree_query().

◆ query_impl()

void Aleph::AABBTree::query_impl	(	const size_t	ni,
		const Rectangle &	q,
		Array< size_t > &	results
	)		const

inlineprivate

Definition at line 12237 of file geom_algorithms.H.

References Aleph::AABBTree::Node::bbox, Aleph::blossom_maximum_cardinality_matching(), boxes_overlap(), entries_, Aleph::AABBTree::Node::entry_idx, Aleph::AABBTree::Node::is_leaf(), Aleph::AABBTree::Node::left, nodes_, NONE, query_impl(), and Aleph::AABBTree::Node::right.

Referenced by query(), and query_impl().

◆ query_point()

Array< size_t > Aleph::AABBTree::query_point ( const Point & p ) const

inline

Find all entries whose bounding box contains the query point.

Parameters

p	The query point.

Returns: Array of user-defined indices of entries containing p.

Definition at line 12322 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), NONE, query_point_impl(), and root_.

Referenced by TEST_F(), and TEST_F().

◆ query_point_impl()

void Aleph::AABBTree::query_point_impl	(	const size_t	ni,
		const Point &	p,
		Array< size_t > &	results
	)		const

inlineprivate

Definition at line 12255 of file geom_algorithms.H.

References Aleph::AABBTree::Node::bbox, Aleph::blossom_maximum_cardinality_matching(), box_contains_point(), entries_, Aleph::AABBTree::Node::entry_idx, Aleph::AABBTree::Node::is_leaf(), Aleph::AABBTree::Node::left, nodes_, NONE, query_point_impl(), and Aleph::AABBTree::Node::right.

Referenced by query_point(), and query_point_impl().

◆ root_bbox()

Rectangle Aleph::AABBTree::root_bbox ( ) const

inline

Return the root bounding box (union of all entries).

Definition at line 12331 of file geom_algorithms.H.

References ah_domain_error_if, nodes_, NONE, and root_.

Referenced by TEST_F().

◆ select_kth_by_center()

void Aleph::AABBTree::select_kth_by_center	(	Array< size_t > &	idx,
		size_t	lo,
		size_t	hi,
		const size_t	kth,
		const bool	split_x
	)		const

inlineprivate

Definition at line 12153 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), center_coord(), and insertion_sort_by_center().

Referenced by build().

◆ size()

size_t Aleph::AABBTree::size ( ) const

inline

Number of entries.

Definition at line 12338 of file geom_algorithms.H.

References entries_.

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

◆ union_bbox()

static Rectangle Aleph::AABBTree::union_bbox	(	const Rectangle &	a,
		const Rectangle &	b
	)

inlinestaticprivate

Computes the union of two axis-aligned bounding boxes.

Definition at line 12099 of file geom_algorithms.H.

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

Referenced by build().

Member Data Documentation

◆ entries_

Array<Entry> Aleph::AABBTree::entries_

private

Original entries stored in the tree.

Definition at line 12092 of file geom_algorithms.H.

Referenced by build(), build(), center_coord(), debug_snapshot(), is_empty(), query_impl(), query_point_impl(), and size().

◆ nodes_

Array<Node> Aleph::AABBTree::nodes_

private

Internal array storing tree nodes.

Definition at line 12091 of file geom_algorithms.H.

Referenced by build(), build(), debug_snapshot(), query_impl(), query_point_impl(), and root_bbox().

◆ NONE

constexpr size_t Aleph::AABBTree::NONE = ~static_cast<size_t>(0)

staticconstexprprivate

Definition at line 12094 of file geom_algorithms.H.

Referenced by build(), debug_snapshot(), query(), query_impl(), query_point(), query_point_impl(), and root_bbox().

◆ root_

size_t Aleph::AABBTree::root_ = NONE

private

Definition at line 12274 of file geom_algorithms.H.

Referenced by build(), debug_snapshot(), query(), query_point(), and root_bbox().

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

geom_algorithms.H

Classes

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Construction

Complexity

Constructor & Destructor Documentation

◆ AABBTree()

Member Function Documentation

◆ box_contains_point()

◆ boxes_overlap()

◆ build() [1/2]

◆ build() [2/2]

◆ center_coord()

◆ debug_snapshot()

◆ insertion_sort_by_center()

◆ is_empty()

◆ query()

◆ query_impl()

◆ query_point()

◆ query_point_impl()

◆ root_bbox()

◆ select_kth_by_center()

◆ size()

◆ union_bbox()

Member Data Documentation

◆ entries_

◆ nodes_

◆ NONE

◆ root_