2D k-d tree for efficient spatial point operations. More...

#include <tpl_2dtree.H>

Collaboration diagram for K2Tree< T >:

Classes
struct	NearestState
	Thread-local state for nearest-neighbor recursion. More...

struct	Node
	Internal node structure for the k-d tree. More...

Public Member Functions
	K2Tree ()
	Default constructor - creates an empty tree with zero-sized region.

	K2Tree (Point pmin, Point pmax)
	Construct a k-d tree with specified bounding region.

	K2Tree (const Geom_Number &xmin, const Geom_Number &ymin, const Geom_Number &xmax, const Geom_Number &ymax)
	Construct a k-d tree with specified coordinate bounds.

	K2Tree (const K2Tree &)=delete

K2Tree &	operator= (const K2Tree &)=delete

	K2Tree (K2Tree &&other) noexcept
	Move constructor — transfers ownership of all nodes.

K2Tree &	operator= (K2Tree &&other) noexcept
	Move assignment operator — transfers ownership of all nodes.

constexpr bool	is_empty () const noexcept
	Check if the tree is empty.

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

bool	insert (const Point &p)
	Insert a point into the tree.

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

void	range (const Rectangle &rect, DynList< Point > *l) const
	Find all points within a rectangle.

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

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

	~K2Tree ()
	Destructor - frees all nodes.

Static Public Member Functions
static K2Tree	build (Array< Point > points, const Point &pmin, const Point &pmax)
	Build a balanced k-d tree from an array of points.

Private Member Functions
Node *	lr_insert (Node *root, const Point &p)
	Insert into tree with left-right (X) split.

Node *	bu_insert (Node *root, const Point &p)
	Insert into tree with bottom-up (Y) split.

void	destroy_tree (Node *node) noexcept
	Recursively delete all nodes.

Static Private Member Functions
static Node *	bu_search (Node *root, const Point &p) noexcept
	Search with bottom-up (Y) split pattern.

static Node *	lr_search (Node *root, const Point &p) noexcept
	Search with left-right (X) split pattern.

static void	range (Node root, const Rectangle &rect, DynList< Point > q)
	Recursively find points within a rectangle.

static void	lr_nearest (Node *root, const Point &p, NearestState &st) noexcept
	Recursively find the nearest neighbor (X-split level).

static void	bu_nearest (Node *root, const Point &p, NearestState &st) noexcept
	Recursively find the nearest neighbor (Y-split level).

static Node *	build_balanced (Array< Point > &pts, const size_t lo, const size_t hi, const bool split_x, const Point &rmin, const Point &rmax)
	Recursively build a balanced subtree selecting medians.

template<typename Op >
static void	for_each_node (const Node *node, Op &&op)
	Recursive inorder traversal helper for for_each.

Private Attributes
Point	pmin_
	Lower-left corner of reference rectangle.

Point	pmax_
	Upper-right corner of reference rectangle.

size_t	N_
	Number of points in the tree.

Node *	root_
	Root of the tree.

Detailed Description

template<typename T = Empty_Class>
class K2Tree< T >

2D k-d tree for efficient spatial point operations.

K2Tree is a binary space partitioning tree that recursively divides 2D space using alternating vertical (X) and horizontal (Y) splits. Each node represents a point and implicitly defines a rectangular region.

Key Characteristics:

Alternating splits: Even levels split on X, odd levels split on Y
Binary structure: Each node has at most two children (left/bottom, right/top)
Duplicate rejection: Duplicate points are not inserted
Balanced on random data: Expected O(log n) height for random insertions
Worst-case unbalanced: Can degenerate to O(n) on sorted data

Split Pattern:: Root (split on X):

x < root.x → Left subtree

x >= root.x → Right subtree

├─ Child (split on Y):

│ y < child.y → Bottom subtree

│ y >= child.y → Top subtree

└─ ...

Y
#define Y(p)
Definition btreepic.C:375

X
#define X(p)
Definition btreepic.C:374

root
__gmp_expr< T, __gmp_binary_expr< __gmp_expr< T, U >, unsigned long int, __gmp_root_function > > root(const __gmp_expr< T, U > &expr, unsigned long int l)
Definition gmpfrxx.h:4060

y
static mpfr_t y
Definition mpfr_mul_d.c:3

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

Aleph::split
std::vector< std::string > & split(const std::string &s, const char delim, std::vector< std::string > &elems)
Split a std::string by a single delimiter character.
Definition ah-string-utils.H:725

Complexity:

Insert: O(log n) average, O(n) worst case
Search: O(log n) average, O(n) worst case
Nearest neighbor: O(log n) average, O(n) worst case
Range query: O(sqrt(n) + k) where k is result size
Space: O(n)

Comparison with QuadTree:

K2Tree: Binary splits, simpler structure, better for uniformly distributed data
QuadTree: Quaternary splits, adapts to density, better for clustered data

Use Cases:: ✓ Nearest neighbor search ✓ Range queries (all points in rectangle) ✓ Spatial databases ✓ Computer graphics (ray tracing, collision detection) ✓ Geographic information systems (GIS)

Example:: // Create a k-d tree for region [0, 100] × [0, 100]

K2Tree<> tree(0, 0, 100, 100);

// Insert points

tree.insert(Point(25, 50));

tree.insert(Point(75, 25));

tree.insert(Point(50, 75));

// Check if point exists

if (tree.contains(Point(25, 50)))

std::cout << "Point found!" << '\n';

// Find nearest neighbor

if (auto nearest = tree.nearest(Point(30, 45)))

std::cout << "Nearest: (" << nearest->get_x() << ", "

<< nearest->get_y() << ")" << '\n';

// Range query

Rectangle rect(20, 20, 80, 80);

DynList<Point> points_in_rect;

tree.range(rect, &points_in_rect);

Aleph::DynList
Dynamic singly linked list with functional programming support.
Definition htlist.H:1155

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

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

K2Tree
2D k-d tree for efficient spatial point operations.
Definition tpl_2dtree.H:136

K2Tree::nearest
std::optional< Point > nearest(const Point &p) const noexcept
Find the nearest point to a query point.
Definition tpl_2dtree.H:557

Template Parameters

T	Optional user data type associated with points (default: Empty_Class)

Note: The tree does NOT automatically balance. For sorted insertions, use the static build() factory which selects medians to produce an O(log n)-height tree.

See also: QuadTree Alternative spatial structure with adaptive quadrant subdivision.

Author: Leandro Rabindranath León

Definition at line 135 of file tpl_2dtree.H.

Constructor & Destructor Documentation

◆ K2Tree() [1/5]

template<typename T = Empty_Class>

K2Tree< T >::K2Tree ( )

inline

Default constructor - creates an empty tree with zero-sized region.

Definition at line 180 of file tpl_2dtree.H.

◆ K2Tree() [2/5]

template<typename T = Empty_Class>

K2Tree< T >::K2Tree	(	Point	pmin,
		Point	pmax
	)

inline

Construct a k-d tree with specified bounding region.

Parameters

pmin	Lower-left corner of the region
pmax	Upper-right corner of the region

Definition at line 190 of file tpl_2dtree.H.

◆ K2Tree() [3/5]

template<typename T = Empty_Class>

K2Tree< T >::K2Tree	(	const Geom_Number &	xmin,
		const Geom_Number &	ymin,
		const Geom_Number &	xmax,
		const Geom_Number &	ymax
	)

inline

Construct a k-d tree with specified coordinate bounds.

Parameters

xmin	Minimum X coordinate
ymin	Minimum Y coordinate
xmax	Maximum X coordinate
ymax	Maximum Y coordinate

Definition at line 203 of file tpl_2dtree.H.

◆ K2Tree() [4/5]

template<typename T = Empty_Class>

K2Tree< T >::K2Tree ( const K2Tree< T > & )

delete

◆ K2Tree() [5/5]

template<typename T = Empty_Class>

K2Tree< T >::K2Tree ( K2Tree< T > && other )

inlinenoexcept

Move constructor — transfers ownership of all nodes.

Definition at line 215 of file tpl_2dtree.H.

References Aleph::divide_and_conquer_partition_dp().

◆ ~K2Tree()

template<typename T = Empty_Class>

K2Tree< T >::~K2Tree ( )

inline

Destructor - frees all nodes.

Definition at line 738 of file tpl_2dtree.H.

References K2Tree< T >::destroy_tree(), and K2Tree< T >::root_.

Member Function Documentation

◆ bu_insert()

template<typename T = Empty_Class>

Node * K2Tree< T >::bu_insert	(	Node *	root,
		const Point &	p
	)

inlineprivate

Insert into tree with bottom-up (Y) split.

Recursively inserts a point, splitting on Y coordinate at this level.

Parameters

root	Current node
p	Point to insert

Returns: New subtree root, or nullptr if point is duplicate

Definition at line 313 of file tpl_2dtree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Point::get_x(), Aleph::Point::get_y(), K2Tree< T >::lr_insert(), and root().

Referenced by K2Tree< T >::lr_insert().

◆ bu_nearest()

template<typename T = Empty_Class>

static void K2Tree< T >::bu_nearest	(	Node *	root,
		const Point &	p,
		NearestState &	st
	)

inlinestaticprivatenoexcept

Recursively find the nearest neighbor (Y-split level).

Parameters

root	Current node
p	Query point
st	Mutable search state

Definition at line 521 of file tpl_2dtree.H.

References K2Tree< T >::lr_nearest(), and root().

Referenced by K2Tree< T >::lr_nearest().

◆ bu_search()

template<typename T = Empty_Class>

static Node * K2Tree< T >::bu_search	(	Node *	root,
		const Point &	p
	)

inlinestaticprivatenoexcept

Search with bottom-up (Y) split pattern.

Definition at line 391 of file tpl_2dtree.H.

References K2Tree< T >::lr_search(), and root().

Referenced by K2Tree< T >::lr_search().

◆ build()

template<typename T = Empty_Class>

static K2Tree K2Tree< T >::build	(	Array< Point >	points,
		const Point &	pmin,
		const Point &	pmax
	)

inlinestatic

Build a balanced k-d tree from an array of points.

Constructs a balanced tree by recursively selecting medians, alternating between X and Y coordinates. This avoids the degeneration to O(n) height that occurs with sorted insertions.

Duplicate points are removed internally.

Parameters

points	Array of points (copied internally).
pmin	Lower-left corner of the bounding region.
pmax	Upper-right corner of the bounding region.

Returns: A balanced K2Tree containing all unique points.

Complexity:

Time: O(n log n)
Space: O(n)

Definition at line 599 of file tpl_2dtree.H.

References K2Tree< T >::build_balanced(), Aleph::Point::get_x(), Aleph::Point::get_y(), Aleph::in_place_sort(), Aleph::Array< T >::is_empty(), K2Tree< T >::N_, Aleph::pmax(), Aleph::pmin(), r, Aleph::Array< T >::remove_last(), K2Tree< T >::root_, Aleph::Array< T >::size(), and w.

Referenced by Aleph::KDTreePointSearch::build(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ build_balanced()

template<typename T = Empty_Class>

static Node * K2Tree< T >::build_balanced	(	Array< Point > &	pts,
		const size_t	lo,
		const size_t	hi,
		const bool	split_x,
		const Point &	rmin,
		const Point &	rmax
	)

inlinestaticprivate

Recursively build a balanced subtree selecting medians.

After nth_element, elements with the same splitting coordinate as the median are moved to the right partition so that lr_search/bu_search (which send equal-coord queries right) can find them.

Definition at line 639 of file tpl_2dtree.H.

References K2Tree< T >::build_balanced(), Aleph::divide_and_conquer_partition_dp(), Aleph::Point::get_x(), Aleph::Point::get_y(), K2Tree< T >::Node::lb_, K2Tree< T >::Node::rt_, K2Tree< T >::Node::set_rect(), K2Tree< T >::Node::x(), and K2Tree< T >::Node::y().

Referenced by K2Tree< T >::build(), and K2Tree< T >::build_balanced().