Bucket PR quadtree for two-dimensional point data. More...

#include <QuadTree.h>

Inheritance diagram for pcl::QuadTree< T >:

Classes
class	LeafNode
	Quadtree leaf node structure. More...

class	Node
	Quadtree node structure. More...

Public Types
using	component = typename point::component

using	coordinate = rectangle::component

using	point = T

using	point_list = Array< point >

using	rectangle = DRect

Public Member Functions
	QuadTree ()=default

	QuadTree (const point_list &points, int bucketCapacity=__PCL_QUADTREE_DEFAULT_BUCKET_CAPACITY, double epsilon=__PCL_QUADTREE_DEFAULT_EPSILON)

	QuadTree (const QuadTree &)=delete

	QuadTree (const rectangle &rect, const point_list &points, int bucketCapacity=__PCL_QUADTREE_DEFAULT_BUCKET_CAPACITY, double epsilon=__PCL_QUADTREE_DEFAULT_EPSILON)

	QuadTree (QuadTree &&x)

	~QuadTree ()

int	BucketCapacity () const

void	Build (const point_list &points, int bucketCapacity=__PCL_QUADTREE_DEFAULT_BUCKET_CAPACITY, double epsilon=__PCL_QUADTREE_DEFAULT_EPSILON)

void	Build (const rectangle &rect, const point_list &points, int bucketCapacity=__PCL_QUADTREE_DEFAULT_BUCKET_CAPACITY, double epsilon=__PCL_QUADTREE_DEFAULT_EPSILON)

void	Clear ()

void	Delete (const point &pt)

void	Delete (const rectangle &rect)

int	Height () const

void	Insert (const point &pt)

bool	IsEmpty () const

LeafNode *	LeafNodeAt (rectangle::point p)

const LeafNode *	LeafNodeAt (rectangle::point p) const

size_type	Length () const

Node *	NodeAt (rectangle::point p)

const Node *	NodeAt (rectangle::point p) const

size_type	NumberOfLeafNodes () const

size_type	NumberOfNodes () const

QuadTree &	operator= (const QuadTree &)=delete

QuadTree &	operator= (QuadTree &&x)

Node *	Root ()

const Node *	Root () const

point_list	Search (const rectangle &rect) const

template<class F >
void	Search (const rectangle &rect, F callback, void *data) const

Node *	SplitAt (rectangle::point p)

template<class F >
void	Traverse (F f)

template<class F >
void	Traverse (F f) const

Static Public Member Functions
static int	Height (const Node *node)

static size_type	NumberOfLeafNodes (const Node *node)

static size_type	NumberOfNodes (const Node *node)

template<class F >
static void	Traverse (const Node *node, F f)

template<class F >
static void	Traverse (Node *node, F f)

Friends
void	Swap (QuadTree &x1, QuadTree &x2)

Detailed Description

template<class T>
class pcl::QuadTree< T >

A quadtree is a specialized binary search tree for partitioning of a set of points in two dimensions. Quadtrees have important applications in computational geometry problems requiring efficient rectangular range searching and nearest neighbor queries.

This class implements a bucket point region quadtree structure (see Reference 2).

The template type argument T represents the type of a point object stored in a QuadTree structure. The type T must have the following properties:

The standard default and copy constructors are required:

T::T()
T::T( const T& )

The T::component subtype must be defined. It represents a component of an object of type T. For example, if T is a vector type, T::component must be the type of a vector component.

The array subscript operator must be defined as follows:

component T::operator []( int i ) const

This operator must return the value of the first or second component of an object being stored in the quadtree. The subindex i will be either 0 or 1 for the first or second point component, respectively.

References

Mark de Berg et al, Computational Geometry: Algorithms and Applications Third Edition, Springer, 2010, Chapter 14.
Hanan Samet, Foundations of Multidimensional and Metric Data Structures, Morgan Kaufmann, 2006, Section 1.4.

See also: KDTree

Definition at line 123 of file QuadTree.h.

Member Typedef Documentation

◆ component

template<class T >

using pcl::QuadTree< T >::component = typename point::component

Represents a point component.

Definition at line 135 of file QuadTree.h.

◆ coordinate

template<class T >

using pcl::QuadTree< T >::coordinate = rectangle::component

The type of rectangular region coordinates.

Definition at line 150 of file QuadTree.h.

◆ point

template<class T >

using pcl::QuadTree< T >::point = T

Represents a two-dimensional point stored in this quadtree.

Definition at line 130 of file QuadTree.h.

◆ point_list

template<class T >

using pcl::QuadTree< T >::point_list = Array<point>

A list of points. Used for tree build and search operations.

Definition at line 140 of file QuadTree.h.

◆ rectangle

template<class T >

using pcl::QuadTree< T >::rectangle = DRect

A rectangular region. Used for rectangular range search operations.

Definition at line 145 of file QuadTree.h.

Constructor & Destructor Documentation

◆ QuadTree() [1/5]

template<class T >

pcl::QuadTree< T >::QuadTree ( )

default

Constructs an empty quadtree.

◆ QuadTree() [2/5]

template<class T >

pcl::QuadTree< T >::QuadTree	(	const point_list &	points,
		int	bucketCapacity = `__PCL_QUADTREE_DEFAULT_BUCKET_CAPACITY`,
		double	epsilon = `__PCL_QUADTREE_DEFAULT_EPSILON`
	)

inline

Constructs a quadtree and builds it for the specified list of points.

Parameters

points	A list of points that will be stored in this quadtree.
bucketCapacity	The maximum number of points in a leaf tree node. Must be ≥ 1. The default value is 40.
epsilon	The minimum allowed dimension of a quadtree node region. Must be larger than or equal to twice the machine epsilon for the `coordinate` type. The default value is 1e-8.

If the specified list of points is empty, this constructor yields an empty quadtree.

Definition at line 346 of file QuadTree.h.

◆ QuadTree() [3/5]

template<class T >

pcl::QuadTree< T >::QuadTree	(	const rectangle &	rect,
		const point_list &	points,
		int	bucketCapacity = `__PCL_QUADTREE_DEFAULT_BUCKET_CAPACITY`,
		double	epsilon = `__PCL_QUADTREE_DEFAULT_EPSILON`
	)

inline

Constructs a quadtree and builds it for the specified list of points and a prescribed rectangular search region.

Parameters

rect	The rectangular search region.
points	A list of points that will be stored in this quadtree.
bucketCapacity	The maximum number of points in a leaf tree node. Must be ≥ 1. The default value is 40.
epsilon	The minimum allowed dimension of a quadtree node region. Must be larger than or equal to twice the machine epsilon for the `coordinate` type. The default value is 1e-8.

If the specified list of points is empty, or if no points lie within the rect region, this constructor yields an empty quadtree.

Definition at line 373 of file QuadTree.h.

◆ QuadTree() [4/5]

template<class T >

pcl::QuadTree< T >::QuadTree ( const QuadTree< T > & )

delete

Copy constructor. Copy construction is disabled because this class uses internal data structures that cannot be copy-constructed. However, QuadTree implements move construction and move assignment.

◆ QuadTree() [5/5]

template<class T >

pcl::QuadTree< T >::QuadTree ( QuadTree< T > && x )

inline

Move constructor.

Definition at line 397 of file QuadTree.h.

◆ ~QuadTree()

template<class T >

pcl::QuadTree< T >::~QuadTree ( )

inline

Destroys a quadtree. All the stored point objects are deleted.

Definition at line 428 of file QuadTree.h.

References pcl::QuadTree< T >::Clear().

Member Function Documentation

◆ BucketCapacity()

template<class T >

int pcl::QuadTree< T >::BucketCapacity ( ) const

inline

Returns the bucket capacity of this quadtree, or the maximum number of points that can be stored in a leaf tree node. This parameter is specified when a new tree is built.

Definition at line 603 of file QuadTree.h.

◆ Build() [1/2]

template<class T >

void pcl::QuadTree< T >::Build	(	const point_list &	points,
		int	bucketCapacity = `__PCL_QUADTREE_DEFAULT_BUCKET_CAPACITY`,
		double	epsilon = `__PCL_QUADTREE_DEFAULT_EPSILON`
	)

inline

Builds a new quadtree for the specified list of points.

Parameters

points	A list of points that will be stored in this quadtree.
bucketCapacity	The maximum number of points in a leaf tree node. Must be ≥ 1. The default value is 40.
epsilon	The minimum allowed dimension of a quadtree node region. Must be larger than or equal to twice the machine epsilon for the `coordinate` type. The default value is 1e-8.

If the tree stores point objects before calling this function, they are destroyed and removed before building a new tree.

If the specified list of points is empty, this member function yields an empty quadtree.

Definition at line 463 of file QuadTree.h.

◆ Build() [2/2]

template<class T >

void pcl::QuadTree< T >::Build	(	const rectangle &	rect,
		const point_list &	points,
		int	bucketCapacity = `__PCL_QUADTREE_DEFAULT_BUCKET_CAPACITY`,
		double	epsilon = `__PCL_QUADTREE_DEFAULT_EPSILON`
	)

inline

Builds a new quadtree with the specified list of points and a prescribed rectangular search region.

Parameters

rect	The rectangular search region.
points	A list of points to be stored in this quadtree. Only points included in the specified rect search region will be inserted in the tree. All points outside rect will be ignored.
bucketCapacity	The maximum number of points in a leaf tree node. Must be ≥ 1. The default value is 40.
epsilon	The minimum allowed dimension of a quadtree node region. Must be larger than or equal to twice the machine epsilon for the `coordinate` type. The default value is 1e-8.

If the tree stores point objects before calling this function, they are destroyed and removed before building a new tree.

If the specified list of points is empty, or if no points lie within the rect region, this member function yields an empty quadtree.

Definition at line 518 of file QuadTree.h.

◆ Clear()

template<class T >

void pcl::QuadTree< T >::Clear ( )

inline

Removes all the stored point objects, yielding an empty quadtree.

Definition at line 436 of file QuadTree.h.

Referenced by pcl::QuadTree< T >::~QuadTree().

◆ Delete() [1/2]

template<class T >

void pcl::QuadTree< T >::Delete ( const point & pt )

inline

Deletes all points in this quadtree equal to the specified point.

Definition at line 584 of file QuadTree.h.

◆ Delete() [2/2]

template<class T >

void pcl::QuadTree< T >::Delete ( const rectangle & rect )

inline

Deletes all points in this quadtree included in the specified rectangular region rect.

Definition at line 593 of file QuadTree.h.

References pcl::GenericRectangle< T >::Ordered().

◆ Height() [1/2]

template<class T >

int pcl::QuadTree< T >::Height ( ) const

inline

Returns the height of this quadtree.

Definition at line 884 of file QuadTree.h.

◆ Height() [2/2]

template<class T >

static int pcl::QuadTree< T >::Height ( const Node * node )

inlinestatic

Returns the height of the subtree rooted at the specified node.

Definition at line 876 of file QuadTree.h.

◆ Insert()

template<class T >

void pcl::QuadTree< T >::Insert ( const point & pt )

inline

Inserts a point in this quadtree.

Definition at line 569 of file QuadTree.h.

◆ IsEmpty()

template<class T >

bool pcl::QuadTree< T >::IsEmpty ( ) const

inline

Returns true iff this quadtree is empty.

Definition at line 619 of file QuadTree.h.

◆ LeafNodeAt() [1/2]

template<class T >

LeafNode* pcl::QuadTree< T >::LeafNodeAt ( rectangle::point p )

inline

Returns a pointer to the leaf node of this quadtree that includes the specified point p in the plane, or nullptr if no such leaf node exists in this quadtree.

Definition at line 660 of file QuadTree.h.

◆ LeafNodeAt() [2/2]

template<class T >

const LeafNode* pcl::QuadTree< T >::LeafNodeAt ( rectangle::point p ) const

inline

Returns a pointer to the (immutable) leaf node of this quadtree that includes the specified point p in the plane, or nullptr if no such leaf node exists in this quadtree.

Definition at line 650 of file QuadTree.h.

◆ Length()

template<class T >

size_type pcl::QuadTree< T >::Length ( ) const

inline

Returns the total number of points stored in this quadtree.

Definition at line 611 of file QuadTree.h.

◆ NodeAt() [1/2]

template<class T >

Node* pcl::QuadTree< T >::NodeAt ( rectangle::point p )

inline

Returns a pointer to the node of this quadtree that includes the specified point p in the plane, or nullptr if no such node exists in this quadtree.

The returned node can be a leaf node or a structural node. This function should only return nullptr if the specified point p is exterior to the root rectangular region of this quadtree, or if this quadtree is empty.

Definition at line 688 of file QuadTree.h.

◆ NodeAt() [2/2]

template<class T >

const Node* pcl::QuadTree< T >::NodeAt ( rectangle::point p ) const

inline

Returns a pointer to the (immutable) node of this quadtree that includes the specified point p in the plane, or nullptr if no such node exists in this quadtree.

The returned node can be a leaf node or a structural node. This function should only return nullptr if the specified point p is exterior to the root rectangular region of this quadtree, or if this quadtree is empty.

Definition at line 674 of file QuadTree.h.

◆ NumberOfLeafNodes() [1/2]

template<class T >

size_type pcl::QuadTree< T >::NumberOfLeafNodes ( ) const

inline

Returns the total number of existing leaf nodes in this quadtree.

Definition at line 868 of file QuadTree.h.

◆ NumberOfLeafNodes() [2/2]

template<class T >

static size_type pcl::QuadTree< T >::NumberOfLeafNodes ( const Node * node )

inlinestatic

Returns the total number of existing leaf nodes in the subtree rooted at the specified node.

Definition at line 858 of file QuadTree.h.

◆ NumberOfNodes() [1/2]

template<class T >

size_type pcl::QuadTree< T >::NumberOfNodes ( ) const

inline

Returns the total number of existing nodes in this quadtree, including structural and leaf nodes.

Definition at line 849 of file QuadTree.h.

◆ NumberOfNodes() [2/2]

template<class T >

static size_type pcl::QuadTree< T >::NumberOfNodes ( const Node * node )

inlinestatic

Returns the total number of existing nodes in the subtree rooted at the specified node, including structural and leaf nodes.

Definition at line 838 of file QuadTree.h.

◆ operator=() [1/2]

template<class T >

QuadTree& pcl::QuadTree< T >::operator= ( const QuadTree< T > & )

delete

Copy assignment operator. Copy assignment is disabled because this class uses internal data structures that cannot be copy-assigned. However, QuadTree implements move assignment and move construction.

◆ operator=() [2/2]

template<class T >

QuadTree& pcl::QuadTree< T >::operator= ( QuadTree< T > && x )

inline

Move assignment operator. Returns a reference to this object.

Definition at line 410 of file QuadTree.h.

◆ Root() [1/2]

template<class T >

Node* pcl::QuadTree< T >::Root ( )

inline

Returns a pointer to the (mutable) root node of this quadtree, or nullptr if this quadtree is empty.

Definition at line 640 of file QuadTree.h.

◆ Root() [2/2]

template<class T >

const Node* pcl::QuadTree< T >::Root ( ) const

inline

Returns a pointer to the root node of this quadtree, or nullptr if this quadtree is empty.

The returned pointer is const qualified to forbid uncontrolled alterations that might invalidate the quadtree structure.

Definition at line 631 of file QuadTree.h.

◆ Search() [1/2]

template<class T >

point_list pcl::QuadTree< T >::Search ( const rectangle & rect ) const

inline

Performs a rectangular range search in this quadtree.

Parameters

rect	The rectangular search region.

Returns a (possibly empty) list with all the points found in this tree within the specified search range.

Definition at line 537 of file QuadTree.h.

References pcl::GenericRectangle< T >::Ordered().

◆ Search() [2/2]

template<class T >

template<class F >

void pcl::QuadTree< T >::Search	(	const rectangle &	rect,
		F	callback,
		void *	data
	)		const

inline

Performs a rectangular range search in this quadtree.

Parameters

rect	The rectangular search region.
callback	Callback functional.
data	Callback data.

The callback function prototype should be:

void callback( const point& pt, void* data )

pcl::QuadTree::point

T point

Definition: QuadTree.h:130

The callback function will be called once for each point found in the tree within the specified search range.

Definition at line 561 of file QuadTree.h.

◆ SplitAt()

template<class T >

Node* pcl::QuadTree< T >::SplitAt ( rectangle::point p )

inline

Forces a quadtree subdivision of the leaf node that includes the specified point p in the plane.

Returns the newly created structural node. This function should only return nullptr if the specified point p is exterior to the root rectangular region of this quadtree, or if this quadtree is empty. It could also return nullptr in degenerate cases where no further subdivision of the plane would be possible because of numerical limits.

Definition at line 703 of file QuadTree.h.

References pcl::QuadTree< T >::Node::Includes(), pcl::QuadTree< T >::Node::ne, pcl::QuadTree< T >::Node::nw, pcl::QuadTree< T >::Node::se, and pcl::QuadTree< T >::Node::sw.

◆ Traverse() [1/4]

template<class T >

template<class F >

static void pcl::QuadTree< T >::Traverse	(	const Node *	node,
		F	f
	)

inlinestatic

Performs a recursive left-to-right, depth-first traversal of the subtree rooted at the specified node, invoking the specified function f successively for each leaf node.

The function f must be compatible with the form:

void f( const rectangle& r, const point_list& p, void*& d )

pcl::QuadTree::rectangle

DRect rectangle

Definition: QuadTree.h:145

pcl::QuadTree::point_list

Array< point > point_list

Definition: QuadTree.h:140

where r is the plane region covered by the current leaf node, p is the list of points in the current leaf node, and d is the optional pointer to arbitrary data associated with the current leaf node.

The sequence of calls for the subtrees in each non-leaf node is: NW, NE, SW, SE. Only non-empty leaf nodes are included in the traversal, hence the function f will be invoked exclusively for non-empty point lists.

If the specified node is nullptr, this function takes no action.

Definition at line 753 of file QuadTree.h.

◆ Traverse() [2/4]

template<class T >

template<class F >

void pcl::QuadTree< T >::Traverse ( F f )

inline

Performs a recursive left-to-right, depth-first traversal of the entire (mutable) quadtree, invoking the specified function f successively for each leaf node. Calling this function is equivalent to:

Traverse( Root(), f )

pcl::QuadTree::Traverse

static void Traverse(const Node *node, F f)

Definition: QuadTree.h:753

pcl::QuadTree::Root

const Node * Root() const

Definition: QuadTree.h:631

If this quadtree is empty, this function takes no action.

Definition at line 829 of file QuadTree.h.

◆ Traverse() [3/4]

template<class T >

template<class F >

void pcl::QuadTree< T >::Traverse ( F f ) const

inline

Performs a recursive left-to-right, depth-first traversal of the entire quadtree, invoking the specified function f successively for each leaf node. Calling this function is equivalent to:

Traverse( Root(), f )

If this quadtree is empty, this function takes no action.

Definition at line 814 of file QuadTree.h.

◆ Traverse() [4/4]

template<class T >

template<class F >

static void pcl::QuadTree< T >::Traverse	(	Node *	node,
		F	f
	)

inlinestatic

Performs a recursive left-to-right, depth-first traversal of the subtree rooted at the specified (mutable) node, invoking the specified function f successively for each leaf node.

The function f must be compatible with the form:

void f( const rectangle& r, point_list& p, void*& d )

where r is the plane region covered by the current leaf node, p is the list of points in the current leaf node, and d is the optional pointer to arbitrary data associated with the current leaf node.

The sequence of calls for the subtrees in each non-leaf node is: NW, NE, SW, SE. Only non-empty leaf nodes are included in the traversal, hence the function f will be invoked exclusively for non-empty point lists.

If the specified node is nullptr, this function takes no action.

Definition at line 789 of file QuadTree.h.

Friends And Related Function Documentation

◆ Swap

template<class T >

void Swap	(	QuadTree< T > &	x1,
		QuadTree< T > &	x2
	)

friend

Exchanges two QuadTree objects x1 and x2.

Definition at line 892 of file QuadTree.h.

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

QuadTree.h

Classes

Public Types

Public Member Functions

Static Public Member Functions

Friends

Detailed Description

template<class T> class pcl::QuadTree< T >

Member Typedef Documentation

◆ component

◆ coordinate

◆ point

◆ point_list

◆ rectangle

Constructor & Destructor Documentation

◆ QuadTree() [1/5]

◆ QuadTree() [2/5]

◆ QuadTree() [3/5]

◆ QuadTree() [4/5]

◆ QuadTree() [5/5]

◆ ~QuadTree()

Member Function Documentation

◆ BucketCapacity()

◆ Build() [1/2]

◆ Build() [2/2]

◆ Clear()

◆ Delete() [1/2]

◆ Delete() [2/2]

◆ Height() [1/2]

◆ Height() [2/2]

◆ Insert()

◆ IsEmpty()

◆ LeafNodeAt() [1/2]

◆ LeafNodeAt() [2/2]

◆ Length()

◆ NodeAt() [1/2]

◆ NodeAt() [2/2]

◆ NumberOfLeafNodes() [1/2]

◆ NumberOfLeafNodes() [2/2]

◆ NumberOfNodes() [1/2]

◆ NumberOfNodes() [2/2]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ Root() [1/2]

◆ Root() [2/2]

◆ Search() [1/2]

◆ Search() [2/2]

◆ SplitAt()

◆ Traverse() [1/4]

◆ Traverse() [2/4]

◆ Traverse() [3/4]

◆ Traverse() [4/4]

Friends And Related Function Documentation

◆ Swap

template<class T>
class pcl::QuadTree< T >