#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

GeomTraits must 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	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.

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 `i`th child.

template<typename... Indices>
Node_index	descendant (Node_index node, Indices... indices)
	retrieves an arbitrary descendant of the node specified by `node`.

template<typename... Indices>
Node_index	node (Indices... indices)
	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.

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

traits the 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

T	the type of the property to add

Parameters

name	the name of the new property
default_value	the 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

n	index of the node to find a neighbor of
adjacency	which 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

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.

◆ barycenter()

template<typename GeomTraits >

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

returns the center point of a node.

Parameters

n	index 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

n	node 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

n	index of the node to retrieve the child of
i	in [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

n	the 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

n	index 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
	)

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

◆ 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

n	the index of the node to find the `d`th first child of.
d	the 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

Query	the primitive class (e.g., sphere, ray)
OutputIterator	a model of `OutputIterator` that accepts `Node_index` types

Parameters

query	the intersecting primitive.
output	output 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

lhs	an Orthtree
rhs	another 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

lhsNode	index of a node in lhsTree
lhsTree	an Orthtree
rhsNode	index of a node in rhsTree
rhsTree	another 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

point query 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

OutputIterator a model of OutputIterator that accepts GeomTraits::Node_data_element objects.

Parameters

query	query point
k	number of neighbors to find
output	output 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

OutputIterator must be a model of OutputIterator that accepts GeomTraits::Node_data_element

Parameters

query	the region to search within
k	the number of elements to find
output	the 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

OutputIterator a model of OutputIterator that accepts GeomTraits::Node_data_element objects.

Parameters

query	query sphere
output	output 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

n	the 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

n	the 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 )

convenience function for retrieving arbitrary nodes.

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

Parameters

indices the 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

rhs	the 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

rhs	the 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

n	index 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

T	the type of the property to retrieve

Parameters

name	the 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_predicate determines 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_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.

◆ 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

T	the type of the property to remove

Parameters

property the 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

n	index 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

Traversal a model of OrthtreeTraversal

Parameters

args	Arguments 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

Traversal a model of OrthtreeTraversal

Parameters

traversal class defining the traversal strategy

Returns: a ForwardRange over the node indices of the tree

Definition

Traits Types

Public Types

Constructor

Tree Building

Accessors

Custom Properties

Queries

Operators

Node Access

Member Typedef Documentation

◆ Global_coordinates

◆ Local_coordinates

Constructor & Destructor Documentation

◆ Orthtree()

Member Function Documentation

◆ add_property()

◆ adjacent_node() [1/2]

◆ adjacent_node() [2/2]

◆ barycenter()

◆ bbox()

◆ child()

◆ deepest_first_child()

◆ depth()

◆ descendant()

◆ first_child_at_depth()

◆ grade()

◆ intersected_nodes()

◆ is_topology_equal() [1/2]

◆ is_topology_equal() [2/2]

◆ locate()

◆ nearest_k_neighbors()

◆ nearest_k_neighbors_within_radius()

◆ neighbors_within_radius()

◆ next_sibling()

◆ next_sibling_up()

◆ node()

◆ operator!=()

◆ operator==()

◆ parent()

◆ property()

◆ refine() [1/2]

◆ refine() [2/2]

◆ remove_property()

◆ split()

◆ traverse() [1/2]

◆ traverse() [2/2]