<div dir="ltr">I agree, i just meant that the *current* kdtree uses euclidean distances (right?), and that should be a template parameter.<br><br><div class="gmail_quote">2008/10/21 Sylvain Bougerel <span dir="ltr"><<a href="mailto:sylvain.bougerel.devel@gmail.com">sylvain.bougerel.devel@gmail.com</a>></span><br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="Ih2E3d">On Mon, Oct 20, 2008 at 4:38 PM, Renaud Detry <<a href="mailto:renaudjdetry@airpost.net">renaudjdetry@airpost.net</a>> wrote:<br>
> Hello all,<br>
><br>
>> Maybe instead of storing the angle, store the 3 components of the<br>
>> unit direction vector.<br>
><br>
> I also believe this is the right way to go. K-d trees seem very<br>
> dependant on the Euclidean metric; when organizing data that support a<br>
> non-Euclidean metric M, it sounds fair to first project the data in a<br>
> space where M can be approximated with the Euclidean distance. When<br>
> searching for angles, one could project on the contour of a 2d<br>
> circle. When searching for 3d rotations, one could use the surface of<br>
> the 3-sphere, where rotations are represented with unit quaternions.<br>
<br>
</div>Sorry to break into the conversation. I wanted to jump on this :)<br>
because it's a misconception (?), and it currently affects the library<br>
in some ways.<br>
<br>
kd-tree are not linked to euclidean distances in anyway. In fact they<br>
have nothing to do with it. The only thing you need to build a kd-tree<br>
is: operator[] and operator<. That's all. You don't need any distance<br>
calculation. It's because kd-tree represent vector spaces only. And<br>
these two operators allow you to walk the kd-tree, and even answer<br>
range queries.<br>
<br>
It's only when it comes to nearest neighbor calculation that you have<br>
to transform your vector space into a *metric* vector space. To do<br>
this, you need another function to be applied on the space: dist().<br>
There is plenty of common dist() calculation: euclidean distance,<br>
Manhattan distance, orthogonal distance, reimannean distance, etc...<br>
They "bend" your metric space in a certain way that is independent<br>
from the original vector space. I think they should all work with the<br>
kd-tree if the library was designed properly.<br>
<br>
I know you might want to argue on this :). Before you do so, I urge<br>
you to consult the kd-tree page on CGal, and the documentation for<br>
ANN, as well as the wikipedia page for metric spaces.<br>
<br>
So I would like to propose that we include a distance functor as a<br>
parameter of the nearest neighbor calculation :-D<br>
<br>
We could even do it without breaking the implementation by specifying<br>
a default parameter functor that computes euclidean distance?<br>
<div class="Ih2E3d"><br>
><br>
> This would be a very elegant solution for nearest neighbor search.<br>
><br>
> For range queries, since the Euclidean K-d tree range is just an<br>
> approximation, I would only use it as an upper bound, then compute the<br>
> appropriate distance for all the points that fall within the range.<br>
<br>
</div>The above design allow you to specify the proper distance calculation<br>
and therefore avoid the approximation altogether...<br>
<font color="#888888"><br>
<br>
Sylvain<br>
</font><div><div></div><div class="Wj3C7c"><br>
_______________________________________________<br>
libkdtree-devel mailing list<br>
<a href="mailto:libkdtree-devel@lists.alioth.debian.org">libkdtree-devel@lists.alioth.debian.org</a><br>
<a href="http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel" target="_blank">http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel</a><br>
</div></div></blockquote></div><br></div>