#include <CGAL/Octree/Node.h>

Definition

template<typename Point_index>
class CGAL::Octree::Node< Point_index >

represents a single node of the tree. Alternatively referred to as a cell, octant, or subtree

The role of the node isn't fully stable yet

Template Parameters

Point_index is the datatype the node will contain

Types
enum	Child
	the index of a node relative to its parent (a position defined by the corners of a cube) More...

enum	Direction
	two directions along each axis in cartesian space, relative to a node More...

typedef Node< Point_index >	Self
	self typedef for convenience

typedef std::array< Self, 8 >	Children
	array for containing the child nodes of this node

typedef std::bitset< 3 >	Index
	set of bits representing this node's relationship to its parent More...

typedef std::array< uint32_t, 3 >	Int_location
	coordinate location representing this node's relationship with the rest of the tree More...

typedef boost::iterator_range< Point_index >	Point_range
	a collection of point indices represented by begin and end iterators

Construction
	Node (Self *parent=nullptr, Index index=0)
	creates a new node, optionally as the child of a parent More...

Mutators
void	split ()
	split a node into subnodes More...

void	unsplit ()
	eliminate this node's children, making it a leaf node More...

Child Accessors
Self &	operator[] (int index)
	access the child nodes of this node by their indices More...

const Self &	operator[] (int index) const
	read-only access the child nodes of this node by their indices More...

Property Accessors
const Self *	parent () const
	read-only access to this node's parent More...

const uint8_t &	depth () const
	retrieve this node's depth in the tree More...

Int_location	location () const
	retrieve this node's location in the tree More...

Index	index () const
	retrieve this node's index in relation to its parent More...

bool	is_leaf () const
	determine whether this node is a leaf node More...

bool	is_root () const
	determine whether this node is the root node More...

const Self *	adjacent_node (std::bitset< 3 > direction) const
	find the directly adjacent node in a specific direction More...

const Self *	adjacent_node (Direction direction) const
	equivalent to adjacent_node, with a Direction rather than a bitset

Self *	adjacent_node (std::bitset< 3 > direction)
	equivalent to adjacent_node, except non-const

Self *	adjacent_node (Direction direction)
	equivalent to adjacent_node, with a Direction rather than a bitset and non-const

Value Accessors
Point_range &	points ()
	access to the content held by this node More...

const Point_range &	points () const
	read-only access to the content held by this node More...

bool	empty () const
	check whether this node contains any points More...

std::size_t	size () const
	count the points contained by this node More...

Operators
bool	operator== (const Self &rhs) const
	compare the topology of this node to another node More...

bool	operator!= (const Self &rhs) const
	compares the topology of this node to another node More...

Member Typedef Documentation

◆ Index

template<typename Point_index >

typedef std::bitset<3> CGAL::Octree::Node< Point_index >::Index

set of bits representing this node's relationship to its parent

Equivalent to an array of three booleans, where index[0] is whether x is greater, index[1] is whether y is greater, and index[2] is whether z is greater. Used to represent a node's relationship to the center of its parent.

◆ Int_location

template<typename Point_index >

typedef std::array<uint32_t, 3> CGAL::Octree::Node< Point_index >::Int_location

coordinate location representing this node's relationship with the rest of the tree

Each value (x, y, z) of a location is calculated by doubling the parent's location and adding the Index.

Todo:: Maybe I should add an example?

Member Enumeration Documentation

◆ Child

template<typename Point_index >

enum CGAL::Octree::Node::Child

the index of a node relative to its parent (a position defined by the corners of a cube)

Corners are mapped to numbers as 3-bit integers, in "zyx" order.

For example:

right-top-back --> x=1, y=1, z=0 --> zyx = 011 --> 3

The following diagram may be a useful reference:

      6          7
       +--------+
      /|       /|             y+
     / |      / |             *  z+
  2 +--------+ 3|             | *
    |  |     |  |             |/
    |  +-----|--+             +-----* x+
    | / 4    | / 5
    |/       |/
    +--------+
  0           1

This lookup table may also be helpful:

Child	bitset	number	Enum
left, bottom, back	000	0	LEFT_BOTTOM_BACK
right, bottom, back	001	1	RIGHT_BOTTOM_BACK
left, top, back	010	2	LEFT_TOP_BACK
right, top, back	011	3	RIGHT_TOP_BACK
left, bottom, front	100	4	LEFT_BOTTOM_FRONT
right, bottom, front	101	5	RIGHT_BOTTOM_FRONT
left, top, front	110	6	LEFT_TOP_FRONT
right, top, front	111	7	RIGHT_TOP_FRONT

◆ Direction

template<typename Point_index >

enum CGAL::Octree::Node::Direction

two directions along each axis in cartesian space, relative to a node

Directions are mapped to numbers as 3-bit integers, though the numbers 6 and 7 are not used because there are only 6 different directions.

The first two bits indicate the axis (00 = x, 01 = y, 10 = z), the third bit indicates the direction along that axis (0 = -, 1 = +).

The following diagram may be a useful reference:

       3 *
         |  * 5
         | /                  y+
         |/                   *  z+
0 *------+------* 1           | *
        /|                    |/
       / |                    +-----* x+
    4 *  |
         * 2

This lookup table may also be helpful:

Direction	bitset	number	Enum
`-x`	000	0	LEFT
`+x`	001	1	RIGHT
`-y`	010	2	DOWN
`+y`	011	3	UP
`-z`	100	4	BACK
`+z`	101	5	FRONT

Constructor & Destructor Documentation

◆ Node()

template<typename Point_index >

CGAL::Octree::Node< Point_index >::Node	(	Self *	parent = `nullptr`,
		Index	index = `0`
	)

explicit

creates a new node, optionally as the child of a parent

If no parent is provided, the node created is assumed to be the root of a tree. This means that the parent reference is a nullptr, and the depth is zero. If a parent is provided, the node becomes the child of that parent. In that case, an index should be passed, telling this node its relationship to its parent. Depth and location are automatically determined in the constructor, and should generally be considered immutable after construction.

Parameters

parent	A reference to the node containing this one
index	This node's relationship to its parent

Member Function Documentation

◆ adjacent_node()

template<typename Point_index >

const Self* CGAL::Octree::Node< Point_index >::adjacent_node ( std::bitset< 3 > direction ) const

find the directly adjacent node in a specific direction

Adjacent nodes are found according to several properties:

Adjacent nodes may be larger than the seek node, but never smaller
A node can have no more than 6 different adjacent nodes (left, right, up, down, front, back)
A node is free to have fewer than 6 adjacent nodes (e.g. edge nodes have no neighbors in some directions, the root node has none at all).
Adjacent nodes are not required to be leaf nodes

Here's a diagram demonstrating the concept for a quadtree. Because it's in 2d space, the seek node has only four neighbors (up, down, left, right)

+---------------+---------------+
|               |               |
|               |               |
|               |               |
|       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 a pointer to the adjacent node if it's found. If there is no adjacent node in that direction, it returns nullptr.

Todo:: explain how direction is encoded

Parameters

direction which way to find the adjacent node relative to this one

Returns: a pointer to the adjacent node if it exists

◆ depth()

template<typename Point_index >

const uint8_t& CGAL::Octree::Node< Point_index >::depth ( ) const

retrieve this node's depth in the tree

Returns: the depth of this node, where root has a depth of 0

◆ empty()

template<typename Point_index >

bool CGAL::Octree::Node< Point_index >::empty ( ) const

check whether this node contains any points

Returns: if this node contains no points

◆ index()

template<typename Point_index >

Index CGAL::Octree::Node< Point_index >::index ( ) const

retrieve this node's index in relation to its parent

Returns: the index of this nod3

◆ is_leaf()

template<typename Point_index >

bool CGAL::Octree::Node< Point_index >::is_leaf ( ) const

determine whether this node is a leaf node

Returns: whether this node has no children

◆ is_root()

template<typename Point_index >

bool CGAL::Octree::Node< Point_index >::is_root ( ) const

determine whether this node is the root node

Returns: whether this node has no parent

◆ location()

template<typename Point_index >

Int_location CGAL::Octree::Node< Point_index >::location ( ) const

retrieve this node's location in the tree

Todo:: Should I link to an explanation of the location type?

Returns: this node's location

◆ operator!=()

template<typename Point_index >

bool CGAL::Octree::Node< Point_index >::operator!= ( const Self & rhs ) const

compares the topology of this node to another node

Todo:

Parameters

rhs	node to compare with

Returns: whether the trees have different topology

◆ operator==()

template<typename Point_index >

bool CGAL::Octree::Node< Point_index >::operator== ( const Self & rhs ) const

compare the topology of this node to another node

Todo:

Parameters

rhs	node to compare with

Returns: whether the nodes have different topology

◆ operator[]() [1/2]

template<typename Point_index >

Self& CGAL::Octree::Node< Point_index >::operator[] ( int index )

access the child nodes of this node by their indices

Todo:: Explain how index values map to the Index type

Retrieves a reference to the child node described by the index. The operator can be chained. for example, to access the third child of the second child of the fifth child of a node n

n[5][2][3];

Parameters

index The index of the child node, as an int

Returns: A reference to the node

◆ operator[]() [2/2]

template<typename Point_index >

const Self& CGAL::Octree::Node< Point_index >::operator[] ( int index ) const

read-only access the child nodes of this node by their indices

Parameters

index The index of the child node, as an int

Returns: A const reference to the node

◆ parent()

template<typename Point_index >

const Self* CGAL::Octree::Node< Point_index >::parent ( ) const

read-only access to this node's parent

Ownership of a node is not equivalent to ownership of the entire tree, so it's not possible to obtain write access to a node's parent, only its children. Note that the return type is nullable, attempting to find the parent of a root node will return null.

Todo:: Should I instead assert the node isn't root? (that would make this undefined behavior)

Returns: A const pointer to the parent of this node (possibly nullptr)

◆ points() [1/2]

template<typename Point_index >

Point_range& CGAL::Octree::Node< Point_index >::points ( )

access to the content held by this node

Returns: a reference to the collection of point indices

◆ points() [2/2]

template<typename Point_index >

const Point_range& CGAL::Octree::Node< Point_index >::points ( ) const

read-only access to the content held by this node

Returns: a read-only reference to the collection of point indices

◆ size()

template<typename Point_index >

std::size_t CGAL::Octree::Node< Point_index >::size ( ) const

count the points contained by this node

Returns: the number of points this node owns

◆ split()

template<typename Point_index >

void CGAL::Octree::Node< Point_index >::split ( )

split a node into subnodes

Only leaf nodes should be split. When a node is split it is no longer a leaf node. 8 Children are constructed automatically, and their values are set. Contents of this node are not propagated automatically. It's the responsibility of the caller to redistribute the points contained by a node after splitting

◆ unsplit()

template<typename Point_index >

void CGAL::Octree::Node< Point_index >::unsplit ( )

eliminate this node's children, making it a leaf node

When a node is un-split, its children are automatically deleted. After un-splitting a node it will be considered a leaf node

Definition

template<typename Point_index> class CGAL::Octree::Node< Point_index >

Types

Construction

Mutators

Child Accessors

Property Accessors

Value Accessors

Operators

Member Typedef Documentation

◆ Index

◆ Int_location

Member Enumeration Documentation

◆ Child

◆ Direction

Constructor & Destructor Documentation

◆ Node()

Member Function Documentation

◆ adjacent_node()

◆ depth()

◆ empty()

◆ index()

◆ is_leaf()

◆ is_root()

◆ location()

◆ operator!=()

◆ operator==()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ parent()

◆ points() [1/2]

◆ points() [2/2]

◆ size()

◆ split()

◆ unsplit()

template<typename Point_index>
class CGAL::Octree::Node< Point_index >