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

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

#include <kd_tree.h>

Inheritance diagram for lass::spat::KdTree< ObjectType, ObjectTraits >:

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.
Neighbour	nearestNeighbour (const TPoint &target, TParam maxRadius) const
	Locates the object that's nearest to a target position, within a maximum range.
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.
void	swap (TSelf &other)
	Swap the representation of two k-d trees.
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.
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.

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 87 of file kd_tree.h.

Constructor & Destructor Documentation

KdTree()

template<class O, class OT>

lass::spat::KdTree< O, OT >::KdTree	(	TObjectIterator	first,
		TObjectIterator	last )

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.

Member Function Documentation

reset()

template<class O, class OT>

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

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 129 of file kd_tree.inl.

rangeSearch() [1/3]

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

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 239 of file kd_tree.inl.

References isEmpty(), and rangeSearch().

Referenced by rangeSearch().

rangeSearch() [2/3]

template<class O, class OT>

template<typename OutputIterator>

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

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 297 of file kd_tree.inl.

References isEmpty().

rangeSearch() [3/3]

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

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 334 of file kd_tree.inl.

---

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

• kd_tree.h
• kd_tree.inl