CGAL 6.0 - Quadtrees, Octrees, and Orthtrees
Loading...
Searching...
No Matches
CGAL::Orthtree< GeomTraits > Class Template Reference

#include <CGAL/Orthtree.h>

Definition

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
GeomTraitsmust be a model of OrthtreeTraits or OrthtreeTraitsWithData.
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.

Traits Types

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.
 

Public Types

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).
 

Constructor

 Orthtree (Traits traits)
 constructs an orthtree for a traits instance.
 
template<class ... Args, class = std::enable_if_t<sizeof...(Args)>= 2>
 Orthtree (Args &&... args)
 constructs an orthtree from a set of arguments provided to the traits constructor
 
 Orthtree (const Orthtree &other)
 copy constructor
 
 Orthtree (Orthtree &&other)
 move constructor
 

Tree Building

void refine (const Split_predicate &split_predicate)
 recursively subdivides the orthtree until it meets the given criteria.
 
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 contained elements in a node as split predicate.
 
void grade ()
 refines the orthtree such that the difference of depth between two immediate neighbor leaves is never more than 1.
 

Accessors

const Traits & traits () const
 provides direct read-only access to the tree traits.
 
const Kernelgeom_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.
 

Custom Properties

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.
 

Queries

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.
 

Operators

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

Node Access

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_indexnext_sibling (Node_index n) const
 finds the next sibling in the parent of the node specified by the index n.
 
const std::optional< Node_indexnext_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_indexfirst_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_indexadjacent_node (Node_index n, const Local_coordinates &direction) const
 finds the directly adjacent node in a specific direction
 
std::optional< Node_indexadjacent_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.
 

Member Typedef Documentation

◆ Global_coordinates

template<typename GeomTraits >
using CGAL::Orthtree< GeomTraits >::Global_coordinates = std::array<std::uint32_t, dimension>

Coordinates representing this node's relationship with the rest of the tree.

Each value (x, y, z, ...) of global coordinates is calculated by doubling the parent's global coordinates and adding the local coordinates.

◆ Local_coordinates

template<typename GeomTraits >
using CGAL::Orthtree< GeomTraits >::Local_coordinates = std::bitset<dimension>

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.

Constructor & Destructor Documentation

◆ Orthtree()

template<typename GeomTraits >
CGAL::Orthtree< GeomTraits >::Orthtree ( Traits  traits)
explicit

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
traitsthe traits object.

Member Function Documentation

◆ add_property()

template<typename GeomTraits >
template<typename T >
std::pair< Property_map< T >, bool > CGAL::Orthtree< GeomTraits >::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 Parameters
Tthe type of the property to add
Parameters
namethe name of the new property
default_valuethe default value assigned to nodes for this property
Returns
pair of the property map and a Boolean which is true if the property needed to be created

◆ adjacent_node() [1/2]

template<typename GeomTraits >
std::optional< Node_index > CGAL::Orthtree< GeomTraits >::adjacent_node ( Node_index  n,
Adjacency  adjacency 
) const

equivalent to adjacent_node(), with an adjacency direction rather than a bitset.

Parameters
nindex of the node to find a neighbor of
adjacencywhich way to find the adjacent node relative to this one

◆ adjacent_node() [2/2]

template<typename GeomTraits >
std::optional< Node_index > CGAL::Orthtree< GeomTraits >::adjacent_node ( Node_index  n,
const Local_coordinates direction 
) const

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
nindex of the node to find a neighbor of
directionwhich 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.

◆ barycenter()

template<typename GeomTraits >
Point CGAL::Orthtree< GeomTraits >::barycenter ( Node_index  n) const

returns the center point of a node.

Parameters
nindex of the node to find the center point for
Returns
the center point of node n

◆ bbox()

template<typename GeomTraits >
Bbox CGAL::Orthtree< GeomTraits >::bbox ( Node_index  n) const

constructs the bounding box of a node.

Note
The object constructed is not the bounding box of the node's contents, but the bounding box of the node itself.
Parameters
nnode to generate a bounding box for
Returns
the bounding box of the node n

◆ child()

template<typename GeomTraits >
Node_index CGAL::Orthtree< GeomTraits >::child ( Node_index  n,
std::size_t  i 
) const

returns a node's ith child.

Precondition
!is_leaf()
Parameters
nindex of the node to retrieve the child of
iin [0, 2^D) specifying the child to retrieve
Returns
the index of the ith child of node n

◆ deepest_first_child()

template<typename GeomTraits >
Node_index CGAL::Orthtree< GeomTraits >::deepest_first_child ( Node_index  n) const

finds the leaf node reached when descending the tree and always choosing child 0.

This is the starting point of a depth-first traversal.

Parameters
nthe index of the node to find the deepest first child of.
Returns
the index of the deepest first child of node n.

◆ depth()

template<typename GeomTraits >
std::size_t CGAL::Orthtree< GeomTraits >::depth ( Node_index  n) const

determines the depth of the node specified.

The root node has depth 0, its children have depth 1, and so on.

Parameters
nindex of the node to check.
Returns
the depth of the node n within its tree.

◆ descendant()

template<typename GeomTraits >
template<typename... Indices>
Node_index CGAL::Orthtree< GeomTraits >::descendant ( Node_index  node,
Indices...  indices 
) const

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
nodethe node to descend
indicesthe integer indices specifying the descent to perform
Returns
the index of the specified descendant node

◆ first_child_at_depth()

template<typename GeomTraits >
std::optional< Node_index > CGAL::Orthtree< GeomTraits >::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.

Similar to deepest_first_child(), but does go to a fixed depth.

Parameters
nthe index of the node to find the dth first child of.
dthe depth to descend to.
Returns
the index of the dth first child, nothing if the tree is not deep enough.

◆ grade()

template<typename GeomTraits >
void CGAL::Orthtree< GeomTraits >::grade ( )

refines the orthtree such that the difference of depth between two immediate neighbor leaves is never more than 1.

This is done only by adding nodes, nodes are never removed.

◆ intersected_nodes()

template<typename GeomTraits >
template<typename Query , typename OutputIterator >
OutputIterator CGAL::Orthtree< GeomTraits >::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 leaf nodes and writes their indices to the output iterator.

Template Parameters
Querythe primitive class (e.g., sphere, ray)
OutputIteratora model of OutputIterator that accepts Node_index types
Parameters
querythe intersecting primitive.
outputoutput iterator.
Returns
the output iterator after writing

◆ is_topology_equal() [1/2]

template<typename GeomTraits >
static bool CGAL::Orthtree< GeomTraits >::is_topology_equal ( const Self lhs,
const Self rhs 
)
static

helper function for calling is_topology_equal() on the root nodes of two trees.

Parameters
lhsan Orthtree
rhsanother Orthtree
Returns
true if lhs and rhs have the same topology, and false otherwise

◆ is_topology_equal() [2/2]

template<typename GeomTraits >
static bool CGAL::Orthtree< GeomTraits >::is_topology_equal ( Node_index  lhsNode,
const Self lhsTree,
Node_index  rhsNode,
const Self rhsTree 
)
static

determines whether a pair of subtrees have the same topology.

Parameters
lhsNodeindex of a node in lhsTree
lhsTreean Orthtree
rhsNodeindex of a node in rhsTree
rhsTreeanother Orthtree
Returns
true if lhsNode and rhsNode have the same topology, false otherwise

◆ locate()

template<typename GeomTraits >
Node_index CGAL::Orthtree< GeomTraits >::locate ( const Point point) const

finds the leaf node which contains a particular point in space.

Traverses the orthtree and finds the leaf 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). The point is contained in the lower cell of each direction if its coordinate is lower than the center.

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

◆ nearest_k_neighbors()

template<typename GeomTraits >
template<typename OutputIterator >
auto CGAL::Orthtree< GeomTraits >::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.

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

Template Parameters
OutputIteratora model of OutputIterator that accepts GeomTraits::Node_data_element objects.
Parameters
queryquery point
knumber of neighbors to find
outputoutput iterator
Warning
Nearest neighbor searches requires GeomTraits to be a model of CollectionPartitioningOrthtreeTraits.

◆ nearest_k_neighbors_within_radius()

template<typename GeomTraits >
template<typename OutputIterator >
auto CGAL::Orthtree< GeomTraits >::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.

This function is useful when the user already knows how sparse the elements are, or if they do not care about elements that are too far away. Setting a small radius may have performance benefits.

Template Parameters
OutputIteratormust be a model of OutputIterator that accepts GeomTraits::Node_data_element
Parameters
querythe region to search within
kthe number of elements to find
outputthe output iterator to add the found elements to (in order of increasing distance)
Warning
Nearest neighbor searches requires GeomTraits to be a model of CollectionPartitioningOrthtreeTraits.

◆ neighbors_within_radius()

template<typename GeomTraits >
template<typename OutputIterator >
auto CGAL::Orthtree< GeomTraits >::neighbors_within_radius ( const Sphere query,
OutputIterator  output 
) const -> std::enable_if_t<supports_neighbor_search, OutputIterator>

finds the elements in the sphere query.

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

Template Parameters
OutputIteratora model of OutputIterator that accepts GeomTraits::Node_data_element objects.
Parameters
queryquery sphere
outputoutput iterator
Warning
Nearest neighbor searches requires GeomTraits to be a model of CollectionPartitioningOrthtreeTraits.

◆ next_sibling()

template<typename GeomTraits >
const std::optional< Node_index > CGAL::Orthtree< GeomTraits >::next_sibling ( Node_index  n) const

finds the next sibling in the parent of the node specified by the index n.

Traverses the tree in increasing order of local index (e.g., 000, 001, 010, etc.)

Parameters
nthe index of the node to find the sibling of
Returns
the index of the next sibling of n if n is not the last node in its parent, otherwise std::nullopt.

◆ next_sibling_up()

template<typename GeomTraits >
const std::optional< Node_index > CGAL::Orthtree< GeomTraits >::next_sibling_up ( Node_index  n) const

finds the next sibling of the parent of the node specified by n if it exists.

Parameters
nthe index node to find the sibling up of.
Returns
The index of the next sibling of the parent of n if n is not the root and its parent has a sibling, otherwise nothing.

◆ node()

template<typename GeomTraits >
template<typename... Indices>
Node_index CGAL::Orthtree< GeomTraits >::node ( Indices...  indices) const

convenience function for retrieving arbitrary nodes.

Equivalent to tree.descendant(tree.root(), indices...).

Parameters
indicesthe integer indices specifying the descent to perform, starting from the root
Returns
the index of the specified node

◆ operator!=()

template<typename GeomTraits >
bool CGAL::Orthtree< GeomTraits >::operator!= ( const Self rhs) const

compares the topology of the orthtree with that of rhs.

Parameters
rhsthe other orthtree
Returns
false if the trees have the same topology, and true otherwise

◆ operator==()

template<typename GeomTraits >
bool CGAL::Orthtree< GeomTraits >::operator== ( const Self rhs) const

compares the topology of the orthtree with that of rhs.

Trees may be considered equivalent even if they have different contents. Equivalent trees must have the same root bounding box and the same node structure.

Parameters
rhsthe other orthtree
Returns
true if the trees have the same topology, and false otherwise

◆ parent()

template<typename GeomTraits >
Node_index CGAL::Orthtree< GeomTraits >::parent ( Node_index  n) const

returns this n's parent.

Precondition
!is_root()
Parameters
nindex of the node to retrieve the parent of
Returns
the index of the parent of node n

◆ property()

template<typename GeomTraits >
template<typename T >
std::optional< Property_map< T > > CGAL::Orthtree< GeomTraits >::property ( const std::string &  name) const

gets a property of the nodes if it exists.

Template Parameters
Tthe type of the property to retrieve
Parameters
namethe name of the property
Returns
an optional containing the property map if it exists

◆ refine() [1/2]

template<typename GeomTraits >
void CGAL::Orthtree< GeomTraits >::refine ( const Split_predicate split_predicate)

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_predicatedetermines whether or not a leaf node needs to be subdivided.

◆ refine() [2/2]

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_depthdeepest a tree is allowed to be (nodes at this depth will not be split).
bucket_sizemaximum number of items a node is allowed to contain.

◆ remove_property()

template<typename GeomTraits >
template<typename T >
bool CGAL::Orthtree< GeomTraits >::remove_property ( Property_map< T >  property)

removes the node property from the tree.

Template Parameters
Tthe type of the property to remove
Parameters
propertythe property to be removed from the tree.
Returns
true if property was a valid property of the tree.

◆ split()

template<typename GeomTraits >
void CGAL::Orthtree< GeomTraits >::split ( Node_index  n)

splits a node into subnodes.

Only leaf nodes should be split. When a node is split it is no longer a leaf node. The full set of degree children are constructed automatically, and their values are set. Contents of this node are not propagated automatically, this is responsibility of the distribute_node_contents_object in the traits class.

Parameters
nindex of the node to split

◆ traverse() [1/2]

template<typename GeomTraits >
template<typename Traversal , typename ... Args>
Node_index_range CGAL::Orthtree< GeomTraits >::traverse ( Args &&...  args) const

convenience method for using a traversal without constructing it yourself

Template Parameters
Traversala model of OrthtreeTraversal
Parameters
argsArguments to to pass to the traversal's constructor, excluding the first (always an orthtree reference)
Returns
a ForwardRange over the node indices of the tree

◆ traverse() [2/2]

template<typename GeomTraits >
template<typename Traversal >
Node_index_range CGAL::Orthtree< GeomTraits >::traverse ( Traversal  traversal) const

constructs a node index range using a tree-traversal function.

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

Template Parameters
Traversala model of OrthtreeTraversal
Parameters
traversalclass defining the traversal strategy
Returns
a ForwardRange over the node indices of the tree