Template Class NearestNeighborsSqrtApprox

Inheritance Relationships

Base Type

Class Documentation

template<typename _T>
class NearestNeighborsSqrtApprox : public ompl::NearestNeighborsLinear<_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).

Public Functions

NearestNeighborsSqrtApprox() = default
~NearestNeighborsSqrtApprox() override = default
inline virtual void clear() override

Clear the datastructure.

inline virtual void add(const _T &data) override

Add an element to the datastructure.

inline virtual void add(const std::vector<_T> &data) override

Add a vector of points.

inline virtual bool remove(const _T &data) override

Remove an element from the datastructure.

inline virtual _T nearest(const _T &data) const override

Get the nearest neighbor of a point.

Protected Functions

inline void updateCheckCount()

The maximum number of checks to perform when searching for a nearest neighbor.

Protected Attributes

std::size_t checks_ = {0}

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

mutable std::size_t offset_ = {0}

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