Quadtree spatial index for efficient range and intersection queries. More...

#include <quadtree.hpp>

Classes
struct	DetailedStatistics
	Get detailed tree statistics. More...
class	Iterator
	Iterator support for tree traversal. More...
struct	Statistics
	Get tree statistics for performance analysis. More...

Public Types
using	ObjectType = T
using	BoundingBoxFunc = std::function<geometry::Rectangle(const T&)>

Public Member Functions
	QuadTree (const geometry::Rectangle &boundary, BoundingBoxFunc get_bbox, size_t capacity=10, size_t max_depth=8)
	Constructor.
bool	insert (const T &object)
	Insert object into quadtree.
std::vector< T >	query_range (const geometry::Rectangle &range) const
	Query objects in rectangular range.
std::vector< T >	query_point (const geometry::Point &point) const
	Query objects containing a specific point.
std::vector< T >	query_nearby (const T &target, double distance) const
	Find objects within distance of target object.
std::vector< std::pair< T, T > >	find_potential_intersections () const
	Find all potentially intersecting pairs of objects.
std::vector< std::pair< T, T > >	find_intersections (std::function< bool(const T &, const T &)> collision_func) const
	Find intersecting objects using efficient spatial queries.
size_t	size () const
	Get total number of objects in tree.
bool	empty () const
	Check if tree is empty.
void	clear ()
	Clear all objects from tree.
Statistics	get_statistics () const
	Calculate tree statistics.
const QuadTreeNode< T > *	get_root () const
	Get root node (for visualization/debugging)
void	rebuild (size_t new_capacity, size_t new_max_depth)
	Rebuild tree with new parameters.
bool	remove (const T &object)
	Remove object from tree.
bool	update (const T &old_object, const T &new_object)
	Update object position (remove and re-insert)
size_t	batch_insert (const std::vector< T > &objects)
	Batch insert multiple objects efficiently.
size_t	batch_remove (const std::vector< T > &objects)
	Batch remove multiple objects efficiently.
Iterator	begin () const
	Get iterator to beginning of tree.
Iterator	end () const
	Get iterator to end of tree.
bool	contains (const T &object) const
	Check if object exists in tree.
std::vector< T >	get_all_objects () const
	Get all objects in tree as vector.
std::vector< T >	query_circle (const geometry::Point &center, double radius) const
	Get objects within circular range.
std::vector< T >	query_k_nearest (const T &target, size_t k) const
	Get k nearest neighbors to target object.
void	optimize ()
	Optimize tree structure for better performance This rebuilds the tree with better parameters based on current data.
DetailedStatistics	get_detailed_statistics () const
	Get detailed statistics about tree structure.
bool	merge (const QuadTree &other)
	Merge another quadtree into this one.
std::vector< std::unique_ptr< QuadTree > >	split_by_regions (const std::vector< geometry::Rectangle > &regions) const
	Split tree into multiple subtrees based on spatial regions.
bool	validate () const
	Validate tree structure integrity.
std::string	to_string () const
	Get tree as string representation (for debugging)
void	set_statistics_collection (bool enable)
	Enable/disable statistics collection.
double	get_load_factor () const
	Get current load factor of the tree.
	__init__ (self, Rectangle boundary, int capacity=10, int max_depth=8)
bool	insert (self, Any obj, Optional[Rectangle] bbox=None)
List[Any]	query_range (self, Rectangle range_bbox)
List[Any]	query_point (self, Point point)
List[Tuple[Any, Any]]	find_intersections (self)
List[Any]	find_nearby_objects (self, Any obj, float distance)
int	size (self)
None	clear (self)

Public Attributes
	root = QuadTreeNode(boundary, capacity, max_depth)
int	object_count = 0

Protected Member Functions
List[Tuple[Any, Rectangle]]	_get_all_object_bbox_pairs (self)
List[Tuple[Any, Rectangle]]	_collect_object_bbox_pairs (self, QuadTreeNode node)

Detailed Description

template<typename T>
class zlayout::spatial::QuadTree< T >

Quadtree spatial index for efficient range and intersection queries.

Quadtree spatial index for efficient range and intersection queries.

High-performance spatial data structure that partitions 2D space recursively into quadrants. Optimizes range queries, nearest neighbor searches, and intersection detection for large numbers of geometric objects.

Definition at line 120 of file quadtree.hpp.

Member Typedef Documentation

◆ BoundingBoxFunc

template<typename T>

using zlayout::spatial::QuadTree< T >::BoundingBoxFunc = std::function<geometry::Rectangle(const T&)>

Definition at line 123 of file quadtree.hpp.

◆ ObjectType

template<typename T>

using zlayout::spatial::QuadTree< T >::ObjectType = T

Definition at line 122 of file quadtree.hpp.

Constructor & Destructor Documentation

◆ QuadTree()

template<typename T>

zlayout::spatial::QuadTree< T >::QuadTree	(	const geometry::Rectangle &	boundary,
		BoundingBoxFunc	get_bbox,
		size_t	capacity = 10,
		size_t	max_depth = 8 )

Constructor.

Parameters

boundary	World boundary for the quadtree
get_bbox	Function to extract bounding box from objects
capacity	Maximum objects per node before subdivision
max_depth	Maximum subdivision depth

Definition at line 613 of file quadtree.hpp.

Here is the caller graph for this function:

◆ init()

zlayout.spatial.QuadTree< T >.__init__	(		self,
		Rectangle	boundary,
		int	capacity = 10,
		int	max_depth = 8 )

Definition at line 131 of file spatial.py.

Member Function Documentation

◆ _collect_object_bbox_pairs()

List[Tuple[Any, Rectangle]] zlayout.spatial.QuadTree< T >._collect_object_bbox_pairs	(		self,
		QuadTreeNode	node )

protected

Recursively collect all object-bbox pairs.

Definition at line 204 of file spatial.py.

Here is the caller graph for this function:

◆ _get_all_object_bbox_pairs()

List[Tuple[Any, Rectangle]] zlayout.spatial.QuadTree< T >._get_all_object_bbox_pairs ( self )

protected

Get all (object, bbox) pairs from the tree.

Definition at line 200 of file spatial.py.

Here is the caller graph for this function:

◆ batch_insert()

template<typename T>

size_t zlayout::spatial::QuadTree< T >::batch_insert ( const std::vector< T > & objects )

Batch insert multiple objects efficiently.

Parameters

objects Vector of objects to insert

Returns: Number of objects successfully inserted

Definition at line 744 of file quadtree.hpp.

◆ batch_remove()

template<typename T>

size_t zlayout::spatial::QuadTree< T >::batch_remove ( const std::vector< T > & objects )

Batch remove multiple objects efficiently.

Parameters

objects Vector of objects to remove

Returns: Number of objects successfully removed

Definition at line 758 of file quadtree.hpp.

◆ begin()

template<typename T>

QuadTree< T >::Iterator zlayout::spatial::QuadTree< T >::begin ( ) const

Get iterator to beginning of tree.

Definition at line 772 of file quadtree.hpp.

◆ clear() [1/2]

None zlayout.spatial.QuadTree< T >.clear ( self )

Remove all objects from the tree.

Definition at line 218 of file spatial.py.

◆ clear() [2/2]

template<typename T>

void zlayout::spatial::QuadTree< T >::clear ( )

Clear all objects from tree.

Definition at line 674 of file quadtree.hpp.

◆ contains()

template<typename T>

bool zlayout::spatial::QuadTree< T >::contains ( const T & object ) const

Check if object exists in tree.

Parameters

object Object to find

Returns: true if object exists

Definition at line 782 of file quadtree.hpp.

Here is the call graph for this function:

◆ empty()

template<typename T>

bool zlayout::spatial::QuadTree< T >::empty ( ) const

inline

Check if tree is empty.

Definition at line 198 of file quadtree.hpp.

◆ end()

template<typename T>

QuadTree< T >::Iterator zlayout::spatial::QuadTree< T >::end ( ) const

Get iterator to end of tree.

Definition at line 777 of file quadtree.hpp.

◆ find_intersections() [1/2]

List[Tuple[Any, Any]] zlayout.spatial.QuadTree< T >.find_intersections ( self )

Find all pairs of objects that potentially intersect.

Definition at line 164 of file spatial.py.

◆ find_intersections() [2/2]

template<typename T>

std::vector< std::pair< T, T > > zlayout::spatial::QuadTree< T >::find_intersections ( std::function< bool(const T &, const T &)> collision_func ) const

Find intersecting objects using efficient spatial queries.

Parameters

collision_func Function to test actual collision between objects

Returns: Vector of intersecting object pairs

Definition at line 666 of file quadtree.hpp.

◆ find_nearby_objects()

List[Any] zlayout.spatial.QuadTree< T >.find_nearby_objects	(		self,
		Any	obj,
		float	distance )

Find objects within a certain distance of the given object.

Definition at line 180 of file spatial.py.

◆ find_potential_intersections()

template<typename T>

std::vector< std::pair< T, T > > zlayout::spatial::QuadTree< T >::find_potential_intersections ( ) const

Find all potentially intersecting pairs of objects.

Returns: Vector of object pairs that might intersect

Definition at line 659 of file quadtree.hpp.

◆ get_all_objects()

template<typename T>

std::vector< T > zlayout::spatial::QuadTree< T >::get_all_objects ( ) const

Get all objects in tree as vector.

Returns: Vector containing all objects

Definition at line 789 of file quadtree.hpp.

◆ get_detailed_statistics()

template<typename T>

QuadTree< T >::DetailedStatistics zlayout::spatial::QuadTree< T >::get_detailed_statistics ( ) const

Get detailed statistics about tree structure.

Definition at line 884 of file quadtree.hpp.

Here is the caller graph for this function:

◆ get_load_factor()

template<typename T>

double zlayout::spatial::QuadTree< T >::get_load_factor ( ) const

Get current load factor of the tree.

Returns: Load factor (0.0 to 1.0)

Definition at line 982 of file quadtree.hpp.

Here is the call graph for this function:

◆ get_root()

template<typename T>

const QuadTreeNode< T > * zlayout::spatial::QuadTree< T >::get_root ( ) const

inline

Get root node (for visualization/debugging)

Definition at line 225 of file quadtree.hpp.

◆ get_statistics()

template<typename T>

QuadTree< T >::Statistics zlayout::spatial::QuadTree< T >::get_statistics ( ) const

Calculate tree statistics.

Definition at line 682 of file quadtree.hpp.

Here is the caller graph for this function:

◆ insert() [1/2]

bool zlayout.spatial.QuadTree< T >.insert	(		self,
		Any	obj,
		Optional[Rectangle]	bbox = None )

Insert an object. If bbox is not provided, try to get it from the object.

Definition at line 135 of file spatial.py.

◆ insert() [2/2]

template<typename T>

bool zlayout::spatial::QuadTree< T >::insert ( const T & object )

Insert object into quadtree.

Parameters

object Object to insert

Returns: true if successfully inserted

Definition at line 627 of file quadtree.hpp.

Here is the caller graph for this function:

◆ merge()

template<typename T>

bool zlayout::spatial::QuadTree< T >::merge ( const QuadTree< T > & other )

Merge another quadtree into this one.

Parameters

other QuadTree to merge

Returns: true if merge was successful

◆ optimize()

template<typename T>

void zlayout::spatial::QuadTree< T >::optimize ( )

Optimize tree structure for better performance This rebuilds the tree with better parameters based on current data.

Definition at line 872 of file quadtree.hpp.

Here is the call graph for this function:

◆ query_circle()

template<typename T>

std::vector< T > zlayout::spatial::QuadTree< T >::query_circle	(	const geometry::Point &	center,
		double	radius ) const

Get objects within circular range.

Parameters

center	Center point of search
radius	Search radius

Returns: Vector of objects within radius

Definition at line 811 of file quadtree.hpp.

Here is the call graph for this function:

◆ query_k_nearest()

template<typename T>

std::vector< T > zlayout::spatial::QuadTree< T >::query_k_nearest	(	const T &	target,
		size_t	k ) const

Get k nearest neighbors to target object.

Parameters

target	Target object
k	Number of neighbors to find

Returns: Vector of k nearest objects

Definition at line 831 of file quadtree.hpp.

◆ query_nearby()

template<typename T>

std::vector< T > zlayout::spatial::QuadTree< T >::query_nearby	(	const T &	target,
		double	distance ) const

Find objects within distance of target object.

Parameters

target	Target object
distance	Maximum distance

Returns: Vector of nearby objects

Definition at line 652 of file quadtree.hpp.

◆ query_point() [1/2]

List[Any] zlayout.spatial.QuadTree< T >.query_point	(		self,
		Point	point )

Find all objects that contain the given point.

Definition at line 160 of file spatial.py.

◆ query_point() [2/2]

template<typename T>

std::vector< T > zlayout::spatial::QuadTree< T >::query_point ( const geometry::Point & point ) const

Query objects containing a specific point.

Parameters

point Query point

Returns: Vector of objects containing the point

Definition at line 645 of file quadtree.hpp.

◆ query_range() [1/2]

List[Any] zlayout.spatial.QuadTree< T >.query_range	(		self,
		Rectangle	range_bbox )

Find all objects that intersect with the given range.

Definition at line 156 of file spatial.py.

◆ query_range() [2/2]

template<typename T>

std::vector< T > zlayout::spatial::QuadTree< T >::query_range ( const geometry::Rectangle & range ) const

Query objects in rectangular range.

Parameters

range Query rectangle

Returns: Vector of objects intersecting the range

Definition at line 638 of file quadtree.hpp.

Here is the caller graph for this function:

◆ rebuild()

template<typename T>

void zlayout::spatial::QuadTree< T >::rebuild	(	size_t	new_capacity,
		size_t	new_max_depth )

Rebuild tree with new parameters.

Definition at line 694 of file quadtree.hpp.

Here is the caller graph for this function:

◆ remove()

template<typename T>

bool zlayout::spatial::QuadTree< T >::remove ( const T & object )

Remove object from tree.

Parameters

object Object to remove

Returns: true if object was found and removed

Definition at line 700 of file quadtree.hpp.

Here is the caller graph for this function:

◆ set_statistics_collection()

template<typename T>

void zlayout::spatial::QuadTree< T >::set_statistics_collection ( bool enable )

inline

Enable/disable statistics collection.

Parameters

enable Whether to collect detailed statistics

Definition at line 377 of file quadtree.hpp.

◆ size() [1/2]

int zlayout.spatial.QuadTree< T >.size ( self )

Get total number of objects in the tree.

Definition at line 214 of file spatial.py.

◆ size() [2/2]

template<typename T>

size_t zlayout::spatial::QuadTree< T >::size ( ) const

inline

Get total number of objects in tree.

Definition at line 193 of file quadtree.hpp.

◆ split_by_regions()

template<typename T>

std::vector< std::unique_ptr< QuadTree > > zlayout::spatial::QuadTree< T >::split_by_regions ( const std::vector< geometry::Rectangle > & regions ) const

Split tree into multiple subtrees based on spatial regions.

Parameters

regions Vector of rectangular regions to split into

Returns: Vector of new QuadTrees for each region

◆ to_string()

template<typename T>

std::string zlayout::spatial::QuadTree< T >::to_string ( ) const

Get tree as string representation (for debugging)

Definition at line 960 of file quadtree.hpp.

◆ update()

template<typename T>

bool zlayout::spatial::QuadTree< T >::update	(	const T &	old_object,
		const T &	new_object )

Update object position (remove and re-insert)

Parameters

old_object	Object to update
new_object	New object data

Returns: true if update was successful

Definition at line 734 of file quadtree.hpp.

Here is the call graph for this function:

◆ validate()

template<typename T>

bool zlayout::spatial::QuadTree< T >::validate ( ) const

Validate tree structure integrity.

Returns: true if tree structure is valid

Definition at line 931 of file quadtree.hpp.

Member Data Documentation

◆ object_count

int zlayout.spatial.QuadTree< T >.object_count = 0

Definition at line 133 of file spatial.py.

◆ root

zlayout.spatial.QuadTree< T >.root = QuadTreeNode(boundary, capacity, max_depth)

Definition at line 132 of file spatial.py.

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

include/zlayout/spatial/quadtree.hpp
zlayout/spatial.py

Classes

Public Types

Public Member Functions

Public Attributes

Protected Member Functions

Detailed Description

Member Typedef Documentation

◆ BoundingBoxFunc

◆ ObjectType

Constructor & Destructor Documentation

◆ QuadTree()

◆ __init__()

Member Function Documentation

◆ _collect_object_bbox_pairs()

◆ _get_all_object_bbox_pairs()

◆ batch_insert()

◆ batch_remove()

◆ begin()

◆ clear() [1/2]

◆ clear() [2/2]

◆ contains()

◆ empty()

◆ end()

◆ find_intersections() [1/2]

◆ find_intersections() [2/2]

◆ find_nearby_objects()

◆ find_potential_intersections()

◆ get_all_objects()

◆ get_detailed_statistics()

◆ get_load_factor()

◆ get_root()

◆ get_statistics()

◆ insert() [1/2]

◆ insert() [2/2]

◆ merge()

◆ optimize()

◆ query_circle()

◆ query_k_nearest()

◆ query_nearby()

◆ query_point() [1/2]

◆ query_point() [2/2]

◆ query_range() [1/2]

◆ query_range() [2/2]

◆ rebuild()

◆ remove()

◆ set_statistics_collection()

◆ size() [1/2]

◆ size() [2/2]

◆ split_by_regions()

◆ to_string()

◆ update()

◆ validate()

Member Data Documentation

◆ object_count

◆ root

◆ init()