Static 2D range tree for orthogonal range queries. More...

#include <geom_algorithms.H>

Collaboration diagram for Aleph::RangeTree2D:

Classes
struct	DebugNode
	Represents a node in the range tree for debugging. More...

struct	DebugSnapshot
	A complete snapshot of the range tree for debugging. More...

struct	Node
	Internal node structure containing the y-sorted secondary array. More...

Public Member Functions
void	build (const DynList< Point > &points)
	Build the range tree from a point set.

DynList< Point >	query (const Geom_Number &xmin, const Geom_Number &xmax, const Geom_Number &ymin, const Geom_Number &ymax) const
	Query: return all points inside [xmin,xmax] × [ymin,ymax].

size_t	size () const noexcept

bool	is_empty () const noexcept

DebugSnapshot	debug_snapshot () const
	Return structural snapshot for visualization/debug.

Private Member Functions
size_t	lower_bound_x (const Geom_Number &xval) const
	Binary search: first index i in pts_ where pts_(i).get_x() >= xval.

size_t	upper_bound_x (const Geom_Number &xval) const
	Binary search: first index i in pts_ where pts_(i).get_x() > xval.

void	build_node (const size_t node, const size_t lo, const size_t hi)

void	query_range (const size_t node, const size_t lo, const size_t hi, const size_t qlo, const size_t qhi, const Geom_Number &ymin, const Geom_Number &ymax, DynList< Point > &out) const

Static Private Member Functions
static size_t	lower_bound_y (const Array< Point > &arr, const Geom_Number &ymin)
	Binary search: first index i in arr where arr(i).get_y() >= ymin.

static size_t	upper_bound_y (const Array< Point > &arr, const Geom_Number &ymax)
	Binary search: first index i in arr where arr(i).get_y() > ymax.

Private Attributes
Array< Point >	pts_
	points sorted by x (primary key)

Array< Node >	tree_
	implicit binary tree (1-indexed)

size_t	n_ = 0

bool	built_ = false

Detailed Description

Static 2D range tree for orthogonal range queries.

Supports axis-aligned rectangle queries: given [xmin,xmax] × [ymin,ymax], find all points inside.

Complexity

Build: O(n log n) time, O(n log n) space
Query: O(log² n + k) where k = output size

Example: Array<Point> pts;

pts.append(Point(0,0));

pts.append(Point(2,1));

pts.append(Point(3,3));

RangeTree2D rt;

rt.build(pts);

Array<Point> out;

rt.query(0, 0, 2, 2, out);

out
size_t size_t int32_t * out
Definition ca-c-api.h:120

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::Point
Represents a point with rectangular coordinates in a 2D plane.
Definition point.H:221

Aleph::RangeTree2D
Static 2D range tree for orthogonal range queries.
Definition geom_algorithms.H:8564

Aleph::RangeTree2D::build
void build(const DynList< Point > &points)
Build the range tree from a point set.
Definition geom_algorithms.H:8714

Aleph::blossom_maximum_cardinality_matching
size_t blossom_maximum_cardinality_matching(const GT &g, DynDlist< typename GT::Arc * > &matching, SA sa=SA())
Alias of compute_maximum_cardinality_general_matching().
Definition Blossom.H:466

Definition at line 8563 of file geom_algorithms.H.

Member Function Documentation

◆ build()

void Aleph::RangeTree2D::build ( const DynList< Point > & points )

inline

Build the range tree from a point set.

Definition at line 8714 of file geom_algorithms.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), build_node(), built_, Aleph::Point::get_x(), Aleph::Point::get_y(), Aleph::HTList::Iterator::has_curr(), n_, pts_, Aleph::quicksort_op(), and tree_.

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

◆ build_node()

void Aleph::RangeTree2D::build_node	(	const size_t	node,
		const size_t	lo,
		const size_t	hi
	)

inlineprivate

Definition at line 8654 of file geom_algorithms.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), build_node(), pts_, and tree_.

Referenced by build(), and build_node().

◆ debug_snapshot()

DebugSnapshot Aleph::RangeTree2D::debug_snapshot ( ) const

inline

Return structural snapshot for visualization/debug.

Definition at line 8772 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), built_, n_, pts_, tree_, and Aleph::RangeTree2D::DebugSnapshot::x_sorted_points.

Referenced by TEST_F(), TEST_F(), Aleph::visualize_range_tree(), and Aleph::visualize_range_tree_query().

◆ is_empty()

bool Aleph::RangeTree2D::is_empty ( ) const

inlinenoexcept

Definition at line 8766 of file geom_algorithms.H.

References n_.

Referenced by TEST_F().

◆ lower_bound_x()

size_t Aleph::RangeTree2D::lower_bound_x ( const Geom_Number & xval ) const

inlineprivate

Binary search: first index i in pts_ where pts_(i).get_x() >= xval.

Definition at line 8631 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), n_, and pts_.

Referenced by query().

◆ lower_bound_y()

static size_t Aleph::RangeTree2D::lower_bound_y	(	const Array< Point > &	arr,
		const Geom_Number &	ymin
	)

inlinestaticprivate

Binary search: first index i in arr where arr(i).get_y() >= ymin.

Definition at line 8607 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Array< T >::size().

Referenced by query_range().

◆ query()

DynList< Point > Aleph::RangeTree2D::query	(	const Geom_Number &	xmin,
		const Geom_Number &	xmax,
		const Geom_Number &	ymin,
		const Geom_Number &	ymax
	)		const

inline

Query: return all points inside [xmin,xmax] × [ymin,ymax].

Definition at line 8743 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), built_, lower_bound_x(), n_, out, query_range(), and upper_bound_x().

Referenced by TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and Aleph::visualize_range_tree_query().

◆ query_range()

void Aleph::RangeTree2D::query_range	(	const size_t	node,
		const size_t	lo,
		const size_t	hi,
		const size_t	qlo,
		const size_t	qhi,
		const Geom_Number &	ymin,
		const Geom_Number &	ymax,
		DynList< Point > &	out
	)		const

inlineprivate

Definition at line 8685 of file geom_algorithms.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), lower_bound_y(), out, query_range(), tree_, and upper_bound_y().

Referenced by query(), and query_range().

◆ size()

size_t Aleph::RangeTree2D::size ( ) const

inlinenoexcept

Definition at line 8761 of file geom_algorithms.H.

References n_.

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

◆ upper_bound_x()

size_t Aleph::RangeTree2D::upper_bound_x ( const Geom_Number & xval ) const

inlineprivate

Binary search: first index i in pts_ where pts_(i).get_x() > xval.

Definition at line 8643 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), n_, and pts_.

Referenced by query().

◆ upper_bound_y()

static size_t Aleph::RangeTree2D::upper_bound_y	(	const Array< Point > &	arr,
		const Geom_Number &	ymax
	)

inlinestaticprivate

Binary search: first index i in arr where arr(i).get_y() > ymax.

Definition at line 8619 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Array< T >::size().

Referenced by query_range().

Member Data Documentation

◆ built_

bool Aleph::RangeTree2D::built_ = false

private

Definition at line 8604 of file geom_algorithms.H.

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

◆ n_

size_t Aleph::RangeTree2D::n_ = 0

private

Definition at line 8603 of file geom_algorithms.H.

Referenced by build(), debug_snapshot(), is_empty(), lower_bound_x(), query(), size(), and upper_bound_x().

◆ pts_

Array<Point> Aleph::RangeTree2D::pts_

private

points sorted by x (primary key)

Definition at line 8601 of file geom_algorithms.H.

Referenced by build(), build_node(), debug_snapshot(), lower_bound_x(), and upper_bound_x().

◆ tree_

Array<Node> Aleph::RangeTree2D::tree_

private

implicit binary tree (1-indexed)

Definition at line 8602 of file geom_algorithms.H.

Referenced by build(), build_node(), debug_snapshot(), and query_range().

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

Detailed Description

Complexity

Member Function Documentation

◆ build()

◆ build_node()

◆ debug_snapshot()

◆ is_empty()

◆ lower_bound_x()

◆ lower_bound_y()

◆ query()

◆ query_range()

◆ size()

◆ upper_bound_x()

◆ upper_bound_y()

Member Data Documentation

◆ built_

◆ n_

◆ pts_

◆ tree_