CGAL 6.2 - Quadtrees, Octrees, and Orthtrees

Loading...
Searching...
No Matches
List of all members
CGAL::Orthtree< GeomTraits > Class Template Reference
Reference Manual

`#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 | 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 bool | supports_ball_search = bool_value
| `true` if `GeomTraits` provides a `Has_on_bounded_side` functor 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.
template<typename Orthtree = Self>
auto | refine (size_t max_depth=10, size_t bucket_size=20) -> std::enable_if_t< Orthtree::has_data, void >
| 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 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.

## 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 , typename Orthtree = Self>
auto | nearest_k_neighbors (const Point &query, std::size_t k, OutputIterator output) const -> std::enable_if_t< Orthtree::supports_neighbor_search, OutputIterator >
| finds the `k` nearest neighbors of the point `query`.
template<typename OutputIterator , typename Orthtree = Self>
auto | neighbors_within_radius (const Sphere &query, OutputIterator output) const -> std::enable_if_t< Orthtree::supports_neighbor_search, OutputIterator >
| finds the elements in the sphere `query`.
template<typename OutputIterator , typename Orthtree = Self>
auto | nearest_k_neighbors_within_radius (const Sphere &query, std::size_t k, OutputIterator output) const -> std::enable_if_t< Orthtree::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.
template<typename OutputIterator >
auto | intersected_nodes (const Point &center, const FT squared_radius, OutputIterator output) const -> std::enable_if_t< Orthtree::supports_ball_search, OutputIterator >
| finds the leaf nodes that intersect with a ball.
template<typename Query , typename OutputIterator , typename IntersectionFunctor >
OutputIterator | intersected_nodes (const Query &query, OutputIterator output, IntersectionFunctor &func) 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) 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.

## 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 `i`th 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 `i`th 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
| ) |  | 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

  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 `d`th 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() [1/3]

template<typename GeomTraits >
template<typename OutputIterator >

auto CGAL::Orthtree< GeomTraits >::intersected_nodes | ( | const Point & | center,
|  | const FT | squared_radius,
|  | OutputIterator | output
| ) |  | const -> std::enable_if_t<Orthtree::supports_ball_search, OutputIterator>

finds the leaf nodes that intersect with a ball.

This function finds all the intersecting leaf nodes and writes their indices to the output iterator. Requires the Traits class to provide the functor via `has_on_bounded_side_object()` with an operator:

`bool operator()(Traits::Sphere_d, Traits::Bbox_d)`

`Kernel::HasOnUnboundedSide_2` and `Kernel::HasOnUnboundedSide_3` are compatible concepts for dimensions 2 and 3.

Template Parameters

  OutputIterator | a model of `OutputIterator` that accepts `Node_index` types

Parameters

  center | the center of the ball
  squared_radius | the squared radius of the ball
  output | output iterator.

Returns
  the output iterator after writing

## ◆ intersected_nodes() [2/3]

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., plane, 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

## ◆ intersected_nodes() [3/3]

template<typename GeomTraits >
template<typename Query , typename OutputIterator , typename IntersectionFunctor >

OutputIterator CGAL::Orthtree< GeomTraits >::intersected_nodes | ( | const Query & | query,
|  | OutputIterator | output,
|  | IntersectionFunctor & | func
| ) |  | const

finds the leaf nodes that intersect with any primitive.

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
  IntersectionFunctor | a functor that is invoked on each node while traversing the tree to determine intersection must be of type `bool(const Query&, const Traits::Bbox_d&)`

Parameters

  query | the intersecting primitive.
  output | output iterator.
  func | the intersection functor.

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 , typename Orthtree = Self>

auto CGAL::Orthtree< GeomTraits >::nearest_k_neighbors | ( | const Point & | query,
|  | std::size_t | k,
|  | OutputIterator | output
| ) |  | const -> std::enable_if_t<Orthtree::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 , typename Orthtree = Self>

auto CGAL::Orthtree< GeomTraits >::nearest_k_neighbors_within_radius | ( | const Sphere & | query,
|  | std::size_t | k,
|  | OutputIterator | output
| ) |  | const -> std::enable_if_t<Orthtree::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 , typename Orthtree = Self>

auto CGAL::Orthtree< GeomTraits >::neighbors_within_radius | ( | const Sphere & | query,
|  | OutputIterator | output
| ) |  | const -> std::enable_if_t<Orthtree::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 | ) | const

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 >
template<typename Orthtree = Self>

auto CGAL::Orthtree< GeomTraits >::refine | ( | size_t | max_depth = `10`,
|  | size_t | bucket_size = `20`
| ) |  | -> std::enable_if_t<Orthtree::has_data, void>

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