CGAL 5.6.3 - Quadtrees, Octrees, and Orthtrees

Loading...
Searching...
No Matches
List of all members | Classes
CGAL::Orthtree< Traits_, PointRange_, PointMap_ > Class Template Reference
Quadtree\, Octree and Orthtree Reference » Classes

`#include <CGAL/Orthtree.h>`

## Definition

template<typename Traits_, typename PointRange_, typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>
class CGAL::Orthtree< Traits_, PointRange_, PointMap_ >

A data structure using an axis-aligned hybercubic decomposition of dD space for efficient point access and computations.

It builds a hierarchy of nodes which subdivide the space based on a collection of points. Each node represents an axis-aligned hypercubic region of space. A node contains the range of points that are present in the region it defines, and it may contain \(2^{dim}\) other nodes which further subdivide the region.

See also
  `CGAL::Quadtree`
  `CGAL::Octree`

Template Parameters

  Traits_ | must be a model of `OrthtreeTraits`
  PointRange_ | must be a model of range whose value type is the key type of `PointMap_`
  PointMap_ | must be a model of `ReadablePropertyMap` whose value type is `Traits_::Point_d`

Examples
  Orthtree/orthtree_build.cpp.

## Classes
class | Node
| represents a single node of the tree. More...

## Template Types
typedef PointRange_ | PointRange
| Point range.
typedef PointMap_ | PointMap
| Point map.

## Traits Types
typedef Traits::Dimension | Dimension
| Dimension of the tree.
typedef Traits::FT | FT
| Number type.
typedef Traits::Point_d | Point
| Point type.
typedef Traits::Bbox_d | Bbox
| Bounding box type.
typedef Traits::Sphere_d | Sphere
| Sphere type.

## Public Types
typedef Orthtree< Traits, PointRange, PointMap > | Self
| Self typedef for convenience.
typedef Dimension_tag<(2<<(Dimension::value-1))> | Degree
| Degree of the tree (number of children of non-leaf nodes).
typedef std::function< bool(Node)> | Split_predicate
| A predicate that determines whether a node must be split when refining a tree.
typedef unspecified_type | Node_range
| A model of `ConstRange` whose value type is `Node`.

## Constructor
| Orthtree (PointRange &point_range, PointMap point_map=PointMap(), const FT enlarge_ratio=1.2, Traits traits=Traits())
| creates an orthtree from a collection of points.

## 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 points 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
Node | root () const
| returns the root node.
Node | operator[] (std::size_t index) const
| Convenience function to access the child nodes of the root node by their indices.
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_range | traverse (const Traversal &traversal=Traversal()) const
| constructs a node range using a tree-traversal function.
Bbox | bbox (const Node &node) const
| constructs the bounding box of a node.

## Queries
Node | locate (const Point &point) const
| finds the leaf node which contains the point `p`.
template<typename OutputIterator >
OutputIterator | nearest_neighbors (const Point &query, std::size_t k, OutputIterator output) const
| finds the `k` nearest neighbors of `query`.
template<typename OutputIterator >
OutputIterator | nearest_neighbors (const Sphere &query, OutputIterator output) const
| finds the points in `sphere`.
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`.

## Constructor & Destructor Documentation

## ◆ Orthtree()

template<typename Traits_ , typename PointRange_ , typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>

CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::Orthtree | ( | PointRange & | point_range,
|  | PointMap | point_map = `PointMap()`,
|  | const FT | enlarge_ratio = `1.2`,
|  | Traits | traits = `Traits()`
| ) |  |

creates an orthtree from a collection of points.

The constructed orthtree has a root node, with no children, that contains the points passed. That root node has a bounding box that encloses all of the points passed, with padding according to the `enlarge_ratio`.

That root node is built as a `n`-cube (square in 2D, cube in 3D, etc.) whose edge size is the longest bounding box edge multiplied by `enlarge_ratio`. Using an `enlarge_ratio>1.0` prevents some points from being exactly on the border of some cells, which can lead to over-refinement.

This single-node orthtree is valid and compatible with all Orthtree functionality, but any performance benefits are unlikely to be realized until `refine()` is called.

Warning
  The input point range is not copied. It is used directly and is rearranged by the `Orthtree`. Altering the point range after creating the orthtree might leave it in an invalid state.

Parameters

  point_range | input point range.
  point_map | property map to access the input points.
  enlarge_ratio | ratio to which the bounding box should be enlarged.
  traits | the traits object.

## Member Function Documentation

## ◆ bbox()

template<typename Traits_ , typename PointRange_ , typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>

Bbox CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::bbox | ( | const Node & | node | ) | const

constructs the bounding box of a node.

Note
  The object constructed is not the bounding box of the point subset inside the node, but the bounding box of the node itself (cubic).

## ◆ intersected_nodes()

template<typename Traits_ , typename PointRange_ , typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>
template<typename Query , typename OutputIterator >

OutputIterator CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::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 nodes and returns them as const pointers.

Template Parameters

  Query | the primitive class (e.g. sphere, ray)
  OutputIterator | a model of `OutputIterator` that accepts `Node` objects

Parameters

  query | the intersecting primitive.
  output | output iterator.

## ◆ locate()

template<typename Traits_ , typename PointRange_ , typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>

Node CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::locate | ( | const Point & | point | ) | const

finds the leaf node which contains the point `p`.

Traverses the orthtree and finds the deepest cell that has a domain enclosing the point passed. The point passed must be within the region enclosed by the orthtree (bbox of the root node).

Parameters

  point | query point.

Returns
  the node which contains the point.

## ◆ nearest_neighbors() [1/2]

template<typename Traits_ , typename PointRange_ , typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>
template<typename OutputIterator >

OutputIterator CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::nearest_neighbors | ( | const Point & | query,
|  | std::size_t | k,
|  | OutputIterator | output
| ) |  | const

finds the `k` nearest neighbors of `query`.

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

Template Parameters

  OutputIterator | a model of `OutputIterator` that accept `Point_d` objects.

Parameters

  query | a query point.
  k | the number of neighbors.
  output | the output iterator.

## ◆ nearest_neighbors() [2/2]

template<typename Traits_ , typename PointRange_ , typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>
template<typename OutputIterator >

OutputIterator CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::nearest_neighbors | ( | const Sphere & | query,
|  | OutputIterator | output
| ) |  | const

finds the points in `sphere`.

Nearest neighbors are outputted in order of increasing distance to the center of `sphere`.

Template Parameters

  OutputIterator | a model of `OutputIterator` that accept `Point_d` objects.

Parameters

  query | query sphere.
  output | output iterator.

## ◆ operator==()

template<typename Traits_ , typename PointRange_ , typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>

bool CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::operator== | ( | const Self & | rhs | ) | const

compares the topology of the orthtree with that of `rhs`.

Trees may be considered equivalent even if they contain different points. Equivalent trees must have the same bounding box and the same node structure. Node structure is evaluated by comparing the root nodes using the node equality operator.

## ◆ operator[]()

template<typename Traits_ , typename PointRange_ , typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>

Node CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::operator[] | ( | std::size_t | index | ) | const

Convenience function to access the child nodes of the root node by their indices.

`my_tree[5]` is equivalent to `my_tree.root()[5]`.

See also
  `Node::operator[]()`

Parameters

  index | the index of the child node.

Returns
  the accessed node.

## ◆ refine() [1/2]

template<typename Traits_ , typename PointRange_ , typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>

void CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::refine | ( | const Split_predicate & | split_predicate | ) |

recursively subdivides the orthtree until it meets the given criteria.

The split predicate is a `std::function` that takes a `Node` and returns a Boolean value (where `true` implies that a `Node` needs to be split, `false` that the `Node` should be a leaf).

This function may be called several times with different predicates: in that case, nodes already split are left unaltered, while nodes that were not split and for which `split_predicate` returns `true` are split.

Parameters

  split_predicate | determines whether or not a node needs to be subdivided.

## ◆ refine() [2/2]

template<typename Traits_ , typename PointRange_ , typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>

void CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::refine | ( | size_t | max_depth = `10`,
|  | size_t | bucket_size = `20`
| ) |  |

Convenience overload that refines an orthtree using a maximum depth and maximum number of points in a node as split predicate.

This is equivalent to calling `refine(Orthtrees::Maximum_depth_and_maximum_number_of_inliers(max_depth, bucket_size))`.

The refinement is stopped as soon as one of the conditions is violated: if a node has more inliers than `bucket_size` but is already at `max_depth`, it is not split. Similarly, a node that is at a depth smaller than `max_depth` but already has fewer inliers than `bucket_size`, it is not split.

Parameters

  max_depth | deepest a tree is allowed to be (nodes at this depth will not be split).
  bucket_size | maximum points a node is allowed to contain.

## ◆ traverse()

template<typename Traits_ , typename PointRange_ , typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>
template<typename Traversal >

Node_range CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::traverse | ( | const Traversal & | traversal = `Traversal()` | ) | const

constructs a node range using a tree-traversal function.

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

Template Parameters

  Traversal | model of `OrthtreeTraversal` that provides functions compatible with the type of the orthree

Parameters

  traversal | the instance of `Traversal` used

Returns
  a forward input iterator over the nodes of the tree