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.
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 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_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 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
-
| 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
1.8.13