Spatial point index for O(log n) nearest-neighbor queries. More...

#include <geom_algorithms.H>

Collaboration diagram for Aleph::KDTreePointSearch:

Classes
struct	DebugPartition
	Represents a spatial partition or leaf in the KD-tree. More...

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

Public Member Functions
	KDTreePointSearch (const Geom_Number &xmin, const Geom_Number &ymin, const Geom_Number &xmax, const Geom_Number &ymax)
	Construct an empty KD-tree for the given bounding region.

bool	insert (const Point &p)
	Insert a point. Returns true if inserted, false if duplicate.

bool	contains (const Point &p) const
	Check if a point exists in the tree.

std::optional< Point >	nearest (const Point &p) const
	Find the nearest neighbor to query point `p`.

void	range (const Geom_Number &xmin, const Geom_Number &ymin, const Geom_Number &xmax, const Geom_Number &ymax, DynList< Point > *out) const
	Collect all points inside the given rectangle.

size_t	size () const noexcept
	Return the number of points in the tree.

bool	is_empty () const noexcept
	Return true if the tree is empty.

template<typename Op >
void	for_each (Op &&op) const
	Apply an operation to every point (inorder traversal).

DebugSnapshot	debug_snapshot () const
	Build a deterministic geometric partition snapshot for visualization.

Static Public Member Functions
static KDTreePointSearch	build (const Array< Point > &points, const Geom_Number &xmin, const Geom_Number &ymin, const Geom_Number &xmax, const Geom_Number &ymax)
	Build a balanced KD-tree from a point array.

Static Private Member Functions
static bool	lexicographic_less (const Point &a, const Point &b)

static Array< Point >	unique_points (Array< Point > points)

Private Attributes
K2Tree	tree

Array< Point >	points_

Rectangle	bounds_

Detailed Description

Spatial point index for O(log n) nearest-neighbor queries.

This is a thin wrapper around K2Tree<> (see tpl_2dtree.H) that provides a convenient interface consistent with the other geometry algorithms in this file.

Complexity

Build (balanced): O(n log n)
Insert: O(log n) average, O(n) worst case
Nearest neighbor: O(log n) average, O(n) worst case
Range query: O(√n + k) where k is output size
Contains: O(log n) average

Example: Array<Point> pts;

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

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

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

auto kd = KDTreePointSearch::build(pts, 0, 0, 2, 2);

auto nn = kd.nearest(Point(1,1));

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

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

Aleph::KDTreePointSearch::build
static KDTreePointSearch build(const Array< Point > &points, const Geom_Number &xmin, const Geom_Number &ymin, const Geom_Number &xmax, const Geom_Number &ymax)
Build a balanced KD-tree from a point array.
Definition geom_algorithms.H:8180

Aleph::Point
Represents a point with rectangular coordinates in a 2D plane.
Definition point.H:229

Aleph::divide_and_conquer_partition_dp
Divide_Conquer_DP_Result< Cost > divide_and_conquer_partition_dp(const size_t groups, const size_t n, Transition_Cost_Fn transition_cost, const Cost inf=dp_optimization_detail::default_inf< Cost >())
Optimize partition DP using divide-and-conquer optimization.
Definition DP_Optimizations.H:133

Definition at line 8104 of file geom_algorithms.H.

Constructor & Destructor Documentation

◆ KDTreePointSearch()

Aleph::KDTreePointSearch::KDTreePointSearch	(	const Geom_Number &	xmin,
		const Geom_Number &	ymin,
		const Geom_Number &	xmax,
		const Geom_Number &	ymax
	)

inline

Construct an empty KD-tree for the given bounding region.

Parameters

xmin	Minimum x of bounding box.
ymin	Minimum y of bounding box.
xmax	Maximum x of bounding box.
ymax	Maximum y of bounding box.

Definition at line 8163 of file geom_algorithms.H.

Member Function Documentation

◆ build()

static KDTreePointSearch Aleph::KDTreePointSearch::build	(	const Array< Point > &	points,
		const Geom_Number &	xmin,
		const Geom_Number &	ymin,
		const Geom_Number &	xmax,
		const Geom_Number &	ymax
	)

inlinestatic

Build a balanced KD-tree from a point array.

Parameters

points	Input points (duplicates removed internally).
xmin	Minimum x of bounding box.
ymin	Minimum y of bounding box.
xmax	Maximum x of bounding box.
ymax	Maximum y of bounding box.

Returns: A balanced KDTreePointSearch.

Definition at line 8180 of file geom_algorithms.H.

References K2Tree< T >::build(), Aleph::divide_and_conquer_partition_dp(), and unique_points().

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

◆ contains()

bool Aleph::KDTreePointSearch::contains ( const Point & p ) const

inline

Check if a point exists in the tree.

Definition at line 8201 of file geom_algorithms.H.

References K2Tree< T >::contains(), and tree.

◆ debug_snapshot()

DebugSnapshot Aleph::KDTreePointSearch::debug_snapshot ( ) const

inline

Build a deterministic geometric partition snapshot for visualization.

The snapshot uses the current point set and alternates split axis by depth (x/y), producing a balanced partition tree suitable for didactic rendering.

Definition at line 8240 of file geom_algorithms.H.

References Aleph::KDTreePointSearch::DebugSnapshot::bounds, bounds_, Aleph::divide_and_conquer_partition_dp(), Aleph::Point::get_x(), Aleph::Point::get_y(), points_, Aleph::quicksort_op(), Aleph::KDTreePointSearch::DebugPartition::region, Aleph::Array< T >::reserve(), and Aleph::Array< T >::size().

◆ for_each()

template<typename Op >

void Aleph::KDTreePointSearch::for_each ( Op && op ) const

inline

Apply an operation to every point (inorder traversal).

Definition at line 8228 of file geom_algorithms.H.

References K2Tree< T >::for_each(), and tree.

◆ insert()

bool Aleph::KDTreePointSearch::insert ( const Point & p )

inline

Insert a point. Returns true if inserted, false if duplicate.

Definition at line 8192 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::insert(), points_, and tree.

◆ is_empty()

bool Aleph::KDTreePointSearch::is_empty ( ) const

inlinenoexcept

Return true if the tree is empty.

Definition at line 8224 of file geom_algorithms.H.

References K2Tree< T >::is_empty(), and tree.

◆ lexicographic_less()

static bool Aleph::KDTreePointSearch::lexicographic_less	(	const Point &	a,
		const Point &	b
	)

inlinestaticprivate

Definition at line 8110 of file geom_algorithms.H.

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

Referenced by unique_points().

◆ nearest()

std::optional< Point > Aleph::KDTreePointSearch::nearest ( const Point & p ) const

inline

Find the nearest neighbor to query point p.

Definition at line 8207 of file geom_algorithms.H.

References K2Tree< T >::nearest(), and tree.

◆ range()

void Aleph::KDTreePointSearch::range	(	const Geom_Number &	xmin,
		const Geom_Number &	ymin,
		const Geom_Number &	xmax,
		const Geom_Number &	ymax,
		DynList< Point > *	out
	)		const

inline

Collect all points inside the given rectangle.

Definition at line 8213 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), K2Tree< T >::range(), and tree.

◆ size()

size_t Aleph::KDTreePointSearch::size ( ) const

inlinenoexcept

Return the number of points in the tree.

Definition at line 8221 of file geom_algorithms.H.

References K2Tree< T >::size(), and tree.

◆ unique_points()

static Array< Point > Aleph::KDTreePointSearch::unique_points ( Array< Point > points )

inlinestaticprivate

Definition at line 8117 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), lexicographic_less(), Aleph::quicksort_op(), Aleph::Array< T >::reserve(), and Aleph::Array< T >::size().

Referenced by build().

Member Data Documentation

◆ bounds_

Rectangle Aleph::KDTreePointSearch::bounds_

private

Definition at line 8108 of file geom_algorithms.H.

Referenced by debug_snapshot().

◆ points_

Array<Point> Aleph::KDTreePointSearch::points_

private

Definition at line 8107 of file geom_algorithms.H.

Referenced by debug_snapshot(), and insert().

◆ tree

K2Tree Aleph::KDTreePointSearch::tree

private

Definition at line 8106 of file geom_algorithms.H.

Referenced by contains(), for_each(), insert(), is_empty(), nearest(), range(), and size().

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

geom_algorithms.H

Classes

Public Member Functions

Static Public Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Complexity

Constructor & Destructor Documentation

◆ KDTreePointSearch()

Member Function Documentation

◆ build()

◆ contains()

◆ debug_snapshot()

◆ for_each()

◆ insert()

◆ is_empty()

◆ lexicographic_less()

◆ nearest()

◆ range()

◆ size()

◆ unique_points()

Member Data Documentation

◆ bounds_

◆ points_

◆ tree