Support for directional data

Renaud Detry renaudjdetry at airpost.net
Mon Oct 20 08:38:17 UTC 2008


Hello all,

> Maybe instead of storing the angle, store the 3 components of the  
> unit direction vector.

I also believe this is the right way to go. K-d trees seem very
dependant on the Euclidean metric; when organizing data that support a
non-Euclidean metric M, it sounds fair to first project the data in a
space where M can be approximated with the Euclidean distance. When
searching for angles, one could project on the contour of a 2d
circle. When searching for 3d rotations, one could use the surface of
the 3-sphere, where rotations are represented with unit quaternions.

This would be a very elegant solution for nearest neighbor search.

For range queries, since the Euclidean K-d tree range is just an
approximation, I would only use it as an upper bound, then compute the
appropriate distance for all the points that fall within the range.

I would be very interested in hearing how efficient this is in practice!

Best,
Renaud.



More information about the libkdtree-devel mailing list