lass::spat::KdTree< ObjectType, ObjectTraits > Class Template Reference

a KD tree for point-like objects More...

#include <kd_tree.h>

Data Structures

class LessDim

class Neighbour

class Node

Public Types

enum { dimension = TObjectTraits::dimension }

typedef KdTree< ObjectType,
ObjectTraits > TSelf

typedef ObjectType TObject

typedef ObjectTraits TObjectTraits

typedef
TObjectTraits::TObjectIterator TObjectIterator

typedef
TObjectTraits::TObjectReference TObjectReference

typedef TObjectTraits::TPoint TPoint

typedef TObjectTraits::TValue TValue

typedef TObjectTraits::TParam TParam

typedef TObjectTraits::TParam TReference

typedef TObjectTraits::TParam TConstReference

typedef std::vector< Neighbour > TNeighbourhood

Public Member Functions

KdTree ()

Constructs an empty k-d tree.

KdTree (TObjectIterator first, TObjectIterator last)

Constructs a k-d tree from objects in range [first, last).

void reset ()

Resets to an empty tree.

void reset (TObjectIterator first, TObjectIterator last)

Resets to a new k-d tree of objects in range [first, last).

Neighbour nearestNeighbour (const TPoint &target) const

Locates the object that's nearest to a target position.

TValue rangeSearch (const TPoint &target, TParam maxRadius, size_t maxCount, TNeighbourhood &neighbourhood) const

Locates objects within a spherical range around a target position.

template<typename OutputIterator >

OutputIterator rangeSearch (const TPoint &target, TParam maxRadius, OutputIterator first) const

Find all objects in a radius of maxRadius of target.

template<typename RandomIterator >

RandomIterator rangeSearch (const TPoint &target, TParam maxRadius, size_t maxCount, RandomIterator first) const

void swap (TSelf &other)

Swap the representation of two k-d trees.

const bool isEmpty () const

returns true if there are no objects in the k-d tree

void clear ()

resest the k-d tree to an empty one.

const TObjectIterator end () const

template<typename RandomAccessIterator >

RandomAccessIterator rangeSearch (const TPoint &target, TParam maxRadius, size_t maxCount, RandomAccessIterator first) const

Find up to a fixed number of objects in a radius of maxRadius of target.

Private Types

enum { dummyAxis_ = TAxis(-1) }

typedef std::vector
< TObjectIterator > TObjectIterators

typedef TObjectIterators::iterator TIteratorIterator

typedef unsigned char TAxis

typedef std::vector< TAxis > TAxes

typedef std::vector< Node > TNodes

Private Member Functions

void buildHeap ()

void balance (size_t index, TIteratorIterator first, TIteratorIterator last)

TAxis findSplitAxis (TIteratorIterator first, TIteratorIterator last) const

void assignNode (size_t index, TObjectIterator object, TAxis splitAxis)

size_t findNode (size_t index, const TPoint &target) const

void doNearestNeighbour (size_t index, const TPoint &target, Neighbour &best) const

template<typename OutputIterator >

OutputIterator doRangeSearch (size_t index, const TPoint &target, TParam squaredRadius, OutputIterator output) const

template<typename RandomIterator >

RandomIterator doRangeSearch (size_t index, const TPoint &target, TReference squaredRadius, size_t maxCount, RandomIterator first, RandomIterator last) const

Static Private Member Functions

static TValue squaredDistance (const TPoint &a, const TPoint &b)

Private Attributes

TNodes heap_

TObjectIterator begin_

TObjectIterator end_

size_t size_

Detailed Description

template<class ObjectType, class ObjectTraits = KdTreeObjectTraits<ObjectType>>
class lass::spat::KdTree< ObjectType, ObjectTraits >

a KD tree for point-like objects

Author:: Bram de Greve [BdG]

the KD tree does NOT own the objects. You must keep them yourself!

Definition at line 86 of file kd_tree.h.

Member Typedef Documentation

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

typedef KdTree<ObjectType, ObjectTraits> lass::spat::KdTree< ObjectType, ObjectTraits >::TSelf

Definition at line 90 of file kd_tree.h.

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

typedef ObjectType lass::spat::KdTree< ObjectType, ObjectTraits >::TObject

Definition at line 92 of file kd_tree.h.

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

typedef ObjectTraits lass::spat::KdTree< ObjectType, ObjectTraits >::TObjectTraits

Definition at line 93 of file kd_tree.h.

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

typedef TObjectTraits::TObjectIterator lass::spat::KdTree< ObjectType, ObjectTraits >::TObjectIterator

Definition at line 95 of file kd_tree.h.

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

typedef TObjectTraits::TObjectReference lass::spat::KdTree< ObjectType, ObjectTraits >::TObjectReference

Definition at line 96 of file kd_tree.h.

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

typedef TObjectTraits::TPoint lass::spat::KdTree< ObjectType, ObjectTraits >::TPoint

Definition at line 97 of file kd_tree.h.

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

typedef TObjectTraits::TValue lass::spat::KdTree< ObjectType, ObjectTraits >::TValue

Definition at line 98 of file kd_tree.h.

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

typedef TObjectTraits::TParam lass::spat::KdTree< ObjectType, ObjectTraits >::TParam

Definition at line 99 of file kd_tree.h.

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

typedef TObjectTraits::TParam lass::spat::KdTree< ObjectType, ObjectTraits >::TReference

Definition at line 100 of file kd_tree.h.

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

typedef TObjectTraits::TParam lass::spat::KdTree< ObjectType, ObjectTraits >::TConstReference

Definition at line 101 of file kd_tree.h.

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

typedef std::vector<Neighbour> lass::spat::KdTree< ObjectType, ObjectTraits >::TNeighbourhood

Definition at line 123 of file kd_tree.h.

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

typedef std::vector<TObjectIterator> lass::spat::KdTree< ObjectType, ObjectTraits >::TObjectIterators [private]

Definition at line 154 of file kd_tree.h.

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

typedef TObjectIterators::iterator lass::spat::KdTree< ObjectType, ObjectTraits >::TIteratorIterator [private]

Definition at line 155 of file kd_tree.h.

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

typedef unsigned char lass::spat::KdTree< ObjectType, ObjectTraits >::TAxis [private]

Definition at line 157 of file kd_tree.h.

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

typedef std::vector<TAxis> lass::spat::KdTree< ObjectType, ObjectTraits >::TAxes [private]

Definition at line 158 of file kd_tree.h.

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

typedef std::vector<Node> lass::spat::KdTree< ObjectType, ObjectTraits >::TNodes [private]

Definition at line 185 of file kd_tree.h.

Member Enumeration Documentation

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

anonymous enum

Enumerator:

dimension

Definition at line 103 of file kd_tree.h.

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

anonymous enum [private]

Enumerator:

dummyAxis_

Definition at line 160 of file kd_tree.h.

Constructor & Destructor Documentation

template<class O , class OT >

lass::spat::KdTree< O, OT >::KdTree ( ) [inline]

Constructs an empty k-d tree.

Definition at line 68 of file kd_tree.inl.

template<class O , class OT >

lass::spat::KdTree< O, OT >::KdTree	(	TObjectIterator	first,
		TObjectIterator	last
	)			`[inline]`

Constructs a k-d tree from objects in range [first, last).

Warning:: [first, last) must stay a valid range during the entire lifespan of the k-d tree!

Definition at line 80 of file kd_tree.inl.

References lass::spat::KdTree< ObjectType, ObjectTraits >::balance(), lass::spat::KdTree< ObjectType, ObjectTraits >::begin_, lass::prim::distance(), lass::spat::KdTree< ObjectType, ObjectTraits >::end_, lass::spat::KdTree< ObjectType, ObjectTraits >::heap_, and lass::spat::KdTree< ObjectType, ObjectTraits >::size_.

Member Function Documentation

template<class O , class OT >

void lass::spat::KdTree< O, OT >::reset ( ) [inline]

Resets to an empty tree.

Definition at line 101 of file kd_tree.inl.

References lass::spat::KdTree< ObjectType, ObjectTraits >::swap().

template<class O , class OT >

void lass::spat::KdTree< O, OT >::reset	(	TObjectIterator	first,
		TObjectIterator	last
	)			`[inline]`

Resets to a new k-d tree of objects in range [first, last).

Warning:: [first, last) must stay a valid range during the entire lifespan of the k-d tree!

Definition at line 113 of file kd_tree.inl.

References lass::spat::KdTree< ObjectType, ObjectTraits >::swap().

template<class O , class OT >

KdTree< O, OT >::Neighbour lass::spat::KdTree< O, OT >::nearestNeighbour ( const TPoint & target ) const [inline]

Locates the object that's nearest to a target position.

Definition at line 125 of file kd_tree.inl.

References lass::spat::KdTree< ObjectType, ObjectTraits >::doNearestNeighbour(), lass::spat::KdTree< ObjectType, ObjectTraits >::end_, lass::spat::KdTree< ObjectType, ObjectTraits >::isEmpty(), and LASS_THROW.

template<class O , class OT >

KdTree< O, OT >::TValue lass::spat::KdTree< O, OT >::rangeSearch	(	const TPoint &	target,
		TParam	maxRadius,
		size_t	maxCount,
		TNeighbourhood &	neighbourhood
	)			const `[inline]`

Locates objects within a spherical range around a target position.

Deprecated:: USE OVERLOADS WITH ITERATORS INSTEAD

Parameters:

	target	[in] the center of the spherical range
	maxRadius	[in] the radius of the range
	maxCount	[in] the maximum number of objects to be returned. If this is zero, then all objects in the range are returned. If this is non-zero, then up to maxCount objects are returned. These will be the ones closest to target
	neighbourhood	[out] a std::vector that will be filled with the found objects. The vector will be cleared before use.

Returns:: the squared distance between target and the furthest found object.

Definition at line 158 of file kd_tree.inl.

References lass::spat::KdTree< ObjectType, ObjectTraits >::end(), lass::spat::KdTree< ObjectType, ObjectTraits >::isEmpty(), LASS_THROW, and lass::spat::KdTree< ObjectType, ObjectTraits >::size_.

template<class O , class OT >

template<typename OutputIterator >

OutputIterator lass::spat::KdTree< O, OT >::rangeSearch	(	const TPoint &	target,
		TParam	maxRadius,
		OutputIterator	first
	)			const `[inline]`

Find all objects in a radius of maxRadius of target.

Parameters:

	target	[in] center of range.
	maxRadius	[in] radius of range
	first	[in] output iterator dereferencable to Neighbour.

Returns:: output iterator last so that [first, last) is the range of all found objects.

Note:: The range starting at first must be large enough to contain all found objects. But since this number is probably unknown beforehand, you better use one of those inserter kind of iterators to add the results to a dynamic sized container.
If you wish to use a fixed sized range, you best use the other rangeSearch overload taking a random access iterator and an extra parameter maxCount.

Definition at line 216 of file kd_tree.inl.

References lass::spat::KdTree< ObjectType, ObjectTraits >::doRangeSearch(), and lass::spat::KdTree< ObjectType, ObjectTraits >::isEmpty().

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

template<typename RandomIterator >

RandomIterator lass::spat::KdTree< ObjectType, ObjectTraits >::rangeSearch	(	const TPoint &	target,
		TParam	maxRadius,
		size_t	maxCount,
		RandomIterator	first
	)			const `[inline]`

template<class O , class OT >

void lass::spat::KdTree< O, OT >::swap ( TSelf & other ) [inline]

Swap the representation of two k-d trees.

Definition at line 269 of file kd_tree.inl.

References lass::spat::KdTree< ObjectType, ObjectTraits >::begin_, lass::spat::KdTree< ObjectType, ObjectTraits >::end_, lass::spat::KdTree< ObjectType, ObjectTraits >::heap_, and lass::spat::KdTree< ObjectType, ObjectTraits >::size_.

Referenced by lass::spat::KdTree< ObjectType, ObjectTraits >::clear(), and lass::spat::KdTree< ObjectType, ObjectTraits >::reset().

template<class O , class OT >

const bool lass::spat::KdTree< O, OT >::isEmpty ( ) const [inline]

returns true if there are no objects in the k-d tree

Definition at line 282 of file kd_tree.inl.

References lass::spat::KdTree< ObjectType, ObjectTraits >::heap_.

Referenced by lass::spat::KdTree< ObjectType, ObjectTraits >::nearestNeighbour(), and lass::spat::KdTree< ObjectType, ObjectTraits >::rangeSearch().

template<class O , class OT >

void lass::spat::KdTree< O, OT >::clear ( ) [inline]

resest the k-d tree to an empty one.

Definition at line 292 of file kd_tree.inl.

References lass::spat::KdTree< ObjectType, ObjectTraits >::swap().

template<class O , class OT >

const KdTree< O, OT >::TObjectIterator lass::spat::KdTree< O, OT >::end ( ) const [inline]

Definition at line 302 of file kd_tree.inl.

References lass::spat::KdTree< ObjectType, ObjectTraits >::end_.

Referenced by lass::spat::KdTree< ObjectType, ObjectTraits >::rangeSearch().

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

void lass::spat::KdTree< ObjectType, ObjectTraits >::buildHeap ( ) [private]

template<class O , class OT >

void lass::spat::KdTree< O, OT >::balance	(	size_t	index,
		TIteratorIterator	first,
		TIteratorIterator	last
	)			`[inline, private]`

Definition at line 390 of file kd_tree.inl.

References lass::spat::KdTree< ObjectType, ObjectTraits >::assignNode(), lass::spat::KdTree< ObjectType, ObjectTraits >::dummyAxis_, lass::spat::KdTree< ObjectType, ObjectTraits >::findSplitAxis(), and lass::stde::split().

Referenced by lass::spat::KdTree< ObjectType, ObjectTraits >::KdTree().

template<class O , class OT >

KdTree< O, OT >::TAxis lass::spat::KdTree< O, OT >::findSplitAxis	(	TIteratorIterator	first,
		TIteratorIterator	last
	)			const `[inline, private]`

Definition at line 420 of file kd_tree.inl.

References lass::spat::KdTree< ObjectType, ObjectTraits >::dimension, and lass::prim::distance().

Referenced by lass::spat::KdTree< ObjectType, ObjectTraits >::balance().

template<class O , class OT >

void lass::spat::KdTree< O, OT >::assignNode	(	size_t	index,
		TObjectIterator	object,
		TAxis	splitAxis
	)			`[inline, private]`

Definition at line 453 of file kd_tree.inl.

References lass::spat::KdTree< ObjectType, ObjectTraits >::end_, and lass::spat::KdTree< ObjectType, ObjectTraits >::heap_.

Referenced by lass::spat::KdTree< ObjectType, ObjectTraits >::balance().

template<class O , class OT >

size_t lass::spat::KdTree< O, OT >::findNode	(	size_t	index,
		const TPoint &	target
	)			const `[inline, private]`

Definition at line 465 of file kd_tree.inl.

References lass::spat::KdTree< ObjectType, ObjectTraits >::Node::axis(), lass::spat::KdTree< ObjectType, ObjectTraits >::dummyAxis_, lass::spat::KdTree< ObjectType, ObjectTraits >::end_, lass::spat::KdTree< ObjectType, ObjectTraits >::heap_, lass::spat::KdTree< ObjectType, ObjectTraits >::Node::position(), and lass::stde::split().

template<class O , class OT >

void lass::spat::KdTree< O, OT >::doNearestNeighbour	(	size_t	index,
		const TPoint &	target,
		Neighbour &	best
	)			const `[inline, private]`

Definition at line 490 of file kd_tree.inl.

Referenced by lass::spat::KdTree< ObjectType, ObjectTraits >::nearestNeighbour().

template<class O , class OT >

template<typename OutputIterator >

OutputIterator lass::spat::KdTree< O, OT >::doRangeSearch	(	size_t	index,
		const TPoint &	target,
		TParam	squaredRadius,
		OutputIterator	output
	)			const `[inline, private]`

Definition at line 534 of file kd_tree.inl.

References lass::spat::KdTree< ObjectType, ObjectTraits >::Node::axis(), lass::spat::KdTree< ObjectType, ObjectTraits >::dummyAxis_, lass::spat::KdTree< ObjectType, ObjectTraits >::end_, lass::spat::KdTree< ObjectType, ObjectTraits >::heap_, lass::spat::KdTree< ObjectType, ObjectTraits >::Node::object(), lass::spat::KdTree< ObjectType, ObjectTraits >::Node::position(), lass::stde::split(), lass::num::sqr(), and lass::spat::KdTree< ObjectType, ObjectTraits >::squaredDistance().

Referenced by lass::spat::KdTree< ObjectType, ObjectTraits >::doRangeSearch(), and lass::spat::KdTree< ObjectType, ObjectTraits >::rangeSearch().

template<class O , class OT >

template<typename RandomIterator >

RandomIterator lass::spat::KdTree< O, OT >::doRangeSearch	(	size_t	index,
		const TPoint &	target,
		TReference	squaredRadius,
		size_t	maxCount,
		RandomIterator	first,
		RandomIterator	last
	)			const `[inline, private]`

Definition at line 581 of file kd_tree.inl.

template<class O , class OT >

KdTree< O, OT >::TValue lass::spat::KdTree< O, OT >::squaredDistance	(	const TPoint &	a,
		const TPoint &	b
	)			`[inline, static, private]`

Definition at line 640 of file kd_tree.inl.

References lass::spat::KdTree< ObjectType, ObjectTraits >::dimension, and sqr().

Referenced by lass::spat::KdTree< ObjectType, ObjectTraits >::doNearestNeighbour(), and lass::spat::KdTree< ObjectType, ObjectTraits >::doRangeSearch().

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

template<typename RandomAccessIterator >

RandomAccessIterator lass::spat::KdTree< ObjectType, ObjectTraits >::rangeSearch	(	const TPoint &	target,
		TParam	maxRadius,
		size_t	maxCount,
		RandomAccessIterator	first
	)			const `[inline]`

Find up to a fixed number of objects in a radius of maxRadius of target.

Parameters:

	target	[in] center of range.
	maxRadius	[in] radius of range
	maxCount	[in] maximum number of objects to be found.
	first	[in] random access iterator dereferencable to Neighbour, [first, first + maxCount + 1) must be a valid range.

Returns:: output iterator last so that [first, last) is the range of all found objects.

Note:: This overload will search for a maximum number of maxCount objects at a maximum distance of maxRadius of the center target. When more than maxCount objects are within this distance, the closest objects will be selected. To select the closest objects, a heap is constructed on the iterator range, which is why random access iterators are required instead of regular output iterators. This is also why there's need of an extra position in the range pointed to by first: there's need of an extra position to swap in/out new/old objects. That's why you must make sure [first, first + maxCount + 1) is a valid range.
If you wish to find all points within the range of maxRadius, you better use the overload with the regular output iterator and without maxCount.

Definition at line 253 of file kd_tree.inl.

References lass::spat::KdTree< ObjectType, ObjectTraits >::doRangeSearch(), and lass::spat::KdTree< ObjectType, ObjectTraits >::isEmpty().

Field Documentation

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

TNodes lass::spat::KdTree< ObjectType, ObjectTraits >::heap_ [private]

Definition at line 204 of file kd_tree.h.

Referenced by lass::spat::KdTree< ObjectType, ObjectTraits >::assignNode(), lass::spat::KdTree< ObjectType, ObjectTraits >::doNearestNeighbour(), lass::spat::KdTree< ObjectType, ObjectTraits >::doRangeSearch(), lass::spat::KdTree< ObjectType, ObjectTraits >::findNode(), lass::spat::KdTree< ObjectType, ObjectTraits >::isEmpty(), lass::spat::KdTree< ObjectType, ObjectTraits >::KdTree(), and lass::spat::KdTree< ObjectType, ObjectTraits >::swap().

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

TObjectIterator lass::spat::KdTree< ObjectType, ObjectTraits >::begin_ [private]

Definition at line 205 of file kd_tree.h.

Referenced by lass::spat::KdTree< ObjectType, ObjectTraits >::KdTree(), and lass::spat::KdTree< ObjectType, ObjectTraits >::swap().

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

TObjectIterator lass::spat::KdTree< ObjectType, ObjectTraits >::end_ [private]

Definition at line 206 of file kd_tree.h.

template<class ObjectType , class ObjectTraits = KdTreeObjectTraits<ObjectType>>

size_t lass::spat::KdTree< ObjectType, ObjectTraits >::size_ [private]

Definition at line 207 of file kd_tree.h.

Referenced by lass::spat::KdTree< ObjectType, ObjectTraits >::KdTree(), lass::spat::KdTree< ObjectType, ObjectTraits >::rangeSearch(), and lass::spat::KdTree< ObjectType, ObjectTraits >::swap().

The documentation for this class was generated from the following files:


Data Structures
class	LessDim
class	Neighbour
class	Node
Public Types
enum	{ dimension = TObjectTraits::dimension }
typedef KdTree< ObjectType, ObjectTraits >	TSelf
typedef ObjectType	TObject
typedef ObjectTraits	TObjectTraits
typedef TObjectTraits::TObjectIterator	TObjectIterator
typedef TObjectTraits::TObjectReference	TObjectReference
typedef TObjectTraits::TPoint	TPoint
typedef TObjectTraits::TValue	TValue
typedef TObjectTraits::TParam	TParam
typedef TObjectTraits::TParam	TReference
typedef TObjectTraits::TParam	TConstReference
typedef std::vector< Neighbour >	TNeighbourhood
Public Member Functions
	KdTree ()
	Constructs an empty k-d tree.
	KdTree (TObjectIterator first, TObjectIterator last)
	Constructs a k-d tree from objects in range [first, last).
void	reset ()
	Resets to an empty tree.
void	reset (TObjectIterator first, TObjectIterator last)
	Resets to a new k-d tree of objects in range [first, last).
Neighbour	nearestNeighbour (const TPoint &target) const
	Locates the object that's nearest to a target position.
TValue	rangeSearch (const TPoint &target, TParam maxRadius, size_t maxCount, TNeighbourhood &neighbourhood) const
	Locates objects within a spherical range around a target position.
template<typename OutputIterator >
OutputIterator	rangeSearch (const TPoint &target, TParam maxRadius, OutputIterator first) const
	Find all objects in a radius of maxRadius of target.
template<typename RandomIterator >
RandomIterator	rangeSearch (const TPoint &target, TParam maxRadius, size_t maxCount, RandomIterator first) const
void	swap (TSelf &other)
	Swap the representation of two k-d trees.
const bool	isEmpty () const
	returns true if there are no objects in the k-d tree
void	clear ()
	resest the k-d tree to an empty one.
const TObjectIterator	end () const
template<typename RandomAccessIterator >
RandomAccessIterator	rangeSearch (const TPoint &target, TParam maxRadius, size_t maxCount, RandomAccessIterator first) const
	Find up to a fixed number of objects in a radius of maxRadius of target.
Private Types
enum	{ dummyAxis_ = TAxis(-1) }
typedef std::vector < TObjectIterator >	TObjectIterators
typedef TObjectIterators::iterator	TIteratorIterator
typedef unsigned char	TAxis
typedef std::vector< TAxis >	TAxes
typedef std::vector< Node >	TNodes
Private Member Functions
void	buildHeap ()
void	balance (size_t index, TIteratorIterator first, TIteratorIterator last)
TAxis	findSplitAxis (TIteratorIterator first, TIteratorIterator last) const
void	assignNode (size_t index, TObjectIterator object, TAxis splitAxis)
size_t	findNode (size_t index, const TPoint &target) const
void	doNearestNeighbour (size_t index, const TPoint &target, Neighbour &best) const
template<typename OutputIterator >
OutputIterator	doRangeSearch (size_t index, const TPoint &target, TParam squaredRadius, OutputIterator output) const
template<typename RandomIterator >
RandomIterator	doRangeSearch (size_t index, const TPoint &target, TReference squaredRadius, size_t maxCount, RandomIterator first, RandomIterator last) const
Static Private Member Functions
static TValue	squaredDistance (const TPoint &a, const TPoint &b)
Private Attributes
TNodes	heap_
TObjectIterator	begin_
TObjectIterator	end_
size_t	size_

library of assembled shared sources

lass::spat::KdTree< ObjectType, ObjectTraits > Class Template Reference

Data Structures

Public Types

Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

template<class ObjectType, class ObjectTraits = KdTreeObjectTraits<ObjectType>> class lass::spat::KdTree< ObjectType, ObjectTraits >

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Field Documentation

template<class ObjectType, class ObjectTraits = KdTreeObjectTraits<ObjectType>>
class lass::spat::KdTree< ObjectType, ObjectTraits >