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

#include <tpl_2dtree.H>

Collaboration diagram for K2Tree< T >:

Classes
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 (const Point &__pmin, const 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

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.

Point *	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)
	Find all points within a rectangle.

Point	nearest (const Point &p) noexcept
	Find the nearest point to a query point.

	~K2Tree ()
	Destructor - frees all nodes.

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	lr_nearest (Node *root, const Point &p) noexcept
	Recursively find nearest neighbor (X-split level).

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

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.

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.

Node *	min_node
	Current nearest node (for nearest())

Geom_Number	min_dist2
	Current minimum squared distance.

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

K2Tree::root
Node * root
Root of the tree.
Definition tpl_2dtree.H:172

y
static mpfr_t y
Definition mpfr_mul_d.c:3

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:657

Aleph::maps
DynList< T > maps(const C &c, Op op)
Classic map operation.
Definition ahFunctional.H:693

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

Point 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:1423

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

K2Tree::nearest
Point nearest(const Point &p) noexcept
Find the nearest point to a query point.
Definition tpl_2dtree.H:523

Point
Rectangular point in the plane.
Definition point.H:156

Point::get_y
const Geom_Number & get_y() const
Returns y value.
Definition point.H:226

Point::get_x
const Geom_Number & get_x() const
Returns x value.
Definition point.H:221

Rectangle
Definition point.H:998

Template Parameters

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

Note: This implementation uses a memory pool for efficient node allocation.; The tree does NOT automatically balance. For sorted insertions, consider building from a shuffled sequence.

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

Author: Leandro Rabindranath León

Definition at line 131 of file tpl_2dtree.H.

Constructor & Destructor Documentation

◆ K2Tree() [1/4]

template<typename T = Empty_Class>

K2Tree< T >::K2Tree ( )

inline

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

Definition at line 176 of file tpl_2dtree.H.

◆ K2Tree() [2/4]

template<typename T = Empty_Class>

K2Tree< T >::K2Tree	(	const Point &	__pmin,
		const 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 186 of file tpl_2dtree.H.

◆ K2Tree() [3/4]

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 199 of file tpl_2dtree.H.

◆ K2Tree() [4/4]

template<typename T = Empty_Class>

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

delete

◆ ~K2Tree()

template<typename T = Empty_Class>

K2Tree< T >::~K2Tree ( )

inline

Destructor - frees all nodes.

Definition at line 551 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 285 of file tpl_2dtree.H.

References K2Tree< T >::Node::lb, K2Tree< T >::lr_insert(), Aleph::maps(), K2Tree< T >::root, K2Tree< T >::Node::rt, K2Tree< T >::Node::set_rect(), K2Tree< T >::Node::x(), K2Tree< T >::Node::xmax(), K2Tree< T >::Node::xmin(), K2Tree< T >::Node::y(), K2Tree< T >::Node::ymax(), and K2Tree< T >::Node::ymin().

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

◆ bu_nearest()

template<typename T = Empty_Class>

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

inlineprivatenoexcept

Recursively find nearest neighbor (Y-split level).

Parameters

root	Current node
p	Query point

Definition at line 489 of file tpl_2dtree.H.

References Rectangle::distance_squared_to(), K2Tree< T >::Node::lb, K2Tree< T >::lr_nearest(), K2Tree< T >::min_dist2, K2Tree< T >::min_node, K2Tree< T >::Node::point, K2Tree< T >::Node::rect, K2Tree< T >::root, K2Tree< T >::Node::rt, and K2Tree< T >::Node::y().

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 365 of file tpl_2dtree.H.

References K2Tree< T >::Node::lb, K2Tree< T >::lr_search(), K2Tree< T >::root, K2Tree< T >::Node::rt, K2Tree< T >::Node::x(), and K2Tree< T >::Node::y().

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

◆ contains()

template<typename T = Empty_Class>

bool K2Tree< T >::contains ( const Point & p ) const

inlinenoexcept

Check if the tree contains a point.

Definition at line 404 of file tpl_2dtree.H.

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

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

◆ destroy_tree()

template<typename T = Empty_Class>

void K2Tree< T >::destroy_tree ( Node * node )

inlineprivatenoexcept

Recursively delete all nodes.

Definition at line 539 of file tpl_2dtree.H.

References K2Tree< T >::destroy_tree().

Referenced by K2Tree< T >::~K2Tree(), and K2Tree< T >::destroy_tree().

◆ insert()

template<typename T = Empty_Class>

Point * K2Tree< T >::insert ( const Point & p )

inline

Insert a point into the tree.

The point is inserted only if it's not already present (no duplicates).

Parameters

p	Point to insert

Returns: Pointer to the inserted point, or nullptr if duplicate

Definition at line 343 of file tpl_2dtree.H.

References K2Tree< T >::lr_insert(), Aleph::maps(), K2Tree< T >::N, K2Tree< T >::pmax, K2Tree< T >::pmin, K2Tree< T >::Node::point, K2Tree< T >::root, and K2Tree< T >::Node::set_rect().

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(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ is_empty()

template<typename T = Empty_Class>

constexpr bool K2Tree< T >::is_empty ( ) const

inlineconstexprnoexcept

Check if the tree is empty.

Definition at line 211 of file tpl_2dtree.H.

References K2Tree< T >::N.

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

◆ lr_insert()

template<typename T = Empty_Class>

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

inlineprivate

Insert into tree with left-right (X) split.

Recursively inserts a point, splitting on X 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 225 of file tpl_2dtree.H.

References K2Tree< T >::bu_insert(), K2Tree< T >::Node::lb, Aleph::maps(), K2Tree< T >::root, K2Tree< T >::Node::rt, K2Tree< T >::Node::set_rect(), K2Tree< T >::Node::x(), K2Tree< T >::Node::xmax(), K2Tree< T >::Node::xmin(), K2Tree< T >::Node::y(), K2Tree< T >::Node::ymax(), and K2Tree< T >::Node::ymin().

Referenced by K2Tree< T >::bu_insert(), and K2Tree< T >::insert().

◆ lr_nearest()

template<typename T = Empty_Class>

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

inlineprivatenoexcept

Recursively find nearest neighbor (X-split level).

Parameters

root	Current node
p	Query point

Definition at line 458 of file tpl_2dtree.H.

References K2Tree< T >::bu_nearest(), Rectangle::distance_squared_to(), K2Tree< T >::Node::lb, K2Tree< T >::min_dist2, K2Tree< T >::min_node, K2Tree< T >::Node::point, K2Tree< T >::Node::rect, K2Tree< T >::root, K2Tree< T >::Node::rt, and K2Tree< T >::Node::x().

Referenced by K2Tree< T >::bu_nearest(), and K2Tree< T >::nearest().

◆ lr_search()

template<typename T = Empty_Class>

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

inlinestaticprivatenoexcept

Search with left-right (X) split pattern.

Definition at line 384 of file tpl_2dtree.H.

References K2Tree< T >::bu_search(), K2Tree< T >::Node::lb, K2Tree< T >::root, K2Tree< T >::Node::rt, K2Tree< T >::Node::x(), and K2Tree< T >::Node::y().

Referenced by K2Tree< T >::bu_search(), and K2Tree< T >::contains().

◆ nearest()

template<typename T = Empty_Class>

Point K2Tree< T >::nearest ( const Point & p )

inlinenoexcept

Find the nearest point to a query point.

Performs a nearest neighbor search using branch-and-bound pruning.

Parameters

p	Query point

Returns: The nearest point in the tree, or NullPoint if tree is empty

Definition at line 523 of file tpl_2dtree.H.

References K2Tree< T >::lr_nearest(), K2Tree< T >::min_dist2, K2Tree< T >::min_node, K2Tree< T >::N, NullPoint, K2Tree< T >::Node::point, and K2Tree< T >::root.

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

◆ operator=()

template<typename T = Empty_Class>

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

delete

◆ range() [1/2]

template<typename T = Empty_Class>

void K2Tree< T >::range	(	const Rectangle &	rect,
		DynList< Point > *	l
	)

inline

Find all points within a rectangle.

Performs a range query to find all points that lie within the specified rectangle.

Parameters

rect	Query rectangle
l	Output list where matching points are appended

Definition at line 441 of file tpl_2dtree.H.

References l, K2Tree< T >::N, K2Tree< T >::range(), and K2Tree< T >::root.

◆ range() [2/2]

template<typename T = Empty_Class>

static void K2Tree< T >::range	(	Node *	root,
		const Rectangle &	rect,
		DynList< Point > *	q
	)

inlinestaticprivate

Recursively find points within a rectangle.

Parameters

root	Current node
rect	Query rectangle
q	Output list for matching points

Definition at line 416 of file tpl_2dtree.H.

References Aleph::DynList< T >::append(), Rectangle::contains(), Rectangle::intersects(), K2Tree< T >::Node::lb, Aleph::maps(), K2Tree< T >::Node::point, K2Tree< T >::range(), K2Tree< T >::Node::rect, K2Tree< T >::root, and K2Tree< T >::Node::rt.

Referenced by main(), K2Tree< T >::range(), K2Tree< T >::range(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ size()

template<typename T = Empty_Class>

constexpr size_t K2Tree< T >::size ( ) const

inlineconstexprnoexcept

Get the number of points in the tree.

Definition at line 214 of file tpl_2dtree.H.

References K2Tree< T >::N.

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

Member Data Documentation

◆ min_dist2

template<typename T = Empty_Class>

Geom_Number K2Tree< T >::min_dist2

private

Current minimum squared distance.

Definition at line 451 of file tpl_2dtree.H.

Referenced by K2Tree< T >::bu_nearest(), K2Tree< T >::lr_nearest(), and K2Tree< T >::nearest().

◆ min_node

template<typename T = Empty_Class>

Node* K2Tree< T >::min_node

private

Current nearest node (for nearest())

Definition at line 450 of file tpl_2dtree.H.

Referenced by K2Tree< T >::bu_nearest(), K2Tree< T >::lr_nearest(), and K2Tree< T >::nearest().

◆ N

template<typename T = Empty_Class>

size_t K2Tree< T >::N

private

Number of points in the tree.

Definition at line 171 of file tpl_2dtree.H.

Referenced by K2Tree< T >::insert(), K2Tree< T >::is_empty(), K2Tree< T >::nearest(), K2Tree< T >::range(), and K2Tree< T >::size().

◆ pmax

template<typename T = Empty_Class>

Point K2Tree< T >::pmax

private

Upper-right corner of reference rectangle.

Definition at line 170 of file tpl_2dtree.H.

Referenced by K2Tree< T >::insert(), and K2Tree< T >::Node::set_rect().

◆ pmin

template<typename T = Empty_Class>

Point K2Tree< T >::pmin

private

Lower-left corner of reference rectangle.

Definition at line 169 of file tpl_2dtree.H.

Referenced by K2Tree< T >::insert(), and K2Tree< T >::Node::set_rect().

◆ root

template<typename T = Empty_Class>

Node* K2Tree< T >::root

private

Root of the tree.

Definition at line 172 of file tpl_2dtree.H.

Referenced by K2Tree< T >::~K2Tree(), K2Tree< T >::bu_insert(), K2Tree< T >::bu_nearest(), K2Tree< T >::bu_search(), K2Tree< T >::contains(), K2Tree< T >::insert(), K2Tree< T >::lr_insert(), K2Tree< T >::lr_nearest(), K2Tree< T >::lr_search(), K2Tree< T >::nearest(), K2Tree< T >::range(), and K2Tree< T >::range().

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

tpl_2dtree.H

Classes

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ K2Tree() [1/4]

◆ K2Tree() [2/4]

◆ K2Tree() [3/4]

◆ K2Tree() [4/4]

◆ ~K2Tree()

Member Function Documentation

◆ bu_insert()

◆ bu_nearest()

◆ bu_search()

◆ contains()

◆ destroy_tree()

◆ insert()

◆ is_empty()

◆ lr_insert()

◆ lr_nearest()

◆ lr_search()

◆ nearest()

◆ operator=()

◆ range() [1/2]

◆ range() [2/2]

◆ size()

Member Data Documentation

◆ min_dist2

◆ min_node

◆ N

◆ pmax

◆ pmin

◆ root