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 
|  | 
| bool | isEmpty () const | 
|  | 
| void | build (const VecCoord &positions) | 
|  | update tree (to be used whenever positions have changed)  More... 
 | 
|  | 
| void | build (const VecCoord &positions, const type::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... 
 | 
|  |