|
CGAL 5.4.3 - Quadtrees, Octrees, and Orthtrees
|
|
CGAL 5.4.3 - Quadtrees, Octrees, and Orthtrees
|
#include <CGAL/Orthtree/Node.h>
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.
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. 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. | |
| 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.
| 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.
| Self CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::Node::adjacent_node | ( | Local_coordinates | direction | ) | const |
finds the directly adjacent node in a specific direction
!is_null() direction.to_ulong < 2 * Dimension::valueAdjacent nodes are found according to several properties:
2 * Dimension::value different adjacent nodes (in 3D: left, right, up, down, front, back)Here's a diagram demonstrating the concept for a Quadtree:
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.
| 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. |
| std::uint8_t CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::Node::depth | ( | ) | const |
returns this node's depth.
!is_null() | Global_coordinates CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::Node::global_coordinates | ( | ) | const |
returns this node's global coordinates.
!is_null() | bool CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::Node::is_leaf | ( | ) | const |
returns true if the node has no children, false otherwise.
!is_null() | bool CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::Node::is_root | ( | ) | const |
returns true if the node has no parent, false otherwise.
!is_null() | Local_coordinates CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::Node::local_coordinates | ( | ) | const |
returns this node's local coordinates (in relation to its parent).
!is_null() | Self CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::Node::operator[] | ( | std::size_t | index | ) | const |
returns the nth child fo this node.
!is_null() !is_leaf() 0 <= index && index < Degree::valueThe 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):
Diagram of a quadtree:
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.
| Self CGAL::Orthtree< Traits_, PointRange_, PointMap_ >::Node::parent | ( | ) | const |
returns this node's parent.
!is_null() 
1.8.13