CGAL 5.5 - Quadtrees, Octrees, and Orthtrees
CGAL::Orthtree< Traits_, PointRange_, PointMap_ > Class Template Reference

#include <CGAL/Orthtree.h>

Definition

template<typename Traits_, typename PointRange_, typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>
class CGAL::Orthtree< Traits_, PointRange_, PointMap_ >

A data structure using an axis-aligned hybercubic decomposition of dD space for efficient point access and computations.

It builds a hierarchy of nodes which subdivide the space based on a collection of points. Each node represents an axis-aligned hypercubic region of space. A node contains the range of points that are present in the region it defines, and it may contain \(2^{dim}\) other nodes which further subdivide the region.

See also
CGAL::Quadtree
CGAL::Octree
Template Parameters
Traits_must be a model of OrthtreeTraits
PointRange_must be a model of range whose value type is the key type of PointMap_
PointMap_must be a model of ReadablePropertyMap whose value type is Traits_::Point_d
Examples:
Orthtree/orthtree_build.cpp.

Classes

class  Node
 represents a single node of the tree. More...
 

Template Types

typedef PointRange_ PointRange
 Point range.
 
typedef PointMap_ PointMap
 Point map.
 

Traits Types

typedef Traits::Dimension Dimension
 Dimension of the tree.
 
typedef Traits::FT FT
 Number type.
 
typedef Traits::Point_d Point
 Point type.
 
typedef Traits::Bbox_d Bbox
 Bounding box type.
 
typedef Traits::Sphere_d Sphere
 Sphere type.
 

Public Types

typedef Orthtree< Traits, PointRange, PointMapSelf
 Self typedef for convenience.
 
typedef Dimension_tag<(2<<(Dimension::value-1))> Degree
 Degree of the tree (number of children of non-leaf nodes).
 
typedef std::function< bool(Node)> Split_predicate
 A predicate that determines whether a node must be split when refining a tree.
 
typedef unspecified_type Node_range
 A model of ConstRange whose value type is Node.
 

Constructor

 Orthtree (PointRange &point_range, PointMap point_map=PointMap(), const FT enlarge_ratio=1.2, Traits traits=Traits())
 creates an orthtree from a collection of points. More...
 

Tree Building

void refine (const Split_predicate &split_predicate)
 recursively subdivides the orthtree until it meets the given criteria. More...
 
void refine (size_t max_depth=10, size_t bucket_size=20)
 Convenience overload that refines an orthtree using a maximum depth and maximum number of points in a node as split predicate. More...
 
void grade ()
 refines the orthtree such that the difference of depth between two immediate neighbor leaves is never more than 1.
 

Accessors

Node root () const
 returns the root node.
 
Node operator[] (std::size_t index) const
 Convenience function to access the child nodes of the root node by their indices. More...
 
std::size_t depth () const
 returns the deepest level reached by a leaf node in this tree (root being level 0).
 
template<typename Traversal >
Node_range traverse (const Traversal &traversal=Traversal()) const
 constructs a node range using a tree-traversal function. More...
 
Bbox bbox (const Node &node) const
 constructs the bounding box of a node. More...
 

Queries

Node locate (const Point &point) const
 finds the leaf node which contains the point p. More...
 
template<typename OutputIterator >
OutputIterator nearest_neighbors (const Point &query, std::size_t k, OutputIterator output) const
 finds the k nearest neighbors of query. More...
 
template<typename OutputIterator >
OutputIterator nearest_neighbors (const Sphere &query, OutputIterator output) const
 finds the points in sphere. More...
 
template<typename Query , typename OutputIterator >
OutputIterator intersected_nodes (const Query &query, OutputIterator output) const
 finds the leaf nodes that intersect with any primitive. More...
 

Operators

bool operator== (const Self &rhs) const
 compares the topology of the orthtree with that of rhs. More...
 
bool operator!= (const Self &rhs) const
 compares the topology of the orthtree with that of rhs.
 

Constructor & Destructor Documentation

◆ Orthtree()

template<typename Traits_, typename PointRange_, typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>
CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::Orthtree ( PointRange point_range,
PointMap  point_map = PointMap(),
const FT  enlarge_ratio = 1.2,
Traits  traits = Traits() 
)

creates an orthtree from a collection of points.

The constructed orthtree has a root node, with no children, that contains the points passed. That root node has a bounding box that encloses all of the points passed, with padding according to the enlarge_ratio.

That root node is built as a n-cube (square in 2D, cube in 3D, etc.) whose edge size is the longest bounding box edge multiplied by enlarge_ratio. Using an enlarge_ratio>1.0 prevents some points from being exactly on the border of some cells, which can lead to over-refinement.

This single-node orthtree is valid and compatible with all Orthtree functionality, but any performance benefits are unlikely to be realized until refine() is called.

Warning
The input point range is not copied. It is used directly and is rearranged by the Orthtree. Altering the point range after creating the orthtree might leave it in an invalid state.
Parameters
point_rangeinput point range.
point_mapproperty map to access the input points.
enlarge_ratioratio to which the bounding box should be enlarged.
traitsthe traits object.

Member Function Documentation

◆ bbox()

template<typename Traits_, typename PointRange_, typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>
Bbox CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::bbox ( const Node node) const

constructs the bounding box of a node.

Note
The object constructed is not the bounding box of the point subset inside the node, but the bounding box of the node itself (cubic).

◆ intersected_nodes()

template<typename Traits_, typename PointRange_, typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>
template<typename Query , typename OutputIterator >
OutputIterator CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::intersected_nodes ( const Query &  query,
OutputIterator  output 
) const

finds the leaf nodes that intersect with any primitive.

Note
this function requires the function bool CGAL::do_intersect(QueryType, Traits::Bbox_d) to be defined.

This function finds all the intersecting nodes and returns them as const pointers.

Template Parameters
Querythe primitive class (e.g. sphere, ray)
OutputIteratora model of OutputIterator that accepts Node objects
Parameters
querythe intersecting primitive.
outputoutput iterator.

◆ locate()

template<typename Traits_, typename PointRange_, typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>
Node CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::locate ( const Point point) const

finds the leaf node which contains the point p.

Traverses the orthtree and finds the deepest cell that has a domain enclosing the point passed. The point passed must be within the region enclosed by the orthtree (bbox of the root node).

Parameters
pointquery point.
Returns
the node which contains the point.

◆ nearest_neighbors() [1/2]

template<typename Traits_, typename PointRange_, typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>
template<typename OutputIterator >
OutputIterator CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::nearest_neighbors ( const Point query,
std::size_t  k,
OutputIterator  output 
) const

finds the k nearest neighbors of query.

Nearest neighbors are outputted in order of increasing distance to query.

Template Parameters
OutputIteratora model of OutputIterator that accept Point_d objects.
Parameters
querya query point.
kthe number of neighbors.
outputthe output iterator.

◆ nearest_neighbors() [2/2]

template<typename Traits_, typename PointRange_, typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>
template<typename OutputIterator >
OutputIterator CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::nearest_neighbors ( const Sphere query,
OutputIterator  output 
) const

finds the points in sphere.

Nearest neighbors are outputted in order of increasing distance to the center of sphere.

Template Parameters
OutputIteratora model of OutputIterator that accept Point_d objects.
Parameters
queryquery sphere.
outputoutput iterator.

◆ operator==()

template<typename Traits_, typename PointRange_, typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>
bool CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::operator== ( const Self rhs) const

compares the topology of the orthtree with that of rhs.

Trees may be considered equivalent even if they contain different points. Equivalent trees must have the same bounding box and the same node structure. Node structure is evaluated by comparing the root nodes using the node equality operator.

◆ operator[]()

template<typename Traits_, typename PointRange_, typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>
Node CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::operator[] ( std::size_t  index) const

Convenience function to access the child nodes of the root node by their indices.

my_tree[5] is equivalent to my_tree.root()[5].

See also
Node::operator[]()
Parameters
indexthe index of the child node.
Returns
the accessed node.

◆ refine() [1/2]

template<typename Traits_, typename PointRange_, typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>
void CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::refine ( const Split_predicate split_predicate)

recursively subdivides the orthtree until it meets the given criteria.

The split predicate is a std::function that takes a Node and returns a Boolean value (where true implies that a Node needs to be split, false that the Node should be a leaf).

This function may be called several times with different predicates: in that case, nodes already split are left unaltered, while nodes that were not split and for which split_predicate returns true are split.

Parameters
split_predicatedetermines whether or not a node needs to be subdivided.

◆ refine() [2/2]

template<typename Traits_, typename PointRange_, typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>
void CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::refine ( size_t  max_depth = 10,
size_t  bucket_size = 20 
)

Convenience overload that refines an orthtree using a maximum depth and maximum number of points in a node as split predicate.

This is equivalent to calling refine(Orthtrees::Maximum_depth_and_maximum_number_of_inliers(max_depth, bucket_size)).

The refinement is stopped as soon as one of the conditions is violated: if a node has more inliers than bucket_size but is already at max_depth, it is not split. Similarly, a node that is at a depth smaller than max_depth but already has fewer inliers than bucket_size, it is not split.

Parameters
max_depthdeepest a tree is allowed to be (nodes at this depth will not be split).
bucket_sizemaximum points a node is allowed to contain.

◆ traverse()

template<typename Traits_, typename PointRange_, typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>
template<typename Traversal >
Node_range CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::traverse ( const Traversal &  traversal = Traversal()) const

constructs a node range using a tree-traversal function.

This method allows to iterate on the nodes of the tree with a user-selected order (preorder, postorder, leaves-only, etc.).

Template Parameters
Traversalmodel of OrthtreeTraversal that provides functions compatible with the type of the orthree
Parameters
traversalthe instance of Traversal used
Returns
a forward input iterator over the nodes of the tree