Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
QuadTree Class Reference

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

#include <quadtree.H>

Collaboration diagram for QuadTree:
[legend]

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)
 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.
 
void clear ()
 Alias for empty().
 
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.
 

Static Private Member Functions

static Node * make_root (const Geom_Number &min_x, const Geom_Number &max_x, const Geom_Number &min_y, const Geom_Number &max_y, const size_t capacity)
 Validate constructor arguments and allocate the root node.
 
static bool contains_only (Node *node, const Point &p)
 Return true when every point stored in a leaf equals p.
 
static bool has_four_leaf_children (Node *node) noexcept
 Return true when an internal node has four leaf children.
 
static size_t leaf_children_size (Node *node) noexcept
 Return the number of points directly stored in four leaf children.
 

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 |
| | |
+-------------------+
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
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';
});
LEVEL
#define LEVEL(p)
Definition btreepic.C:373
Aleph::Point
Represents a point with rectangular coordinates in a 2D plane.
Definition point.H:221
QuadNode
Node for QuadTree spatial data structure.
Definition quadnode.H:94
QuadTree
QuadTree - Hierarchical spatial index for 2D points.
Definition quadtree.H:126
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 365 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_xMinimum X coordinate of the region
max_xMaximum X coordinate of the region
min_yMinimum Y coordinate of the region
max_yMaximum Y coordinate of the region
_max_num_points_per_nodeMaximum points per leaf before splitting (default: 1)
Exceptions
std::domain_errorif capacity is zero or bounds are invalid

Definition at line 380 of file quadtree.H.

◆ QuadTree() [3/4]

QuadTree::QuadTree ( const QuadTree &  tree)
inline

Copy constructor - creates a deep copy of the tree.

Parameters
treeTree to copy

Definition at line 394 of file quadtree.H.

References copy_tree(), and root.

◆ QuadTree() [4/4]

QuadTree::QuadTree ( QuadTree &&  tree)
inlinenoexcept

Move constructor - transfers ownership.

Parameters
treeTree to move from

Definition at line 404 of file quadtree.H.

◆ ~QuadTree()

QuadTree::~QuadTree ( )
inline

Destructor - frees all nodes.

Definition at line 445 of file quadtree.H.

References empty(), and root.

Member Function Documentation

◆ clear()

void QuadTree::clear ( )
inline

Alias for empty().

See empty() for behavior.

Definition at line 602 of file quadtree.H.

References empty().

Referenced by TEST(), and TEST().

◆ contains()

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

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

Parameters
pPoint to check
Returns
true if the point is within the tree's root region

Definition at line 487 of file quadtree.H.

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

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

◆ contains_only()

static bool QuadTree::contains_only ( Node *  node,
const Point &  p 
)
inlinestaticprivate

Return true when every point stored in a leaf equals p.

Definition at line 151 of file quadtree.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), QuadNode::get_points_set(), and QuadNode::is_leaf().

Referenced by insert().

◆ copy_tree()

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

Deep copy a tree structure.

Definition at line 330 of file quadtree.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), COLOR, copy_tree(), QuadNode::get_max_x(), QuadNode::get_max_y(), QuadNode::get_min_x(), QuadNode::get_min_y(), QuadNode::get_points_set(), LEVEL, NE_CHILD, NW_CHILD, PARENT, 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 589 of file quadtree.H.

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

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

◆ empty() [2/2]

void QuadTree::empty ( Node *&  r)
inlineprivatenoexcept

Recursively delete all nodes.

Definition at line 300 of file quadtree.H.

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

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

◆ 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 619 of file quadtree.H.

References Aleph::blossom_maximum_cardinality_matching(), 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
OpFunction object type with signature void(Node*)
Parameters
opOperation to apply

Definition at line 612 of file quadtree.H.

References Aleph::blossom_maximum_cardinality_matching(), 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 477 of file quadtree.H.

References max_num_points_per_node.

Referenced by TEST(), and TEST().

◆ get_root() [1/2]

const Node * QuadTree::get_root ( ) const
inlinenoexcept

Get the root node (const version).

Definition at line 457 of file quadtree.H.

References root.

◆ get_root() [2/2]

Node * QuadTree::get_root ( )
inlinenoexcept

Get the root node.

Definition at line 451 of file quadtree.H.

References root.

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

◆ has_four_leaf_children()

static bool QuadTree::has_four_leaf_children ( Node *  node)
inlinestaticprivatenoexcept

Return true when an internal node has four leaf children.

Definition at line 161 of file quadtree.H.

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

Referenced by leaf_children_size(), and remove().

◆ insert() [1/3]

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

Insert a point given by coordinates.

Parameters
xX coordinate
yY coordinate
Returns
Pointer to the inserted point, or nullptr if outside region

Definition at line 514 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
pPoint to insert
Returns
Pointer to the inserted point, or nullptr if outside region

Definition at line 500 of file quadtree.H.

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

◆ insert() [3/3]

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

Recursive insert helper.

Definition at line 281 of file quadtree.H.

References Aleph::blossom_maximum_cardinality_matching(), contains_only(), QuadNode::get_child_to(), insert(), max_num_points_per_node, r, and split().

Referenced by demo_basic_operations(), demo_collision_detection(), demo_geographic_points(), demo_performance(), demo_traversal(), demo_tree_structure(), insert(), insert(), insert(), RankTreeTest< Tree >::insert_all(), 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(), 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(), 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(), 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(), 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(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), test(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), test_map_tree(), and test_map_tree().

◆ 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
nodeInternal node whose children should be merged

Definition at line 234 of file quadtree.H.

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

Referenced by remove().

◆ leaf_children_size()

static size_t QuadTree::leaf_children_size ( Node *  node)
inlinestaticprivatenoexcept

Return the number of points directly stored in four leaf children.

Definition at line 171 of file quadtree.H.

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

Referenced by remove().

◆ make_root()

static Node * QuadTree::make_root ( const Geom_Number &  min_x,
const Geom_Number &  max_x,
const Geom_Number &  min_y,
const Geom_Number &  max_y,
const size_t  capacity 
)
inlinestaticprivate

Validate constructor arguments and allocate the root node.

Exceptions
std::domain_errorif capacity is zero or bounds are invalid.

Definition at line 140 of file quadtree.H.

References ah_domain_error_if.

◆ 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 316 of file quadtree.H.

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

◆ operator=() [1/2]

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

Copy assignment operator - creates a deep copy.

Parameters
treeTree to assign from
Returns
Reference to this

Definition at line 415 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
treeTree to move from
Returns
Reference to this

Definition at line 432 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
pPoint to remove

Definition at line 565 of file quadtree.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), QuadNode::contains(), QuadNode::get_child_to(), has_four_leaf_children(), QuadNode::is_leaf(), join(), leaf_children_size(), max_num_points_per_node, PARENT, QuadNode::remove_point(), and root.

Referenced by demo_basic_operations(), destroy_tree(), main(), RankTreeTest< Tree >::TearDown(), 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(), 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_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ search()

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

Search for a point in the tree.

Parameters
pPoint to search for
Returns
Pointer to the found point, or nullptr if not found

Definition at line 524 of file quadtree.H.

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

Referenced by demo_basic_operations(), demo_geographic_points(), 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(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), test(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ search_container_node()

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

Find the leaf node containing a point.

Parameters
pPoint to locate
Returns
Pointer to the leaf node containing the point, or nullptr if not found

Definition at line 542 of file quadtree.H.

References Aleph::blossom_maximum_cardinality_matching(), QuadNode::contains(), QuadNode::get_child_to(), QuadNode::is_leaf(), 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)
inline

Set the maximum points per leaf node.

Existing nodes are not immediately repartitioned.

Parameters
_max_num_points_per_nodeNew positive leaf capacity
Exceptions
std::domain_errorif the requested capacity is zero

Definition at line 469 of file quadtree.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), and max_num_points_per_node.

Referenced by TEST().

◆ 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
nodeLeaf node to split

Definition at line 187 of file quadtree.H.

References QuadNode::add_point(), Aleph::blossom_maximum_cardinality_matching(), 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, 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: