Support for directional data

[Sylvain Bougerel]

On Mon, Oct 20, 2008 at 4:38 PM, Renaud Detry <renaudjdetry at airpost.net> wrote:
> 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.

Sorry to break into the conversation. I wanted to jump on this :)
because it's a misconception (?), and it currently affects the library
in some ways.

kd-tree are not linked to euclidean distances in anyway. In fact they
have nothing to do with it. The only thing you need to build a kd-tree
is: operator[] and operator<. That's all. You don't need any distance
calculation. It's because kd-tree represent vector spaces only. And
these two operators allow you to walk the kd-tree, and even answer
range queries.

It's only when it comes to nearest neighbor calculation that you have
to transform your vector space into a *metric* vector space. To do
this, you need another function to be applied on the space: dist().
There is plenty of common dist() calculation: euclidean distance,
Manhattan distance, orthogonal distance, reimannean distance, etc...
They "bend" your metric space in a certain way that is independent
from the original vector space. I think they should all work with the
kd-tree if the library was designed properly.

I know you might want to argue on this :). Before you do so, I urge
you to consult the kd-tree page on CGal, and the documentation for
ANN, as well as the wikipedia page for metric spaces.

So I would like to propose that we include a distance functor as a
parameter of the nearest neighbor calculation :-D

We could even do it without breaking the implementation by specifying
a default parameter functor that computes euclidean distance?

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

The above design allow you to specify the proper distance calculation
and therefore avoid the approximation altogether...


Sylvain