CGAL 5.5 - Quadtrees, Octrees, and Orthtrees
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, PointMapEnclosing
 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. More...
 
typedef std::array< std::uint32_t, Dimension::value > Global_coordinates
 Coordinates representing this node's relationship with the rest of the tree. More...
 
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. More...
 
bool is_leaf () const
 returns true if the node has no children, false otherwise. More...
 
std::uint8_t depth () const
 returns this node's depth. More...
 
Local_coordinates local_coordinates () const
 returns this node's local coordinates (in relation to its parent). More...
 
Global_coordinates global_coordinates () const
 returns this node's global coordinates. More...
 

Adjacency

Self parent () const
 returns this node's parent. More...
 
Self operator[] (std::size_t index) const
 returns the nth child fo this node. More...
 
Self adjacent_node (Local_coordinates direction) const
 finds the directly adjacent node in a specific direction More...
 
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
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 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 fo 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()