All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator
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 >:

List of all members.

Public Member Functions

virtual void clear (void)
 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 (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 57 of file NearestNeighborsSqrtApprox.h.


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