Node for QuadTree spatial data structure. More...

#include <quadnode.H>

Collaboration diagram for QuadNode:

Public Types
enum class	Color { White , Gray , Black , Num_Colors }
	Node color states for quadtree nodes. More...

enum class	Quad { NW , NE , SW , SE , Num_Quads }
	Quadrant directions for child nodes. More...

enum class	Side { North , South , East , West , Num_Sides }
	Cardinal directions for neighbor navigation. More...

Public Member Functions
	QuadNode () noexcept
	Default constructor - creates a white (empty) node.

	QuadNode (const Geom_Number &_min_x, const Geom_Number &_max_x, const Geom_Number &_min_y, const Geom_Number &_max_y, QuadNode *_parent=nullptr) noexcept
	Construct a node with specified region bounds.

	QuadNode (const QuadNode &)=delete

void	set_region (const Geom_Number &_min_x, const Geom_Number &_max_x, const Geom_Number &_min_y, const Geom_Number &_max_y) noexcept
	Set the region boundaries for this node.

QuadNode *&	get_parent () noexcept
	Get reference to parent node (for reading/writing via PARENT macro).

QuadNode *&	get_nw_child () noexcept
	Get reference to NW child (for reading/writing via NW_CHILD macro).

QuadNode *&	get_ne_child () noexcept
	Get reference to NE child (for reading/writing via NE_CHILD macro).

QuadNode *&	get_sw_child () noexcept
	Get reference to SW child (for reading/writing via SW_CHILD macro).

QuadNode *&	get_se_child () noexcept
	Get reference to SE child (for reading/writing via SE_CHILD macro).

Color &	get_color () noexcept
	Get reference to color (for reading/writing via COLOR macro).

unsigned long &	get_level () noexcept
	Get reference to level (for reading/writing via LEVEL macro).

bool	is_leaf () const noexcept
	Check if this node is a leaf (has no children).

bool	is_nw_child () const noexcept
	Check if this node is the NW child of its parent.

bool	is_ne_child () const noexcept
	Check if this node is the NE child of its parent.

bool	is_sw_child () const noexcept
	Check if this node is the SW child of its parent.

bool	is_se_child () const noexcept
	Check if this node is the SE child of its parent.

bool	contains (const Point &p) const noexcept
	Check if a point is contained in this node's region.

QuadNode *	get_child_to (const Point &p) const
	Find which child node should contain a given point.

Point &	add_point (const Point &p)
	Add a point to this node.

size_t	get_num_points () noexcept
	Get total number of points in this subtree.

const Geom_Number &	get_min_x () const noexcept
	Get minimum X coordinate of this region.

const Geom_Number &	get_max_x () const noexcept
	Get maximum X coordinate of this region.

const Geom_Number &	get_min_y () const noexcept
	Get minimum Y coordinate of this region.

const Geom_Number &	get_max_y () const noexcept
	Get maximum Y coordinate of this region.

Geom_Number	get_width () const noexcept
	Get width of this region.

Geom_Number	get_height () const noexcept
	Get height of this region.

Geom_Number	get_mid_x () const noexcept
	Get midpoint X coordinate.

Geom_Number	get_mid_y () const noexcept
	Get midpoint Y coordinate.

Point *	search_point (const Point &p) noexcept
	Search for a point in this node.

bool	remove_point (const Point &p)
	Remove a point from this node.

void	empty () noexcept
	Remove all points from this node and mark it as White.

DynList< QuadNode * >	get_neighbors ()
	Find all adjacent leaf nodes.

DynList< Point > &	get_points_set () noexcept
	Get reference to the points list (for direct manipulation).

template<class Op >
void	for_each_point (Op &op)
	Apply operation to each point in this node.

template<class Op >
void	for_each_point (Op &&op=Op())
	Apply operation to each point (rvalue reference version).

QuadNode &	operator= (const QuadNode &)=delete

Static Private Member Functions
static QuadNode *	get_north_neighbor (QuadNode *v) noexcept
	Find the northern neighbor of a node.

static QuadNode *	get_south_neighbor (QuadNode *v) noexcept
	Find the southern neighbor of a node.

static QuadNode *	get_east_neighbor (QuadNode *v) noexcept
	Find the eastern neighbor of a node.

static QuadNode *	get_west_neighbor (QuadNode *v) noexcept
	Find the western neighbor of a node.

static void	get_neighbors_by_side (QuadNode node, const Side &side, DynList< QuadNode > &neighbors)
	Recursively collect leaf neighbors on a given side.

static size_t	count_points (QuadNode *node) noexcept
	Recursively count all points in a subtree.

Private Attributes
DynList< Point >	points
	Points stored in this node (only for leaves)

QuadNode *	parent
	Parent node (nullptr for root)

QuadNode *	nw_child
	Northwest child.

QuadNode *	ne_child
	Northeast child.

QuadNode *	sw_child
	Southwest child.

QuadNode *	se_child
	Southeast child.

Color	color
	Node state (White/Gray/Black)

unsigned long	level
	Depth in the tree (0 for root)

Geom_Number	min_x
	Minimum X coordinate.

Geom_Number	max_x
	Maximum X coordinate.

Geom_Number	min_y
	Minimum Y coordinate.

Geom_Number	max_y
	Maximum Y coordinate.

Detailed Description

Node for QuadTree spatial data structure.

QuadNode represents a rectangular region in 2D space that can be recursively subdivided into four quadrants (northwest, northeast, southwest, southeast). Each node can store multiple points and maintains pointers to its parent and four potential children.

Node States (Colors):

White: Leaf node with no points (empty)
Black: Leaf node with at least one point
Gray: Internal node (has children)

Spatial Subdivision:: When a leaf node exceeds its point capacity, it splits into four children:
+-------+-------+

| NW | NE |

+-------+-------+

| SW | SE |

+-------+-------+

QuadNode::Quad::SW
@ SW
Southwest quadrant.

QuadNode::Quad::NW
@ NW
Northwest quadrant.

QuadNode::Quad::NE
@ NE
Northeast quadrant.

QuadNode::Quad::SE
@ SE
Southeast quadrant.

Complexity:

Point insertion: O(log n) expected (depends on tree depth)
Point search: O(log n) expected
Point removal: O(log n) expected
Neighbor finding: O(log n)
Space: O(n) for n points

Author: Alejandro Mujica

Definition at line 93 of file quadnode.H.

Member Enumeration Documentation

◆ Color

enum class QuadNode::Color

strong

Node color states for quadtree nodes.

Colors indicate the state of a node:

White: Leaf node with no points (empty region)
Black: Leaf node containing at least one point
Gray: Internal node (non-leaf, has children)

Enumerator
White	Empty leaf node.
Gray	Internal node with children.
Black	Leaf node with points.
Num_Colors

Definition at line 104 of file quadnode.H.

◆ Quad

enum class QuadNode::Quad

strong

Quadrant directions for child nodes.

Identifies which quadrant a child node occupies:

NW: Northwest (top-left)
NE: Northeast (top-right)
SW: Southwest (bottom-left)
SE: Southeast (bottom-right)

Enumerator
NW	Northwest quadrant.
NE	Northeast quadrant.
SW	Southwest quadrant.
SE	Southeast quadrant.
Num_Quads

Definition at line 120 of file quadnode.H.

◆ Side

enum class QuadNode::Side

strong

Cardinal directions for neighbor navigation.

Used to identify neighbors in four cardinal directions.

Enumerator
North	Northern neighbor.
South	Southern neighbor.
East	Eastern neighbor.
West	Western neighbor.
Num_Sides

Definition at line 133 of file quadnode.H.

Constructor & Destructor Documentation

◆ QuadNode() [1/3]

QuadNode::QuadNode ( )

inlinenoexcept

Default constructor - creates a white (empty) node.

Definition at line 307 of file quadnode.H.

◆ QuadNode() [2/3]

QuadNode::QuadNode	(	const Geom_Number &	_min_x,
		const Geom_Number &	_max_x,
		const Geom_Number &	_min_y,
		const Geom_Number &	_max_y,
		QuadNode *	_parent = `nullptr`
	)

inlinenoexcept

Construct a node with specified region bounds.

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
_parent	Parent node (nullptr for root)

Definition at line 323 of file quadnode.H.

◆ QuadNode() [3/3]

QuadNode::QuadNode ( const QuadNode & )

delete

Member Function Documentation

◆ add_point()

Point & QuadNode::add_point ( const Point & p )

inline

Add a point to this node.

Appends the point to the node's point list and marks it as Black. Should only be called on leaf nodes.

Parameters

p	The point to add

Returns: Reference to the added point

Definition at line 465 of file quadnode.H.

References Aleph::DynList< T >::append(), color, and points.

Referenced by QuadTree::insert(), and QuadTree::split().

◆ contains()

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

inlinenoexcept

Check if a point is contained in this node's region.

A point is contained if min_x <= x < max_x and min_y <= y < max_y. Note: Upper bounds are exclusive.

Parameters

p	The point to test

Returns: true if the point is within the region

Definition at line 417 of file quadnode.H.

References Aleph::maps(), max_x, max_y, min_x, and min_y.

Referenced by QuadTree::contains(), get_child_to(), QuadTree::insert(), QuadTree::insert(), QuadTree::search(), and QuadTree::search_container_node().

◆ count_points()

static size_t QuadNode::count_points ( QuadNode * node )

inlinestaticprivatenoexcept

Recursively count all points in a subtree.

Definition at line 286 of file quadnode.H.

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

Referenced by count_points(), and get_num_points().

◆ empty()

void QuadNode::empty ( )

inlinenoexcept

Remove all points from this node and mark it as White.

Definition at line 539 of file quadnode.H.

References color, Aleph::DynList< T >::empty(), and points.

Referenced by QuadTree::empty().

◆ for_each_point() [1/2]

template<class Op >

void QuadNode::for_each_point ( Op && op = Op() )

inline

Apply operation to each point (rvalue reference version).

Definition at line 588 of file quadnode.H.

References Aleph::maps().

◆ for_each_point() [2/2]

template<class Op >

void QuadNode::for_each_point ( Op & op )

inline

Apply operation to each point in this node.

Template Parameters

Op	Function object type with signature void(Point&)

Parameters

op	Operation to apply

Definition at line 580 of file quadnode.H.

References points.

◆ get_child_to()

QuadNode * QuadNode::get_child_to ( const Point & p ) const

inline

Find which child node should contain a given point.

Requires that this node is not a leaf and that the point is within this node's region.

Parameters

p	Point to locate

Returns: Pointer to the child node that contains p

Exceptions

std::domain_error if this node doesn't contain p

Definition at line 432 of file quadnode.H.

References ah_domain_error_if, contains(), Aleph::maps(), ne_child, nw_child, se_child, and sw_child.

Referenced by QuadTree::insert(), QuadTree::remove(), QuadTree::search(), QuadTree::search_container_node(), and QuadTree::split().

◆ get_color()

Color & QuadNode::get_color ( )

inlinenoexcept

Get reference to color (for reading/writing via COLOR macro).

Definition at line 369 of file quadnode.H.

References color.

◆ get_east_neighbor()

static QuadNode * QuadNode::get_east_neighbor ( QuadNode * v )

inlinestaticprivatenoexcept

Find the eastern neighbor of a node.

Definition at line 205 of file quadnode.H.

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

Referenced by get_east_neighbor(), and get_neighbors().

◆ get_height()

Geom_Number QuadNode::get_height ( ) const

inlinenoexcept

Get height of this region.

Definition at line 493 of file quadnode.H.

References max_y, and min_y.

◆ get_level()

unsigned long & QuadNode::get_level ( )

inlinenoexcept

Get reference to level (for reading/writing via LEVEL macro).

Definition at line 372 of file quadnode.H.

References level.

◆ get_max_x()

const Geom_Number & QuadNode::get_max_x ( ) const

inlinenoexcept

Get maximum X coordinate of this region.

Definition at line 481 of file quadnode.H.

References max_x.

Referenced by QuadTree::copy_tree(), and QuadTree::split().

◆ get_max_y()

const Geom_Number & QuadNode::get_max_y ( ) const

inlinenoexcept

Get maximum Y coordinate of this region.

Definition at line 487 of file quadnode.H.

References max_y.

Referenced by QuadTree::copy_tree(), and QuadTree::split().

◆ get_mid_x()

Geom_Number QuadNode::get_mid_x ( ) const

inlinenoexcept

Get midpoint X coordinate.

Definition at line 496 of file quadnode.H.

References max_x, and min_x.

Referenced by QuadTree::split().

◆ get_mid_y()

Geom_Number QuadNode::get_mid_y ( ) const

inlinenoexcept

Get midpoint Y coordinate.

Definition at line 499 of file quadnode.H.

References max_y, and min_y.

Referenced by QuadTree::split().

◆ get_min_x()

const Geom_Number & QuadNode::get_min_x ( ) const

inlinenoexcept

Get minimum X coordinate of this region.

Definition at line 478 of file quadnode.H.

References min_x.

Referenced by QuadTree::copy_tree(), and QuadTree::split().

◆ get_min_y()

const Geom_Number & QuadNode::get_min_y ( ) const

inlinenoexcept

Get minimum Y coordinate of this region.

Definition at line 484 of file quadnode.H.

References min_y.

Referenced by QuadTree::copy_tree(), and QuadTree::split().

◆ get_ne_child()

QuadNode *& QuadNode::get_ne_child ( )

inlinenoexcept

Get reference to NE child (for reading/writing via NE_CHILD macro).

Definition at line 360 of file quadnode.H.

References ne_child.

◆ get_neighbors()

DynList< QuadNode * > QuadNode::get_neighbors ( )

inline

Find all adjacent leaf nodes.

Searches in all four cardinal directions and returns neighboring leaf nodes. Internal nodes are traversed to find their adjacent leaves.

Returns: List of pointers to neighboring leaf nodes

Definition at line 552 of file quadnode.H.

References East, get_east_neighbor(), get_neighbors_by_side(), get_north_neighbor(), get_south_neighbor(), get_west_neighbor(), Aleph::maps(), North, South, and West.

◆ get_neighbors_by_side()

static void QuadNode::get_neighbors_by_side	(	QuadNode *	node,
		const Side &	side,
		DynList< QuadNode * > &	neighbors
	)

inlinestaticprivate

Recursively collect leaf neighbors on a given side.

Definition at line 249 of file quadnode.H.

References ah_domain_error_if, Aleph::DynList< T >::append(), East, get_neighbors_by_side(), is_leaf(), Aleph::maps(), NE_CHILD, North, NW_CHILD, SE_CHILD, South, SW_CHILD, and West.

Referenced by get_neighbors(), and get_neighbors_by_side().

◆ get_north_neighbor()

static QuadNode * QuadNode::get_north_neighbor ( QuadNode * v )

inlinestaticprivatenoexcept

Find the northern neighbor of a node.

Definition at line 161 of file quadnode.H.

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

Referenced by get_neighbors(), and get_north_neighbor().

◆ get_num_points()

size_t QuadNode::get_num_points ( )

inlinenoexcept

Get total number of points in this subtree.

Definition at line 472 of file quadnode.H.

References count_points().

Referenced by QuadTree::insert().

◆ get_nw_child()

QuadNode *& QuadNode::get_nw_child ( )

inlinenoexcept

Get reference to NW child (for reading/writing via NW_CHILD macro).

Definition at line 357 of file quadnode.H.

References nw_child.

◆ get_parent()

QuadNode *& QuadNode::get_parent ( )

inlinenoexcept

Get reference to parent node (for reading/writing via PARENT macro).

Definition at line 354 of file quadnode.H.

References parent.

◆ get_points_set()

DynList< Point > & QuadNode::get_points_set ( )

inlinenoexcept

Get reference to the points list (for direct manipulation).

Definition at line 572 of file quadnode.H.

References points.

Referenced by QuadTree::copy_tree(), demo_traversal(), QuadTree::join(), and QuadTree::split().

◆ get_se_child()

QuadNode *& QuadNode::get_se_child ( )

inlinenoexcept

Get reference to SE child (for reading/writing via SE_CHILD macro).

Definition at line 366 of file quadnode.H.

References se_child.

◆ get_south_neighbor()

static QuadNode * QuadNode::get_south_neighbor ( QuadNode * v )

inlinestaticprivatenoexcept

Find the southern neighbor of a node.

Definition at line 183 of file quadnode.H.

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

Referenced by get_neighbors(), and get_south_neighbor().

◆ get_sw_child()

QuadNode *& QuadNode::get_sw_child ( )

inlinenoexcept

Get reference to SW child (for reading/writing via SW_CHILD macro).

Definition at line 363 of file quadnode.H.

References sw_child.

◆ get_west_neighbor()

static QuadNode * QuadNode::get_west_neighbor ( QuadNode * v )

inlinestaticprivatenoexcept

Find the western neighbor of a node.

Definition at line 227 of file quadnode.H.

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

Referenced by get_neighbors(), and get_west_neighbor().

◆ get_width()

Geom_Number QuadNode::get_width ( ) const

inlinenoexcept

Get width of this region.

Definition at line 490 of file quadnode.H.

References max_x, and min_x.

◆ is_leaf()

bool QuadNode::is_leaf ( ) const

inlinenoexcept

Check if this node is a leaf (has no children).

Definition at line 375 of file quadnode.H.

References color.

Referenced by demo_traversal(), get_east_neighbor(), get_neighbors_by_side(), get_north_neighbor(), get_south_neighbor(), get_west_neighbor(), QuadTree::insert(), QuadTree::join(), QuadTree::remove(), QuadTree::search(), QuadTree::search_container_node(), QuadTree::split(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ is_ne_child()

bool QuadNode::is_ne_child ( ) const

inlinenoexcept

Check if this node is the NE child of its parent.

Definition at line 386 of file quadnode.H.

References NE_CHILD, and parent.

◆ is_nw_child()

bool QuadNode::is_nw_child ( ) const

inlinenoexcept

Check if this node is the NW child of its parent.

Definition at line 378 of file quadnode.H.

References NW_CHILD, and parent.

◆ is_se_child()

bool QuadNode::is_se_child ( ) const

inlinenoexcept

Check if this node is the SE child of its parent.

Definition at line 402 of file quadnode.H.

References parent, and SE_CHILD.

◆ is_sw_child()

bool QuadNode::is_sw_child ( ) const

inlinenoexcept

Check if this node is the SW child of its parent.

Definition at line 394 of file quadnode.H.

References parent, and SW_CHILD.

◆ operator=()

QuadNode & QuadNode::operator= ( const QuadNode & )

delete

◆ remove_point()

bool QuadNode::remove_point ( const Point & p )

inline

Remove a point from this node.

Parameters

p	Point to remove

Returns: true if the point was found and removed, false otherwise

Definition at line 523 of file quadnode.H.

References points.

Referenced by QuadTree::remove().

◆ search_point()

Point * QuadNode::search_point ( const Point & p )

inlinenoexcept

Search for a point in this node.

Linear search through the node's point list.

Parameters

p	Point to search for

Returns: Pointer to the found point, or nullptr if not found

Definition at line 508 of file quadnode.H.

References points.

Referenced by QuadTree::search(), QuadTree::search_container_node(), and TEST().

◆ set_region()

void QuadNode::set_region	(	const Geom_Number &	_min_x,
		const Geom_Number &	_max_x,
		const Geom_Number &	_min_y,
		const Geom_Number &	_max_y
	)

inlinenoexcept

Set the region boundaries for this node.

Parameters

_min_x	Minimum X coordinate
_max_x	Maximum X coordinate
_min_y	Minimum Y coordinate
_max_y	Maximum Y coordinate

Definition at line 342 of file quadnode.H.

References Aleph::maps(), max_x, max_y, min_x, and min_y.

Member Data Documentation

◆ color

Color QuadNode::color

private

Node state (White/Gray/Black)

Definition at line 151 of file quadnode.H.

Referenced by add_point(), empty(), get_color(), and is_leaf().

◆ level

unsigned long QuadNode::level

private

Depth in the tree (0 for root)

Definition at line 152 of file quadnode.H.

Referenced by get_level().

◆ max_x

Geom_Number QuadNode::max_x

private

Maximum X coordinate.

Definition at line 156 of file quadnode.H.

Referenced by contains(), get_max_x(), get_mid_x(), get_width(), and set_region().

◆ max_y

Geom_Number QuadNode::max_y

private

Maximum Y coordinate.

Definition at line 158 of file quadnode.H.

Referenced by contains(), get_height(), get_max_y(), get_mid_y(), and set_region().

◆ min_x

Geom_Number QuadNode::min_x

private

Minimum X coordinate.

Definition at line 155 of file quadnode.H.

Referenced by contains(), get_mid_x(), get_min_x(), get_width(), and set_region().

◆ min_y

Geom_Number QuadNode::min_y

private

Minimum Y coordinate.

Definition at line 157 of file quadnode.H.

Referenced by contains(), get_height(), get_mid_y(), get_min_y(), and set_region().

◆ ne_child

QuadNode* QuadNode::ne_child

private

Northeast child.

Definition at line 147 of file quadnode.H.

Referenced by get_child_to(), and get_ne_child().

◆ nw_child

QuadNode* QuadNode::nw_child

private

Northwest child.

Definition at line 146 of file quadnode.H.

Referenced by get_child_to(), and get_nw_child().

◆ parent

QuadNode* QuadNode::parent

private

Parent node (nullptr for root)

Definition at line 145 of file quadnode.H.

Referenced by get_parent(), is_ne_child(), is_nw_child(), is_se_child(), and is_sw_child().

◆ points

DynList<Point> QuadNode::points

private

Points stored in this node (only for leaves)

Definition at line 143 of file quadnode.H.

Referenced by add_point(), empty(), for_each_point(), get_points_set(), remove_point(), and search_point().

◆ se_child

QuadNode* QuadNode::se_child

private

Southeast child.

Definition at line 149 of file quadnode.H.

Referenced by get_child_to(), and get_se_child().

◆ sw_child

QuadNode* QuadNode::sw_child

private

Southwest child.

Definition at line 148 of file quadnode.H.

Referenced by get_child_to(), and get_sw_child().

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

quadnode.H

Public Types

Public Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Enumeration Documentation

◆ Color

◆ Quad

◆ Side

Constructor & Destructor Documentation

◆ QuadNode() [1/3]

◆ QuadNode() [2/3]

◆ QuadNode() [3/3]

Member Function Documentation

◆ add_point()

◆ contains()

◆ count_points()

◆ empty()

◆ for_each_point() [1/2]

◆ for_each_point() [2/2]

◆ get_child_to()

◆ get_color()

◆ get_east_neighbor()

◆ get_height()

◆ get_level()

◆ get_max_x()

◆ get_max_y()

◆ get_mid_x()

◆ get_mid_y()

◆ get_min_x()

◆ get_min_y()

◆ get_ne_child()

◆ get_neighbors()

◆ get_neighbors_by_side()

◆ get_north_neighbor()

◆ get_num_points()

◆ get_nw_child()

◆ get_parent()

◆ get_points_set()

◆ get_se_child()

◆ get_south_neighbor()

◆ get_sw_child()

◆ get_west_neighbor()

◆ get_width()

◆ is_leaf()

◆ is_ne_child()

◆ is_nw_child()

◆ is_se_child()

◆ is_sw_child()

◆ operator=()

◆ remove_point()

◆ search_point()

◆ set_region()

Member Data Documentation

◆ color

◆ level

◆ max_x

◆ max_y

◆ min_x

◆ min_y

◆ ne_child

◆ nw_child

◆ parent

◆ points

◆ se_child

◆ sw_child