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 <ompl/datastructures/NearestNeighborsSqrtApprox.h>
Inheritance diagram for ompl::NearestNeighborsSqrtApprox< _T >:

Public Member Functions | |
virtual void | clear () |
Clear the datastructure. | |
virtual void | add (const _T &data) |
Add an element to the datastructure. | |
virtual void | add (const std::vector< _T > &data) |
Add a vector of points. | |
virtual bool | remove (const _T &data) |
Remove an element from the datastructure. | |
virtual _T | nearest (const _T &data) const |
Get the nearest neighbor of a point. | |
Protected Member Functions | |
void | updateCheckCount () |
The maximum number of checks to perform when searching for a nearest neighbor. | |
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 57 of file NearestNeighborsSqrtApprox.h.
The documentation for this class was generated from the following file:
- ompl/datastructures/NearestNeighborsSqrtApprox.h