template<typename GeomTraits>
class CGAL::Orthtree< GeomTraits >
A data structure using an axis-aligned hyperrectangle decomposition of dD space for efficient access and computation.
It builds a hierarchy of nodes which subdivides the space. Each node represents an axis-aligned hyperrectangle region of space. The contents of nodes depend on the traits class, non-leaf nodes also contain \(2^{dim}\) other nodes which further subdivide the region.
- See also
CGAL::Quadtree -
CGAL::Octree
- Template Parameters
-
- Examples
- Orthtree/octree_build_from_point_set.cpp, Orthtree/octree_build_from_point_vector.cpp, Orthtree/octree_build_with_custom_split.cpp, Orthtree/octree_find_nearest_neighbor.cpp, Orthtree/octree_grade.cpp, Orthtree/octree_surface_mesh.cpp, Orthtree/octree_traversal_custom.cpp, Orthtree/octree_traversal_manual.cpp, Orthtree/octree_traversal_preorder.cpp, Orthtree/orthtree_build.cpp, and Orthtree/quadtree_build_from_point_vector.cpp.
|
|
using | Kernel = typename Traits::Kernel |
| | Kernel type.
|
| |
|
using | Geom_traits = Kernel |
| |
|
using | FT = typename Traits::FT |
| | Number type.
|
| |
|
using | Point = typename Traits::Point_d |
| | Point type.
|
| |
|
using | Bbox = typename Traits::Bbox_d |
| | Bounding box type.
|
| |
|
using | Sphere = typename Traits::Sphere_d |
| | Sphere type.
|
| |
|
using | Adjacency = typename Traits::Adjacency |
| | Adjacency type.
|
| |
|
using | Node_index = typename Traits::Node_index |
| | Index of a given node in the tree; the root always has index 0.
|
| |
|
using | Node_data = std::conditional_t< has_data, typename GeomTraits::Node_data, void * > |
| |
|
static constexpr bool | has_data = bool_value |
| | true if GeomTraits is a model of OrthtreeTraitsWithData and false otherwise.
|
| |
|
static constexpr bool | supports_neighbor_search = bool_value |
| | true if GeomTraits is a model of CollectionPartitioningOrthtreeTraits and false otherwise.
|
| |
|
static constexpr int | dimension = Traits::dimension |
| | Dimension of the tree.
|
| |
|
|
using | Self = Orthtree< Traits > |
| | Self alias for convenience.
|
| |
| using | Local_coordinates = std::bitset< dimension > |
| | Set of bits representing this node's relationship to its parent.
|
| |
| using | Global_coordinates = std::array< std::uint32_t, dimension > |
| | Coordinates representing this node's relationship with the rest of the tree.
|
| |
|
using | Split_predicate = std::function< bool(Node_index, const Self &)> |
| | A predicate that determines whether a node must be split when refining a tree.
|
| |
|
using | Node_index_range = unspecified_type |
| | A model of ForwardRange whose value type is Node_index.
|
| |
|
template<class T > |
| using | Property_map = unspecified_type |
| | A model of LvaluePropertyMap with Node_index as key type and T as value type.
|
| |
|
static constexpr int | degree = (2 << (dimension - 1)) |
| | Degree of the tree (number of children of non-leaf nodes).
|
| |
|
|
const Traits & | traits () const |
| | provides direct read-only access to the tree traits.
|
| |
|
const Kernel & | geom_traits () const |
| |
|
Node_index | root () const |
| | provides access to the root node, and by extension the rest of the tree.
|
| |
|
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_index_range | traverse (Traversal traversal) const |
| | constructs a node index range using a tree-traversal function.
|
| |
| template<typename Traversal , typename ... Args> |
| Node_index_range | traverse (Args &&...args) const |
| | convenience method for using a traversal without constructing it yourself
|
| |
|
FT | compute_cartesian_coordinate (std::uint32_t gc, std::size_t depth, int ci) const |
| |
| Bbox | bbox (Node_index n) const |
| | constructs the bounding box of a node.
|
| |
|
| template<typename T > |
| std::pair< Property_map< T >, bool > | add_property (const std::string &name, const T default_value=T()) |
| | gets a property for nodes, adding it if it does not already exist.
|
| |
| template<typename T > |
| std::optional< Property_map< T > > | property (const std::string &name) const |
| | gets a property of the nodes if it exists.
|
| |
|
std::vector< std::string > | properties () const |
| | returns a vector of all property names.
|
| |
| template<typename T > |
| bool | remove_property (Property_map< T > property) |
| | removes the node property from the tree.
|
| |
|
| Node_index | locate (const Point &point) const |
| | finds the leaf node which contains a particular point in space.
|
| |
| template<typename OutputIterator > |
| auto | nearest_k_neighbors (const Point &query, std::size_t k, OutputIterator output) const -> std::enable_if_t< supports_neighbor_search, OutputIterator > |
| | finds the k nearest neighbors of the point query.
|
| |
| template<typename OutputIterator > |
| auto | neighbors_within_radius (const Sphere &query, OutputIterator output) const -> std::enable_if_t< supports_neighbor_search, OutputIterator > |
| | finds the elements in the sphere query.
|
| |
| template<typename OutputIterator > |
| auto | nearest_k_neighbors_within_radius (const Sphere &query, std::size_t k, OutputIterator output) const -> std::enable_if_t< supports_neighbor_search, OutputIterator > |
| | finds at most k elements within a specific radius that are nearest to the center of the sphere query: if query does not contain at least k elements, only contained elements will be returned.
|
| |
| template<typename Query , typename OutputIterator > |
| OutputIterator | intersected_nodes (const Query &query, OutputIterator output) const |
| | finds the leaf nodes that intersect with any primitive.
|
| |
|
|
bool | is_leaf (Node_index n) const |
| | determines whether the node specified by index n is a leaf node.
|
| |
|
bool | is_root (Node_index n) const |
| | determines whether the node specified by index n is the root node.
|
| |
| std::size_t | depth (Node_index n) const |
| | determines the depth of the node specified.
|
| |
|
std::conditional_t< has_data, Node_data &, void * > & | data (Node_index n) |
| | retrieves a reference to the Node_data associated with the node specified by n if GeomTraits is a model of OrthtreeTraitswithData, and nullptr otherwise.
|
| |
|
std::conditional_t< has_data, const Node_data &, void * > | data (Node_index n) const |
| | retrieves a const reference to the Node_data associated with the node specified by n if GeomTraits is a model of OrthtreeTraitswithData, and nullptr otherwise.
|
| |
|
Global_coordinates | global_coordinates (Node_index n) const |
| | retrieves the global coordinates of the node.
|
| |
|
Local_coordinates | local_coordinates (Node_index n) const |
| | retrieves the local coordinates of the node.
|
| |
| Node_index | parent (Node_index n) const |
| | returns this n's parent.
|
| |
| Node_index | child (Node_index n, std::size_t i) const |
| | returns a node's ith child.
|
| |
| template<typename... Indices> |
| Node_index | descendant (Node_index node, Indices... indices) const |
| | retrieves an arbitrary descendant of the node specified by node.
|
| |
| template<typename... Indices> |
| Node_index | node (Indices... indices) const |
| | convenience function for retrieving arbitrary nodes.
|
| |
| const std::optional< Node_index > | next_sibling (Node_index n) const |
| | finds the next sibling in the parent of the node specified by the index n.
|
| |
| const std::optional< Node_index > | next_sibling_up (Node_index n) const |
| | finds the next sibling of the parent of the node specified by n if it exists.
|
| |
| Node_index | deepest_first_child (Node_index n) const |
| | finds the leaf node reached when descending the tree and always choosing child 0.
|
| |
| std::optional< Node_index > | first_child_at_depth (Node_index n, std::size_t d) const |
| | finds node reached when descending the tree to a depth d and always choosing child 0.
|
| |
| void | split (Node_index n) |
| | splits a node into subnodes.
|
| |
| Point | barycenter (Node_index n) const |
| | returns the center point of a node.
|
| |
| std::optional< Node_index > | adjacent_node (Node_index n, const Local_coordinates &direction) const |
| | finds the directly adjacent node in a specific direction
|
| |
| std::optional< Node_index > | adjacent_node (Node_index n, Adjacency adjacency) const |
| | equivalent to adjacent_node(), with an adjacency direction rather than a bitset.
|
| |
| static bool | is_topology_equal (Node_index lhsNode, const Self &lhsTree, Node_index rhsNode, const Self &rhsTree) |
| | determines whether a pair of subtrees have the same topology.
|
| |
| static bool | is_topology_equal (const Self &lhs, const Self &rhs) |
| | helper function for calling is_topology_equal() on the root nodes of two trees.
|
| |
template<typename GeomTraits >
Set of bits representing this node's relationship to its parent.
Equivalent to an array of Booleans, where index[0] is whether x is greater, index[1] is whether y is greater, index[2] is whether z is greater, and so on for higher dimensions if needed. Used to represent a node's relationship to the center of its parent.
template<typename GeomTraits >
constructs an orthtree for a traits instance.
The constructed orthtree has a root node with no children, containing the contents determined by Construct_root_node_contents from the traits class. That root node has a bounding box determined by Construct_root_node_bbox from the traits class, which typically encloses its contents.
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.
- Parameters
-
template<typename GeomTraits >
finds the directly adjacent node in a specific direction
- Precondition
direction.to_ulong < 2 * dimension
Adjacent nodes are found according to several properties:
- adjacent nodes may be larger than the seek node, but never smaller
- a node has at most
2 * dimension different adjacent nodes (in 3D: left, right, up, down, front, back)
- adjacent nodes are not required to be leaf nodes
Here's a diagram demonstrating the concept for a quadtree:
+---------------+---------------+
| | |
| | |
| | |
| A | |
| | |
| | |
| | |
+-------+-------+---+---+-------+
| | | | | |
| A | (S) +---A---+ |
| | | | | |
+---+---+-------+---+---+-------+
| | | | | |
+---+---+ A | | |
| | | | | |
+---+---+-------+-------+-------+
- (S) : Seek node
- A : Adjacent node
Note how the top adjacent node is larger than the seek node. The right adjacent node is the same size, even though it contains further subdivisions.
This implementation returns the adjacent node if it's found. If there is no adjacent node in that direction, it returns a null node.
- Parameters
-
| n | index of the node to find a neighbor of |
| direction | which way to find the adjacent node relative to this one. Each successive bit selects the direction for the corresponding dimension: for an octree in 3D, 010 means: negative direction in X, position direction in Y, negative direction in Z. |
- Returns
- the index of the adjacent node if it exists, nothing otherwise.
template<typename GeomTraits >
template<typename... Indices>
retrieves an arbitrary descendant of the node specified by node.
Convenience function to avoid the need to call orthtree.child(orthtree.child(node, 0), 1).
Each index in indices specifies which child to enter as descending the tree from node down. Indices are evaluated in the order they appear as parameters, so descendant(root, 0, 1) returns the second child of the first child of the root.
- Parameters
-
| node | the node to descend |
| indices | the integer indices specifying the descent to perform |
- Returns
- the index of the specified descendant node
template<typename GeomTraits >
recursively subdivides the orthtree until it meets the given criteria.
The split predicate should return true if a leaf node should be split and false otherwise.
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 leaf node needs to be subdivided. |
template<typename GeomTraits >
| void CGAL::Orthtree< GeomTraits >::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 contained elements in a node as split predicate.
This is equivalent to calling refine(Orthtrees::Maximum_depth_and_maximum_contained_elements(max_depth,
bucket_size)).
The refinement is stopped as soon as one of the conditions is violated: if a node contains more elements 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 contains fewer elements than bucket_size, it is not split.
- Warning
- This convenience method is only appropriate for trees with traits classes where
Node_data is a model of Range. RandomAccessRange is suggested for performance.
- Parameters
-
| max_depth | deepest a tree is allowed to be (nodes at this depth will not be split). |
| bucket_size | maximum number of items a node is allowed to contain. |
1.9.6