PCL
pcl::QuadTree< T > Class Template Reference

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

typedef point::component component
 
typedef rectangle::component coordinate
 
typedef T point
 
typedef Array< pointpoint_list
 
typedef DRect rectangle
 

Public Member Functions

 QuadTree ()=default
 
 QuadTree (const point_list &points, int bucketCapacity=40)
 
 QuadTree (const rectangle &rect, const point_list &points, int bucketCapacity=40)
 
 QuadTree (const QuadTree &)=delete
 
 QuadTree (QuadTree &&x)
 
 ~QuadTree ()
 
int BucketCapacity () const
 
void Build (const point_list &points, int bucketCapacity=40)
 
void Build (const rectangle &rect, const point_list &points, int bucketCapacity=40)
 
void Clear ()
 
void Delete (const point &pt)
 
void Delete (const rectangle &rect)
 
void Insert (const point &pt)
 
bool IsEmpty () const
 
const LeafNodeLeafNodeAt (rectangle::point p) const
 
LeafNodeLeafNodeAt (rectangle::point p)
 
size_type Length () const
 
const NodeNodeAt (rectangle::point p) const
 
NodeNodeAt (rectangle::point p)
 
QuadTreeoperator= (const QuadTree &)=delete
 
QuadTreeoperator= (QuadTree &&x)
 
const NodeRoot () const
 
NodeRoot ()
 
point_list Search (const rectangle &rect) const
 
template<class F >
void Search (const rectangle &rect, F callback, void *data) const
 
template<class F >
void Traverse (F f) const
 
template<class F >
void Traverse (F f)
 

Static Public Member Functions

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

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

Definition at line 111 of file QuadTree.h.

Member Typedef Documentation

◆ component

template<class T>
typedef point::component pcl::QuadTree< T >::component

Represents a point component.

Definition at line 123 of file QuadTree.h.

◆ coordinate

template<class T>
typedef rectangle::component pcl::QuadTree< T >::coordinate

The type of rectangular region coordinates.

Definition at line 138 of file QuadTree.h.

◆ point

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

Represents a two-dimensional point stored in this quadtree.

Definition at line 118 of file QuadTree.h.

◆ point_list

template<class T>
typedef Array<point> pcl::QuadTree< T >::point_list

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

Definition at line 128 of file QuadTree.h.

◆ rectangle

template<class T>
typedef DRect pcl::QuadTree< T >::rectangle

A rectangular region. Used for rectangular range search operations.

Definition at line 133 of file QuadTree.h.

Constructor & Destructor Documentation

◆ QuadTree() [1/5]

template<class T>
pcl::QuadTree< T >::QuadTree ( )
default

Constructs an empty quadtree.

Referenced by pcl::QuadTree< T >::LeafNode::Length(), and pcl::QuadTree< vector_type >::QuadTree().

◆ QuadTree() [2/5]

template<class T>
pcl::QuadTree< T >::QuadTree ( const point_list points,
int  bucketCapacity = 40 
)
inline

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

Parameters
pointsA list of points that will be stored in this quadtree.
bucketCapacityThe maximum number of points in a leaf tree node. Must be >= 1. The default value is 40.

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

Definition at line 303 of file QuadTree.h.

◆ QuadTree() [3/5]

template<class T>
pcl::QuadTree< T >::QuadTree ( const rectangle rect,
const point_list points,
int  bucketCapacity = 40 
)
inline

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

Parameters
rectThe rectangular search region.
pointsA list of points that will be stored in this quadtree.
bucketCapacityThe maximum number of points in a leaf tree node. Must be >= 1. The default value is 40.

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 323 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 345 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 372 of file QuadTree.h.

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 524 of file QuadTree.h.

◆ Build() [1/2]

template<class T>
void pcl::QuadTree< T >::Build ( const point_list points,
int  bucketCapacity = 40 
)
inline

Builds a new quadtree for the specified list of points.

Parameters
pointsA list of points that will be stored in this quadtree.
bucketCapacityThe maximum number of points in a leaf tree node. Must be >= 1. The default value is 40.

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 402 of file QuadTree.h.

Referenced by pcl::QuadTree< vector_type >::QuadTree().

◆ Build() [2/2]

template<class T>
void pcl::QuadTree< T >::Build ( const rectangle rect,
const point_list points,
int  bucketCapacity = 40 
)
inline

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

Parameters
rectThe rectangular search region.
pointsA 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.
bucketCapacityThe maximum number of points in a leaf tree node. Must be >= 1. The default value is 40.

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 449 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 380 of file QuadTree.h.

Referenced by pcl::QuadTree< vector_type >::Build(), and pcl::QuadTree< vector_type >::~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 505 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 514 of file QuadTree.h.

◆ Insert()

template<class T>
void pcl::QuadTree< T >::Insert ( const point pt)
inline

Inserts a new point in this quadtree.

Definition at line 497 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 540 of file QuadTree.h.

◆ LeafNodeAt() [1/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 571 of file QuadTree.h.

◆ LeafNodeAt() [2/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 581 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 532 of file QuadTree.h.

◆ NodeAt() [1/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 595 of file QuadTree.h.

◆ NodeAt() [2/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 609 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.

Referenced by pcl::QuadTree< vector_type >::QuadTree().

◆ 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 355 of file QuadTree.h.

◆ Root() [1/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 552 of file QuadTree.h.

◆ Root() [2/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 561 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
rectThe rectangular search region.

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

Definition at line 465 of file QuadTree.h.

◆ Search() [2/2]

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

Performs a rectangular range search in this quadtree.

Parameters
rectThe rectangular search region.
callbackCallback functional.
dataCallback data.

The callback function prototype should be:

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

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

Definition at line 489 of file QuadTree.h.

◆ Traverse() [1/4]

template<class T>
template<class F >
static void pcl::QuadTree< T >::Traverse ( const Node node,
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 )

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 634 of file QuadTree.h.

◆ Traverse() [2/4]

template<class T>
template<class F >
static void pcl::QuadTree< T >::Traverse ( Node node,
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 670 of file QuadTree.h.

◆ Traverse() [3/4]

template<class T>
template<class F >
void pcl::QuadTree< T >::Traverse ( 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 695 of file QuadTree.h.

◆ Traverse() [4/4]

template<class T>
template<class F >
void pcl::QuadTree< T >::Traverse ( 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 )

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

Definition at line 710 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 718 of file QuadTree.h.


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