SOFA API  6a688117
Open source framework for multi-physics simuation
sofa::helper::kdTree< Coord > Class Template Reference

#include <kdTree.h>

Detailed Description

template<class Coord>
class sofa::helper::kdTree< Coord >

This class implements classical kd tree for nearest neighbors search

  • the tree is rebuild from points by calling build(p)
  • N nearest points from point x (in terms of euclidean distance) are retrieved with getNClosest(distance/index_List , x , N)
  • Caching may be used to speed up retrieval: if dx< (d(n)-d(0))/2, then the closest point is in the n-1 cached points (updateCachedDistances is used to update the n-1 distances) see for instance: [zhang92] report and [simon96] thesis for more details
Author
Benjamin Gilles

Classes

struct  TREENODE
 

Protected Attributes

vector< TREENODEtree
 
unsigned int firstNode
 

Public Member Functions

bool isEmpty () const
 
void build (const VecCoord &positions)
 update tree (to be used whenever positions have changed) More...
 
void build (const VecCoord &positions, const vector< unsigned int > &ROI)
 update tree based on positions subset (to be used whenever points p have changed) More...
 
void getNClosest (distanceSet &cl, const Coord &x, const VecCoord &positions, const unsigned int n) const
 get an ordered set of n distance/index pairs between positions and x More...
 
unsigned int getClosest (const Coord &x, const VecCoord &positions) const
 get the index of the closest point between positions and x More...
 
bool getNClosestCached (distanceSet &cl, distanceToPoint &cacheThresh_max, distanceToPoint &cacheThresh_min, Coord &previous_x, const Coord &x, const VecCoord &positions, const unsigned int n) const
 use distance caching to accelerate closest point computation when positions are fixed (see simon96 thesis) More...
 

Protected Member Functions

void print (const unsigned int index)
 
unsigned int build (UIlist &list, unsigned char direction, const VecCoord &positions)
 
void closest (distanceSet &cl, const Coord &x, const unsigned int &currentnode, const VecCoord &positions, unsigned N) const
 
void closest (distanceToPoint &cl, const Coord &x, const unsigned int &currentnode, const VecCoord &positions) const
 

Friends

To be Data-zable
std::ostream & operator<< (std::ostream &os, const kdTree< Coord > &)
 
std::istream & operator>> (std::istream &is, kdTree< Coord > &)
 

Attribute details

template<class Coord >
unsigned int sofa::helper::kdTree< Coord >::firstNode
protected
template<class Coord >
vector< TREENODE > sofa::helper::kdTree< Coord >::tree
protected

Function details

template<class Coord >
void sofa::helper::kdTree< Coord >::build ( const VecCoord positions)

update tree (to be used whenever positions have changed)

template<class Coord >
void sofa::helper::kdTree< Coord >::build ( const VecCoord positions,
const vector< unsigned int > &  ROI 
)

update tree based on positions subset (to be used whenever points p have changed)

template<class Coord >
unsigned int sofa::helper::kdTree< Coord >::build ( UIlist list,
unsigned char  direction,
const VecCoord positions 
)
protected
template<class Coord >
void sofa::helper::kdTree< Coord >::closest ( distanceSet cl,
const Coord &  x,
const unsigned int currentnode,
const VecCoord positions,
unsigned  N 
) const
protected
template<class Coord >
void sofa::helper::kdTree< Coord >::closest ( distanceToPoint cl,
const Coord &  x,
const unsigned int currentnode,
const VecCoord positions 
) const
protected
template<class Coord >
unsigned int sofa::helper::kdTree< Coord >::getClosest ( const Coord &  x,
const VecCoord positions 
) const

get the index of the closest point between positions and x

template<class Coord >
void sofa::helper::kdTree< Coord >::getNClosest ( distanceSet cl,
const Coord &  x,
const VecCoord positions,
const unsigned int  n 
) const

get an ordered set of n distance/index pairs between positions and x

template<class Coord >
bool sofa::helper::kdTree< Coord >::getNClosestCached ( distanceSet cl,
distanceToPoint cacheThresh_max,
distanceToPoint cacheThresh_min,
Coord &  previous_x,
const Coord &  x,
const VecCoord positions,
const unsigned int  n 
) const

use distance caching to accelerate closest point computation when positions are fixed (see simon96 thesis)

template<class Coord >
bool sofa::helper::kdTree< Coord >::isEmpty ( ) const
inline
template<class Coord >
void sofa::helper::kdTree< Coord >::print ( const unsigned int  index)
protected

Enum details

template<class Coord >
anonymous enum
Enumerator
dim 

Related details

template<class Coord >
std::ostream& operator<< ( std::ostream &  os,
const kdTree< Coord > &   
)
friend
template<class Coord >
std::istream& operator>> ( std::istream &  is,
kdTree< Coord > &   
)
friend