G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node Class Reference

Public Member Functions
	Node ()
	Creates node with nullptr children. More...
	Node (const Node &other)
	Doesn't clone children. More...
	Node (const Array< Handle > &pt)
	Copies the specified subarray of pt into point, NULLs the children. More...
	~Node ()
	Deletes the children (but not the values) More...
void	assignSplitBounds (const AABox &myBounds)
	Recurse through the tree, assigning splitBounds fields. More...
Node *	findDeepestContainingNode (const Vector3 &point)
	Returns the deepest node that completely contains bounds. More...
void	getHandles (Array< Handle > &handleArray) const
	Recursively appends all handles and children's handles to the array. More...
void	getIntersectingMembers (const AABox &sphereBounds, const Sphere &sphere, Array< T > &members) const
	Appends all members that intersect the box. More...
void	getIntersectingMembers (const AABox &box, const Sphere &sphere, Array< T > &members, bool useSphere) const
	Appends all members that intersect the box. More...
bool	isLeaf () const
	Returns true if this node is a leaf (no children) More...
void	verifyNode (const Vector3 &lo, const Vector3 &hi)

Static Public Member Functions
static Node *	deserializeStructure (BinaryInput &bi)
	Clears the member table. More...
static void	serializeStructure (const Node *n, BinaryOutput &bo)
	Stores the locations of the splitting planes (the structure but not the content) so that the tree can be quickly rebuilt from a previous configuration without calling balance. More...

Public Attributes
Node *	child [2]
	child[0] contains all values strictly smaller than splitLocation along splitAxis. More...
Vector3::Axis	splitAxis
AABox	splitBounds
	Spatial bounds on all values at this node and its children, based purely on the parent's splitting planes. More...
float	splitLocation
	Location along the specified axis. More...
Array< Handle >	valueArray
	Values if this is a leaf node). More...

Constructor & Destructor Documentation

Node() [1/3]

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::Node ( )

inline

Creates node with nullptr children.

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::deserializeStructure().

Node() [2/3]

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::Node ( const Node &  other )

inline

Doesn't clone children.

Node() [3/3]

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::Node ( const Array< Handle > &  pt )

inline

Copies the specified subarray of pt into point, NULLs the children.

Assumes a second pass will set splitBounds.

~Node()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::~Node ( )

inline

Deletes the children (but not the values)

Member Function Documentation

assignSplitBounds()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::assignSplitBounds ( const AABox &  myBounds )

inline

Recurse through the tree, assigning splitBounds fields.

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::assignSplitBounds(), and G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::balance().

deserializeStructure()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

static Node* G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::deserializeStructure ( BinaryInput &  bi )

inlinestatic

Clears the member table.

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::deserializeStructure().

findDeepestContainingNode()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

Node* G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::findDeepestContainingNode ( const Vector3 &  point )

inline

Returns the deepest node that completely contains bounds.

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::findDeepestContainingNode(), and G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::insert().

getHandles()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::getHandles ( Array< Handle > &  handleArray ) const

inline

Recursively appends all handles and children's handles to the array.

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::balance(), and G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::getHandles().

getIntersectingMembers() [1/2]

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::getIntersectingMembers ( const AABox &  sphereBounds, const Sphere &  sphere, Array< T > &  members  ) const

inline

Appends all members that intersect the box.

If useSphere is true, members are tested against the sphere instead.

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::getIntersectingMembers(), and G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::getIntersectingMembers().

getIntersectingMembers() [2/2]

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::getIntersectingMembers ( const AABox &  box, const Sphere &  sphere, Array< T > &  members, bool  useSphere  ) const

inline

Appends all members that intersect the box.

If useSphere is true, members are tested against the sphere instead.

Implemented using both box and sphere tests to simplify the implementation of a future beginSphereInteresection iterator using the same underlying BoxIterator class.

isLeaf()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

bool G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::isLeaf ( ) const

inline

Returns true if this node is a leaf (no children)

serializeStructure()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

static void G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::serializeStructure ( const Node *  n, BinaryOutput &  bo  )

inlinestatic

Stores the locations of the splitting planes (the structure but not the content) so that the tree can be quickly rebuilt from a previous configuration without calling balance.

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::serializeStructure().

verifyNode()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::verifyNode ( const Vector3 &  lo, const Vector3 &  hi  )

inline

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::balance(), and G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::verifyNode().

Member Data Documentation

child

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

Node* G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::child[2]

child[0] contains all values strictly smaller than splitLocation along splitAxis.

child[1] contains all values strictly larger.

Both may be nullptr if there are not enough values to bother recursing.

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::assignSplitBounds(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::clearData(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::cloneTree(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::deserializeStructure(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::findDeepestContainingNode(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::getHandles(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::getIntersectingMembers(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::isLeaf(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::makeNode(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::Node(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator++(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::serializeStructure(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::verifyNode(), and G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::~Node().

splitAxis

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

Vector3::Axis G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::splitAxis

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::assignSplitBounds(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::deserializeStructure(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::findDeepestContainingNode(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::getIntersectingMembers(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::makeNode(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::Node(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator++(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::serializeStructure(), and G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::verifyNode().

splitBounds

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

AABox G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::splitBounds

Spatial bounds on all values at this node and its children, based purely on the parent's splitting planes.

May be infinite

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::assignSplitBounds(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::deserializeStructure(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::Node(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::serializeStructure(), and G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::verifyNode().

splitLocation

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

float G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::splitLocation

Location along the specified axis.

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::assignSplitBounds(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::deserializeStructure(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::findDeepestContainingNode(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::getIntersectingMembers(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::makeNode(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::Node(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator++(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::serializeStructure(), and G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::verifyNode().

valueArray

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

Array<Handle> G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::valueArray

Values if this is a leaf node).

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::clearData(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::cloneTree(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::getHandles(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::getIntersectingMembers(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::insert(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::makeNode(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::Node(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator*(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator++(), and G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::verifyNode().