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 axisaligned 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 axisaligned 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.
template<typename Traits_, typename PointRange_, typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>
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 overrefinement.
This singlenode 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_range  input point range. 
point_map  property map to access the input points. 
enlarge_ratio  ratio to which the bounding box should be enlarged. 
traits  the traits object. 
template<typename Traits_, typename PointRange_, typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>
template<typename Query , typename OutputIterator >
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

 Parameters

query  the intersecting primitive. 
output  output iterator. 
template<typename Traits_, typename PointRange_, typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>
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

 Returns
 the node which contains the point.
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.
template<typename Traits_, typename PointRange_, typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>
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_predicate  determines whether or not a node needs to be subdivided. 
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_depth  deepest a tree is allowed to be (nodes at this depth will not be split). 
bucket_size  maximum points a node is allowed to contain. 
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 treetraversal function.
This method allows to iterate on the nodes of the tree with a userselected order (preorder, postorder, leavesonly, etc.).
 Template Parameters

Traversal  model of OrthtreeTraversal that provides functions compatible with the type of the orthree 
 Parameters

traversal  the instance of Traversal used 
 Returns
 a forward input iterator over the nodes of the tree