Support for directional data

[Paul Harris]

I agree, i just meant that the *current* kdtree uses euclidean distances
(right?), and that should be a template parameter.

2008/10/21 Sylvain Bougerel <sylvain.bougerel.devel at gmail.com>

> 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
>
> _______________________________________________
> libkdtree-devel mailing list
> libkdtree-devel at lists.alioth.debian.org
> http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.alioth.debian.org/pipermail/libkdtree-devel/attachments/20081021/517fea25/attachment.htm