A node in the quadtree structure. More...

#include <quadtree.hpp>

Collaboration diagram for zlayout::spatial::QuadTreeNode< T >:

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

Public Member Functions
	QuadTreeNode (const geometry::Rectangle &boundary, size_t capacity=10, size_t max_depth=8, size_t depth=0)
	Constructor.
bool	insert (const T &object, const BoundingBoxFunc &get_bbox)
	Insert object into this node or appropriate child.
std::vector< T >	query_range (const geometry::Rectangle &range, const BoundingBoxFunc &get_bbox) const
	Query objects in a rectangular range.
std::vector< T >	query_point (const geometry::Point &point, const BoundingBoxFunc &get_bbox) const
	Query objects containing a specific point.
size_t	size () const
	Get total number of objects in this subtree.
void	clear ()
	Clear all objects and children.
bool	is_divided () const
	Check if this node has been subdivided.
std::vector< T >	get_all_objects () const
	Get all objects in this subtree.
	__init__ (self, Rectangle boundary, int capacity=10, int max_depth=8)
None	subdivide (self)
bool	insert (self, Any obj, Rectangle bbox)
List[Any]	query_range (self, Rectangle range_bbox)
List[Any]	query_point (self, Point point)
List[Any]	get_all_objects (self)
int	size (self)

Public Attributes
geometry::Rectangle	boundary
	Spatial boundary of this node.
std::vector< T >	objects
	Objects stored in this node.
std::unique_ptr< QuadTreeNode >	children [4]
	Child nodes (NW, NE, SW, SE)
bool	divided = False
	Whether this node has been subdivided.
size_t	capacity
	Maximum objects before subdivision.
size_t	max_depth
	Maximum subdivision depth.
size_t	depth
	Current depth in tree.
	boundary = boundary
	capacity = capacity
	max_depth = max_depth
list	objects = []
list	children = []
	objects

Protected Member Functions
bool	_intersects_boundary (self, Rectangle bbox)

Detailed Description

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

A node in the quadtree structure.

A node in the quadtree structure.

Represents a single node in the quadtree hierarchy. Each node can contain objects up to a specified capacity before subdividing into four child nodes.

Definition at line 28 of file quadtree.hpp.

Member Typedef Documentation

◆ BoundingBoxFunc

template<typename T>

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

Definition at line 31 of file quadtree.hpp.

◆ ObjectType

template<typename T>

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

Definition at line 30 of file quadtree.hpp.

Constructor & Destructor Documentation

◆ QuadTreeNode()

template<typename T>

zlayout::spatial::QuadTreeNode< T >::QuadTreeNode	(	const geometry::Rectangle &	boundary,
		size_t	capacity = 10,
		size_t	max_depth = 8,
		size_t	depth = 0 )

Constructor.

Parameters

boundary	Spatial boundary for this node
capacity	Maximum objects before subdivision
max_depth	Maximum depth for subdivision
depth	Current depth (0 for root)

Definition at line 451 of file quadtree.hpp.

◆ init()

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

Definition at line 12 of file spatial.py.

Member Function Documentation

◆ _intersects_boundary()

bool zlayout.spatial.QuadTreeNode< T >._intersects_boundary	(		self,
		Rectangle	bbox )

protected

Check if bounding box intersects with this node's boundary.

Definition at line 105 of file spatial.py.

Here is the caller graph for this function:

◆ clear()

template<typename T>

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

Clear all objects and children.

Definition at line 590 of file quadtree.hpp.

◆ get_all_objects() [1/2]

List[Any] zlayout.spatial.QuadTreeNode< T >.get_all_objects ( self )

Get all objects in this subtree.

Definition at line 109 of file spatial.py.

◆ get_all_objects() [2/2]

template<typename T>

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

Get all objects in this subtree.

Definition at line 601 of file quadtree.hpp.

◆ insert() [1/2]

bool zlayout.spatial.QuadTreeNode< T >.insert	(		self,
		Any	obj,
		Rectangle	bbox )

Insert an object with its bounding box.

Definition at line 37 of file spatial.py.

Here is the call graph for this function:

◆ insert() [2/2]

template<typename T>

bool zlayout::spatial::QuadTreeNode< T >::insert	(	const T &	object,
		const BoundingBoxFunc &	get_bbox )

Insert object into this node or appropriate child.

Parameters

object	Object to insert
get_bbox	Function to get bounding box from object

Returns: true if successfully inserted

Definition at line 461 of file quadtree.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ is_divided()

template<typename T>

bool zlayout::spatial::QuadTreeNode< T >::is_divided ( ) const

inline

Check if this node has been subdivided.

Definition at line 92 of file quadtree.hpp.

◆ query_point() [1/2]

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

Query all objects that contain the given point.

Definition at line 85 of file spatial.py.

◆ query_point() [2/2]

template<typename T>

std::vector< T > zlayout::spatial::QuadTreeNode< T >::query_point	(	const geometry::Point &	point,
		const BoundingBoxFunc &	get_bbox ) const

Query objects containing a specific point.

Parameters

point	Query point
get_bbox	Function to get bounding box from object

Returns: Vector of objects containing the point

Definition at line 525 of file quadtree.hpp.

Here is the call graph for this function:

◆ query_range() [1/2]

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

Query all objects that intersect with the given range.

Definition at line 65 of file spatial.py.

◆ query_range() [2/2]

template<typename T>

std::vector< T > zlayout::spatial::QuadTreeNode< T >::query_range	(	const geometry::Rectangle &	range,
		const BoundingBoxFunc &	get_bbox ) const

Query objects in a rectangular range.

Parameters

range	Query rectangle
get_bbox	Function to get bounding box from object

Returns: Vector of objects intersecting the range

Definition at line 496 of file quadtree.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ size() [1/2]

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

Get total number of objects in this subtree.

Definition at line 119 of file spatial.py.

◆ size() [2/2]

template<typename T>

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

Get total number of objects in this subtree.

Definition at line 579 of file quadtree.hpp.

◆ subdivide()

None zlayout.spatial.QuadTreeNode< T >.subdivide ( self )

Divide this node into four quadrants.

Definition at line 20 of file spatial.py.

Member Data Documentation

◆ boundary [1/2]

zlayout.spatial.QuadTreeNode< T >.boundary = boundary

Definition at line 13 of file spatial.py.

◆ boundary [2/2]

template<typename T>

geometry::Rectangle zlayout::spatial::QuadTreeNode< T >::boundary

Spatial boundary of this node.

Definition at line 33 of file quadtree.hpp.

◆ capacity [1/2]

zlayout.spatial.QuadTreeNode< T >.capacity = capacity

Definition at line 14 of file spatial.py.

◆ capacity [2/2]

template<typename T>

size_t zlayout::spatial::QuadTreeNode< T >::capacity

Maximum objects before subdivision.

Definition at line 37 of file quadtree.hpp.

◆ children [1/2]

list zlayout.spatial.QuadTreeNode< T >.children = []

Definition at line 18 of file spatial.py.

◆ children [2/2]

template<typename T>

std::unique_ptr<QuadTreeNode> zlayout::spatial::QuadTreeNode< T >::children[4]

Child nodes (NW, NE, SW, SE)

Definition at line 35 of file quadtree.hpp.

◆ depth

template<typename T>

size_t zlayout::spatial::QuadTreeNode< T >::depth

Current depth in tree.

Definition at line 39 of file quadtree.hpp.

◆ divided

template<typename T>

bool zlayout::spatial::QuadTreeNode< T >::divided = False

Whether this node has been subdivided.

Definition at line 36 of file quadtree.hpp.

◆ max_depth [1/2]

zlayout.spatial.QuadTreeNode< T >.max_depth = max_depth

Definition at line 15 of file spatial.py.

◆ max_depth [2/2]

template<typename T>

size_t zlayout::spatial::QuadTreeNode< T >::max_depth

Maximum subdivision depth.

Definition at line 38 of file quadtree.hpp.

◆ objects [1/3]

list zlayout.spatial.QuadTreeNode< T >.objects = []

Definition at line 16 of file spatial.py.

◆ objects [2/3]

zlayout.spatial.QuadTreeNode< T >.objects

Definition at line 44 of file spatial.py.

◆ objects [3/3]

template<typename T>

std::vector<T> zlayout::spatial::QuadTreeNode< T >::objects

Objects stored in this node.

Definition at line 34 of file quadtree.hpp.

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

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

Public Types

Public Member Functions

Public Attributes

Protected Member Functions

Detailed Description

Member Typedef Documentation

◆ BoundingBoxFunc

◆ ObjectType

Constructor & Destructor Documentation

◆ QuadTreeNode()

◆ __init__()

Member Function Documentation

◆ _intersects_boundary()

◆ clear()

◆ get_all_objects() [1/2]

◆ get_all_objects() [2/2]

◆ insert() [1/2]

◆ insert() [2/2]

◆ is_divided()

◆ query_point() [1/2]

◆ query_point() [2/2]

◆ query_range() [1/2]

◆ query_range() [2/2]

◆ size() [1/2]

◆ size() [2/2]

◆ subdivide()

Member Data Documentation

◆ boundary [1/2]

◆ boundary [2/2]

◆ capacity [1/2]

◆ capacity [2/2]

◆ children [1/2]

◆ children [2/2]

◆ depth

◆ divided

◆ max_depth [1/2]

◆ max_depth [2/2]

◆ objects [1/3]

◆ objects [2/3]

◆ objects [3/3]

◆ init()