ompl::NearestNeighborsSqrtApprox< _T > Class Template Reference

A nearest neighbors datastructure that uses linear search. The linear search is done over sqrt(n) elements only. (Every sqrt(n) elements are skipped). More...

#include <NearestNeighborsSqrtApprox.h>

Inheritance diagram for ompl::NearestNeighborsSqrtApprox< _T >:

[legend]

List of all members.

Public Member Functions
virtual void	add (const std::vector< _T > &data)
	Add a vector of points.
virtual void	add (const _T &data)
	Add an element to the datastructure.
virtual void	clear (void)
	Clear the datastructure.
virtual _T	nearest (const _T &data) const
	Get the nearest neighbor of a point.
	NearestNeighborsSqrtApprox (void)
virtual bool	remove (const _T &data)
	Remove an element from the datastructure.
virtual	~NearestNeighborsSqrtApprox (void)
Protected Member Functions
void	updateCheckCount (void)
Protected Attributes
std::size_t	checks_
	The number of checks to be performed when looking for a nearest neighbor.
std::size_t	offset_
	The offset to start checking at (between 0 and checks_).

---

Detailed Description

template<typename _T>
class ompl::NearestNeighborsSqrtApprox< _T >

A nearest neighbors datastructure that uses linear search. The linear search is done over sqrt(n) elements only. (Every sqrt(n) elements are skipped).

• Search for nearest neighbor is O(sqrt(n)).
• Search for k-nearest neighbors is O(n log(k)).
• Search for neighbors within a range is O(n log(n)).
• Adding an element to the datastructure is O(1).
• Removing an element from the datastructure O(n).

Definition at line 53 of file NearestNeighborsSqrtApprox.h.

---

Constructor & Destructor Documentation

template<typename _T >

ompl::NearestNeighborsSqrtApprox< _T >::NearestNeighborsSqrtApprox

(

void

)

[inline]

Definition at line 43 of file NearestNeighborsSqrtApprox.h.

template<typename _T >

virtual ompl::NearestNeighborsSqrtApprox< _T >::~NearestNeighborsSqrtApprox

(

void

)

[inline, virtual]

Definition at line 47 of file NearestNeighborsSqrtApprox.h.

---

Member Function Documentation

template<typename _T >

virtual void ompl::NearestNeighborsSqrtApprox< _T >::add

(

const std::vector< _T > &

data

)

[inline, virtual]

Add a vector of points.

Reimplemented from ompl::NearestNeighborsLinear< _T >.

Definition at line 64 of file NearestNeighborsSqrtApprox.h.

template<typename _T >

virtual void ompl::NearestNeighborsSqrtApprox< _T >::add

(

const _T &

data

)

[inline, virtual]

Add an element to the datastructure.

Reimplemented from ompl::NearestNeighborsLinear< _T >.

Definition at line 58 of file NearestNeighborsSqrtApprox.h.

template<typename _T >

virtual void ompl::NearestNeighborsSqrtApprox< _T >::clear

(

void

)

[inline, virtual]

Clear the datastructure.

Reimplemented from ompl::NearestNeighborsLinear< _T >.

Definition at line 51 of file NearestNeighborsSqrtApprox.h.

template<typename _T >

virtual _T ompl::NearestNeighborsSqrtApprox< _T >::nearest

(

const _T &

data

)

const [inline, virtual]

Get the nearest neighbor of a point.

Reimplemented from ompl::NearestNeighborsLinear< _T >.

Definition at line 78 of file NearestNeighborsSqrtApprox.h.

template<typename _T >

virtual bool ompl::NearestNeighborsSqrtApprox< _T >::remove

(

const _T &

data

)

[inline, virtual]

Remove an element from the datastructure.

Reimplemented from ompl::NearestNeighborsLinear< _T >.

Definition at line 70 of file NearestNeighborsSqrtApprox.h.

template<typename _T >

void ompl::NearestNeighborsSqrtApprox< _T >::updateCheckCount

(

void

)

[inline, protected]

Definition at line 108 of file NearestNeighborsSqrtApprox.h.

---

Member Data Documentation

template<typename _T >

std::size_t ompl::NearestNeighborsSqrtApprox< _T >::checks_ [protected]

The number of checks to be performed when looking for a nearest neighbor.

Definition at line 114 of file NearestNeighborsSqrtApprox.h.

template<typename _T >

std::size_t ompl::NearestNeighborsSqrtApprox< _T >::offset_ [mutable, protected]

The offset to start checking at (between 0 and checks_).

Definition at line 117 of file NearestNeighborsSqrtApprox.h.

---

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

• NearestNeighborsSqrtApprox.h