QuadTree Class Reference

QuadTree - Hierarchical spatial index for 2D points. More...

#include <quadtree.H>

Collaboration diagram for QuadTree:

Public Types
using	Node = QuadNode

Public Member Functions
	QuadTree ()
	Default constructor - creates an uninitialized tree.
	QuadTree (const Geom_Number &min_x, const Geom_Number &max_x, const Geom_Number &min_y, const Geom_Number &max_y, const size_t &_max_num_points_per_node=1)
	Construct a quadtree with specified region and capacity.
	QuadTree (const QuadTree &tree)
	Copy constructor - creates a deep copy of the tree.
	QuadTree (QuadTree &&tree) noexcept
	Move constructor - transfers ownership.
QuadTree &	operator= (const QuadTree &tree)
	Copy assignment operator - creates a deep copy.
QuadTree &	operator= (QuadTree &&tree) noexcept
	Move assignment operator - transfers ownership.
	~QuadTree ()
	Destructor - frees all nodes.
Node *	get_root () noexcept
	Get the root node.
const Node *	get_root () const noexcept
	Get the root node (const version).
void	set_max_num_points_per_node (const size_t &_max_num_points_per_node) noexcept
	Set the maximum points per leaf node.
size_t	get_max_num_points_per_node () const noexcept
	Get the maximum points per leaf node.
bool	contains (const Point &p) const noexcept
	Check if a point is within the tree's region.
Point *	insert (const Point &p)
	Insert a point into the tree.
Point *	insert (const Geom_Number &x, const Geom_Number &y)
	Insert a point given by coordinates.
Point *	search (const Point &p) noexcept
	Search for a point in the tree.
Node *	search_container_node (const Point &p) noexcept
	Find the leaf node containing a point.
void	remove (const Point &p)
	Remove a point from the tree.
void	empty ()
	Remove all points from the tree, keeping only the root.
template<class Op >
void	for_each (Op &op)
	Apply an operation to each node in the tree.
template<class Op >
void	for_each (Op &&op=Op())
	Apply operation to each node (rvalue reference version).

Private Member Functions
void	split (Node *node)
	Subdivide a leaf node into four children.
void	join (Node *node)
	Merge four child nodes back into their parent.
Point *	insert (Node *&r, const Point &p)
	Recursive insert helper.
void	empty (Node *&r) noexcept
	Recursively delete all nodes.
template<class Op >
void	operate_on_nodes (Node *r, Op &op)
	Apply operation to all nodes in the tree.
void	copy_tree (QuadNode *src, QuadNode *&tgt, QuadNode *tgt_parent=nullptr)
	Deep copy a tree structure.

Private Attributes
Node *	root
	Root node of the tree.
size_t	max_num_points_per_node
	Maximum points per leaf node before splitting.

Detailed Description

QuadTree - Hierarchical spatial index for 2D points.

QuadTree is a tree data structure where each internal node has exactly four children corresponding to quadrants: NW, NE, SW, and SE. The tree adapts to point distribution by subdividing regions that exceed a specified point capacity.

Key Characteristics:

• Adaptive subdivision: Regions split only when exceeding capacity
• Hierarchical structure: Tree depth adapts to point distribution
• Efficient spatial queries: O(log n) for well-distributed data
• Automatic balancing: Merges empty quadrants after deletions

Spatial Decomposition:

Root Region
+-------------------+
|        |          |
|   NW   |    NE    |
+--------+----------+
|   SW   |    SE    |
|        |          |
+-------------------+

Complexity:

• Insert: O(log n) average, O(depth) worst
• Search: O(log n) average, O(depth) worst
• Remove: O(log n) average, O(depth) worst
• Range query: O(log n + k) where k is result size
• Space: O(n) for n points

Use Cases:

✓ Geographic information systems (GIS) ✓ Collision detection in games ✓ Image processing and compression ✓ Nearest neighbor searches ✓ Range queries (e.g., "find all points in rectangle")

Example:

// Create a quadtree for region [0, 100] × [0, 100]
// with max 4 points per node
QuadTree tree(0, 100, 0, 100, 4);
 
// Insert points
tree.insert(Point(25, 25));
tree.insert(Point(75, 75));
tree.insert(Point(25, 75));
tree.insert(Point(75, 25));
 
// Search for a point
Point * found = tree.search(Point(25, 25));
 
// Check if point is in the tree
if (tree.contains(Point(50, 50)))
  std::cout << "Point found" << '\n';
 
// Remove a point
tree.remove(Point(25, 25));
 
// Traverse all nodes
tree.for_each([](QuadNode * node) {
  std::cout << "Node at level " << LEVEL(node) << '\n';
});

Note

The tree automatically subdivides nodes when they exceed max_num_points_per_node and merges when they fall below it.

See also

QuadNode Node structure for the quadtree.

K2Tree Alternative 2D tree structure (kd-tree variant).

Author

Alejandro Mujica

Definition at line 125 of file quadtree.H.

Member Typedef Documentation

Node

using QuadTree::Node = QuadNode

Definition at line 128 of file quadtree.H.

Constructor & Destructor Documentation

QuadTree() [1/4]

QuadTree::QuadTree ( )

inline

Default constructor - creates an uninitialized tree.

Warning

You must call set_max_num_points_per_node() and ensure the root has proper bounds before using the tree.

Definition at line 312 of file quadtree.H.

QuadTree() [2/4]

QuadTree::QuadTree ( const Geom_Number &  min_x, const Geom_Number &  max_x, const Geom_Number &  min_y, const Geom_Number &  max_y, const size_t &  _max_num_points_per_node = 1  )

inline

Construct a quadtree with specified region and capacity.

Parameters

min_x	Minimum X coordinate of the region
max_x	Maximum X coordinate of the region
min_y	Minimum Y coordinate of the region
max_y	Maximum Y coordinate of the region
_max_num_points_per_node	Maximum points per leaf before splitting (default: 1)

Definition at line 326 of file quadtree.H.

QuadTree() [3/4]

QuadTree::QuadTree ( const QuadTree &  tree )

inline

Copy constructor - creates a deep copy of the tree.

Parameters

tree	Tree to copy

Definition at line 339 of file quadtree.H.

References copy_tree(), and root.

QuadTree() [4/4]

QuadTree::QuadTree ( QuadTree &&  tree )

inlinenoexcept

Move constructor - transfers ownership.

Parameters

tree	Tree to move from

Definition at line 349 of file quadtree.H.

~QuadTree()

QuadTree::~QuadTree ( )

inline

Destructor - frees all nodes.

Definition at line 390 of file quadtree.H.

References empty(), and root.

Member Function Documentation

contains()

bool QuadTree::contains ( const Point &  p ) const

inlinenoexcept

Check if a point is within the tree's region.

Parameters

p	Point to check

Returns

true if the point is within the tree's root region

Definition at line 424 of file quadtree.H.

References QuadNode::contains(), and root.

Referenced by demo_basic_operations(), demo_collision_detection(), demo_geographic_points(), demo_performance(), and TEST().

copy_tree()

void QuadTree::copy_tree ( QuadNode *  src, QuadNode *&  tgt, QuadNode *  tgt_parent = nullptr  )

inlineprivate

Deep copy a tree structure.

Definition at line 285 of file quadtree.H.

References COLOR, copy_tree(), QuadNode::get_max_x(), QuadNode::get_max_y(), QuadNode::get_min_x(), QuadNode::get_min_y(), QuadNode::get_points_set(), LEVEL, Aleph::maps(), NE_CHILD, NW_CHILD, SE_CHILD, and SW_CHILD.

Referenced by QuadTree(), copy_tree(), and operator=().

empty() [1/2]

void QuadTree::empty ( )

inline

Remove all points from the tree, keeping only the root.

Definition at line 525 of file quadtree.H.

References empty(), QuadNode::empty(), NE_CHILD, NW_CHILD, root, SE_CHILD, and SW_CHILD.

Referenced by ~QuadTree(), empty(), empty(), operator=(), and operator=().

empty() [2/2]

void QuadTree::empty ( Node *&  r )

inlineprivatenoexcept

Recursively delete all nodes.

Definition at line 255 of file quadtree.H.

References empty(), NE_CHILD, NW_CHILD, SE_CHILD, and SW_CHILD.

Referenced by TEST().

for_each() [1/2]

template<class Op >

void QuadTree::for_each ( Op &&  op = Op() )

inline

Apply operation to each node (rvalue reference version).

Definition at line 549 of file quadtree.H.

References Aleph::maps(), and root.

for_each() [2/2]

template<class Op >

void QuadTree::for_each ( Op &  op )

inline

Apply an operation to each node in the tree.

Performs preorder traversal, visiting internal nodes before their children.

Template Parameters

Op	Function object type with signature void(Node*)

Parameters

op	Operation to apply

Definition at line 542 of file quadtree.H.

References Aleph::maps(), and root.

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

get_max_num_points_per_node()

size_t QuadTree::get_max_num_points_per_node ( ) const

inlinenoexcept

Get the maximum points per leaf node.

Definition at line 414 of file quadtree.H.

References max_num_points_per_node.

Referenced by TEST().

get_root() [1/2]

const Node * QuadTree::get_root ( ) const

inlinenoexcept

Get the root node (const version).

Definition at line 402 of file quadtree.H.

References root.

get_root() [2/2]

Node * QuadTree::get_root ( )

inlinenoexcept

Get the root node.

Definition at line 396 of file quadtree.H.

References root.

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

insert() [1/3]

Point * QuadTree::insert ( const Geom_Number &  x, const Geom_Number &  y  )

inline

Insert a point given by coordinates.

Parameters

x	X coordinate
y	Y coordinate

Returns

Pointer to the inserted point, or nullptr if outside region

Definition at line 451 of file quadtree.H.

References insert(), and y.

insert() [2/3]

Point * QuadTree::insert ( const Point &  p )

inline

Insert a point into the tree.

If the point is outside the tree's region, insertion fails. If the point already exists, it will still be inserted (duplicates allowed).

Parameters

p	Point to insert

Returns

Pointer to the inserted point, or nullptr if outside region

Definition at line 437 of file quadtree.H.

References QuadNode::contains(), insert(), Aleph::maps(), and root.

insert() [3/3]

Point * QuadTree::insert ( Node *&  r, const Point &  p  )

inlineprivate

Recursive insert helper.

Definition at line 237 of file quadtree.H.

References QuadNode::add_point(), QuadNode::contains(), QuadNode::get_child_to(), QuadNode::get_num_points(), insert(), QuadNode::is_leaf(), Aleph::maps(), max_num_points_per_node, and split().

Referenced by demo_basic_operations(), demo_collision_detection(), demo_geographic_points(), demo_performance(), demo_traversal(), demo_tree_structure(), insert(), insert(), insert(), 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().

join()

void QuadTree::join ( Node *  node )

inlineprivate

Merge four child nodes back into their parent.

Deletes the four child nodes and transfers all their points to the parent node. Applies only to internal nodes whose children are all leaves.

Parameters

node	Internal node whose children should be merged

Definition at line 190 of file quadtree.H.

References Aleph::DynList< T >::append(), QuadNode::Black, COLOR, QuadNode::get_points_set(), Aleph::HTList::is_empty(), QuadNode::is_leaf(), Aleph::is_leaf(), Aleph::maps(), NE_CHILD, NW_CHILD, Aleph::DynList< T >::remove_first(), SE_CHILD, SW_CHILD, and QuadNode::White.

Referenced by remove().

operate_on_nodes()

template<class Op >

void QuadTree::operate_on_nodes ( Node *  r, Op &  op  )

inlineprivate

Apply operation to all nodes in the tree.

Definition at line 271 of file quadtree.H.

References Aleph::maps(), NE_CHILD, NW_CHILD, SE_CHILD, and SW_CHILD.

operator=() [1/2]

QuadTree & QuadTree::operator= ( const QuadTree &  tree )

inline

Copy assignment operator - creates a deep copy.

Parameters

tree	Tree to assign from

Returns

Reference to this

Definition at line 360 of file quadtree.H.

References copy_tree(), empty(), max_num_points_per_node, and root.

operator=() [2/2]

QuadTree & QuadTree::operator= ( QuadTree &&  tree )

inlinenoexcept

Move assignment operator - transfers ownership.

Parameters

tree	Tree to move from

Returns

Reference to this

Definition at line 377 of file quadtree.H.

References empty(), max_num_points_per_node, and root.

remove()

void QuadTree::remove ( const Point &  p )

inline

Remove a point from the tree.

Removes the point and potentially merges nodes if the total point count falls below the threshold.

Parameters

p	Point to remove

Definition at line 502 of file quadtree.H.

References QuadNode::get_child_to(), QuadNode::is_leaf(), join(), Aleph::maps(), max_num_points_per_node, NE_CHILD, NW_CHILD, PARENT, QuadNode::remove_point(), root, SE_CHILD, and SW_CHILD.

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

search()

Point * QuadTree::search ( const Point &  p )

inlinenoexcept

Search for a point in the tree.

Parameters

p	Point to search for

Returns

Pointer to the found point, or nullptr if not found

Definition at line 461 of file quadtree.H.

References QuadNode::contains(), QuadNode::get_child_to(), QuadNode::is_leaf(), Aleph::maps(), root, and QuadNode::search_point().

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

search_container_node()

Node * QuadTree::search_container_node ( const Point &  p )

inlinenoexcept

Find the leaf node containing a point.

Parameters

p	Point to locate

Returns

Pointer to the leaf node containing the point, or nullptr if not found

Definition at line 479 of file quadtree.H.

References QuadNode::contains(), QuadNode::get_child_to(), QuadNode::is_leaf(), Aleph::maps(), root, and QuadNode::search_point().

Referenced by TEST().

set_max_num_points_per_node()

void QuadTree::set_max_num_points_per_node ( const size_t &  _max_num_points_per_node )

inlinenoexcept

Set the maximum points per leaf node.

Definition at line 408 of file quadtree.H.

References Aleph::maps(), and max_num_points_per_node.

split()

void QuadTree::split ( Node *  node )

inlineprivate

Subdivide a leaf node into four children.

Creates four child nodes (NW, NE, SW, SE) and redistributes the node's points among them. Only applies to leaf nodes.

Parameters

node	Leaf node to split

Definition at line 143 of file quadtree.H.

References QuadNode::add_point(), COLOR, QuadNode::get_child_to(), QuadNode::get_max_x(), QuadNode::get_max_y(), QuadNode::get_mid_x(), QuadNode::get_mid_y(), QuadNode::get_min_x(), QuadNode::get_min_y(), QuadNode::get_points_set(), QuadNode::Gray, Aleph::HTList::is_empty(), QuadNode::is_leaf(), LEVEL, Aleph::maps(), NE_CHILD, NW_CHILD, Aleph::DynList< T >::remove_first(), SE_CHILD, and SW_CHILD.

Referenced by insert().

Member Data Documentation

max_num_points_per_node

size_t QuadTree::max_num_points_per_node

private

Maximum points per leaf node before splitting.

Definition at line 134 of file quadtree.H.

Referenced by get_max_num_points_per_node(), insert(), operator=(), operator=(), remove(), and set_max_num_points_per_node().

root

Node* QuadTree::root

private

Root node of the tree.

Definition at line 131 of file quadtree.H.

Referenced by QuadTree(), ~QuadTree(), contains(), empty(), for_each(), for_each(), get_root(), get_root(), insert(), operator=(), operator=(), remove(), search(), and search_container_node().

---

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

• quadtree.H