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

Protected Member Functions

void updateCheckCount ()
 The maximum number of checks to perform when searching for a nearest neighbor. More...
 

Protected Attributes

std::size_t checks_ {0}
 The number of checks to be performed when looking for a nearest neighbor. More...
 
std::size_t offset_ {0}
 The offset to start checking at (between 0 and checks_) More...
 
- Protected Attributes inherited from ompl::NearestNeighborsLinear< _T >
std::vector< _T > data_
 The data elements stored in this structure. More...
 
- Protected Attributes inherited from ompl::NearestNeighbors< _T >
DistanceFunction distFun_
 The used distance function. More...
 

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. More...
 

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: