CGAL 5.6.3 - Quadtrees, Octrees, and Orthtrees

Loading...
Searching...
No Matches
List of all members
CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::Node Class Reference

`#include <CGAL/Orthtree/Node.h>`

## Definition

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

represents a single node of the tree.

Alternatively referred to as a cell, orthant, or sub-tree.

A `Node` is a lightweight object and thus generally passed by copy. It is also a model of `ConstRange` with value type `Traits::Point_d`.

Is Model Of:
  `ConstRange`

## Types
typedef Orthtree< Traits, PointRange, PointMap > | Enclosing
| Orthtree type (enclosing class).
typedef Enclosing::Dimension | Dimension
| Dimension type.
typedef Enclosing::Degree | Degree
| Degree type.
typedef Orthtree< Traits, PointRange, PointMap >::Node | Self
| Self typedef for convenience.
typedef std::bitset< Dimension::value > | Local_coordinates
| Set of bits representing this node's relationship to its parent.
typedef std::array< std::uint32_t, Dimension::value > | Global_coordinates
| Coordinates representing this node's relationship with the rest of the tree.
typedef PointRange::const_iterator | const_iterator
| constant iterator type.
typedef Traits::Adjacency | Adjacency
| Adjacency directions.

## Type & Location
bool | is_null () const
| returns `true` if the node is null, `false` otherwise.
bool | is_root () const
| returns `true` if the node has no parent, `false` otherwise.
bool | is_leaf () const
| returns `true` if the node has no children, `false` otherwise.
std::uint8_t | depth () const
| returns this node's depth.
Local_coordinates | local_coordinates () const
| returns this node's local coordinates (in relation to its parent).
Global_coordinates | global_coordinates () const
| returns this node's global coordinates.

## Adjacency
Self | parent () const
| returns this node's parent.
Self | operator[] (std::size_t index) const
| returns the nth child of this node.
Self | adjacent_node (Local_coordinates direction) const
| finds the directly adjacent node in a specific direction
Self | adjacent_node (Adjacency adjacency) const
| equivalent to `adjacent_node()`, with an adjacency direction rather than a bitset.

## Point Range
bool | empty () const
| checks whether the node is empty of points or not.
std::size_t | size () const
| returns the number of points of this node.
const_iterator | begin () const
| returns the iterator at the start of the collection of points held by this node.
const_iterator | end () const
| returns the iterator at the end of the collection of points held by this node.

## Member Typedef Documentation

## ◆ Global_coordinates

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

typedef std::array<std::uint32_t, Dimension::value> CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::Node::Global_coordinates

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 Traits_ , typename PointRange_ , typename PointMap_ = Identity_property_map<typename Traits_::Point_d>>

typedef std::bitset<Dimension::value> CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::Node::Local_coordinates

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.

## Member Function Documentation

## ◆ adjacent_node()

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

Self CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::Node::adjacent_node | ( | Local_coordinates | direction | ) | const

finds the directly adjacent node in a specific direction

Precondition
  `!is_null()`
  `direction.to_ulong < 2 * Dimension::value`

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::value` 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

  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 adjacent node if it exists, a null node otherwise.

## ◆ depth()

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

std::uint8_t CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::Node::depth | ( |  | ) | const

returns this node's depth.

Precondition
  `!is_null()`

## ◆ global_coordinates()

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

Global_coordinates CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::Node::global_coordinates | ( |  | ) | const

returns this node's global coordinates.

Precondition
  `!is_null()`

## ◆ is_leaf()

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

bool CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::Node::is_leaf | ( |  | ) | const

returns `true` if the node has no children, `false` otherwise.

Precondition
  `!is_null()`

## ◆ is_root()

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

bool CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::Node::is_root | ( |  | ) | const

returns `true` if the node has no parent, `false` otherwise.

Precondition
  `!is_null()`

## ◆ local_coordinates()

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

Local_coordinates CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::Node::local_coordinates | ( |  | ) | const

returns this node's local coordinates (in relation to its parent).

Precondition
  `!is_null()`

## ◆ operator[]()

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

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

returns the nth child of this node.

Precondition
  `!is_null()`
  `!is_leaf()`
  `0 <= index && index < Degree::value`

The orthtree subdivides the space in 2 on each dimension available, so a child node can be accessed by selecting a Boolean value for each dimension. The `index` parameter is thus interpreted as a bitmap, where each bit matches a dimension (starting by the least significant bit for coordinate X).

For example, in the case of an octree (dimension 3):

- index 0 (000 in binary) is the children on the "minimum corner" (xmin, ymin, zmin)
- index 1 (001 in binary) is on (xmax, ymin, zmin)
- index 2 (010 in binary) is on (xmin, ymax, zmin)
- index 6 (101 in binary) is on (xmax, ymin, zmax)

Diagram of a quadtree:

Children of the current node:
Y axis
A
| +-------------------+-------------------+
| | Coord: Ymax Xmin | Coord: Ymax Xmax |
| | Bitmap: 1 0 | Bitmap: 1 1 |
| | | |
| | -> index = 2 | -> index = 3 |
| | | |
| | | |
| | | |
| | | |
| +-------------------+-------------------+
| | Coord: Ymin Xmin | Coord: Ymin Xmax |
| | Bitmap: 0 0 | Bitmap: 0 1 |
| | | |
| | -> index = 0 | -> index = 1 |
| | | |
| | | |
| | | |
| | | |
| +-------------------+-------------------+
|
+--------------------------------------------> X axis
0

The operator can be chained. For example, `n[5][2][3]` returns the third child of the second child of the fifth child of a node `n`.

## ◆ parent()

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

Self CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::Node::parent | ( |  | ) | const

returns this node's parent.

Precondition
  `!is_null()`