Loading...
Searching...
No Matches
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

void clear () override
 Clear the datastructure.
 
void add (const _T &data) override
 Add an element to the datastructure.
 
void add (const std::vector< _T > &data) override
 Add a vector of points.
 
bool remove (const _T &data) override
 Remove an element from the datastructure.
 
_T nearest (const _T &data) const override
 Get the nearest neighbor of a point.
 
- Public Member Functions inherited from ompl::NearestNeighborsLinear< _T >
bool reportsSortedResults () const override
 Return true if the solutions reported by this data structure are sorted, when calling nearestK / nearestR.
 
void nearestK (const _T &data, std::size_t k, std::vector< _T > &nbh) const override
 Return the k nearest neighbors in sorted order.
 
void nearestR (const _T &data, double radius, std::vector< _T > &nbh) const override
 Return the nearest neighbors within distance radius in sorted order.
 
std::size_t size () const override
 Get the number of elements in the datastructure.
 
void list (std::vector< _T > &data) const override
 Get all the elements in the datastructure.
 
- Public Member Functions inherited from ompl::NearestNeighbors< _T >
virtual void setDistanceFunction (const DistanceFunction &distFun)
 Set the distance function to use.
 
const DistanceFunctiongetDistanceFunction () const
 Get the distance function used.
 

Protected Member Functions

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.
 
std::size_t offset_ {0}
 The offset to start checking at (between 0 and checks_)
 
- Protected Attributes inherited from ompl::NearestNeighborsLinear< _T >
std::vector< _T > data_
 The data elements stored in this structure.
 
- Protected Attributes inherited from ompl::NearestNeighbors< _T >
DistanceFunction distFun_
 The used distance function.
 

Additional Inherited Members

- Public Types inherited from ompl::NearestNeighbors< _T >
using DistanceFunction = std::function<double(const _T &, const _T &)>
 The definition of a distance function.
 

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.

Member Function Documentation

◆ add() [1/2]

template<typename _T >
void ompl::NearestNeighborsSqrtApprox< _T >::add ( const _T & data)
inlineoverridevirtual

Add an element to the datastructure.

Reimplemented from ompl::NearestNeighborsLinear< _T >.

Definition at line 71 of file NearestNeighborsSqrtApprox.h.

◆ add() [2/2]

template<typename _T >
void ompl::NearestNeighborsSqrtApprox< _T >::add ( const std::vector< _T > & data)
inlineoverridevirtual

Add a vector of points.

Reimplemented from ompl::NearestNeighborsLinear< _T >.

Definition at line 77 of file NearestNeighborsSqrtApprox.h.

◆ clear()

template<typename _T >
void ompl::NearestNeighborsSqrtApprox< _T >::clear ( )
inlineoverridevirtual

Clear the datastructure.

Reimplemented from ompl::NearestNeighborsLinear< _T >.

Definition at line 64 of file NearestNeighborsSqrtApprox.h.

◆ nearest()

template<typename _T >
_T ompl::NearestNeighborsSqrtApprox< _T >::nearest ( const _T & data) const
inlineoverridevirtual

Get the nearest neighbor of a point.

Reimplemented from ompl::NearestNeighborsLinear< _T >.

Definition at line 91 of file NearestNeighborsSqrtApprox.h.

◆ remove()

template<typename _T >
bool ompl::NearestNeighborsSqrtApprox< _T >::remove ( const _T & data)
inlineoverridevirtual

Remove an element from the datastructure.

Reimplemented from ompl::NearestNeighborsLinear< _T >.

Definition at line 83 of file NearestNeighborsSqrtApprox.h.

◆ updateCheckCount()

template<typename _T >
void ompl::NearestNeighborsSqrtApprox< _T >::updateCheckCount ( )
inlineprotected

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

Definition at line 120 of file NearestNeighborsSqrtApprox.h.

Member Data Documentation

◆ checks_

template<typename _T >
std::size_t ompl::NearestNeighborsSqrtApprox< _T >::checks_ {0}
protected

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

Definition at line 126 of file NearestNeighborsSqrtApprox.h.

◆ offset_

template<typename _T >
std::size_t ompl::NearestNeighborsSqrtApprox< _T >::offset_ {0}
mutableprotected

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

Definition at line 129 of file NearestNeighborsSqrtApprox.h.


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