Support for directional data

[Sylvain Bougerel]

On Fri, Oct 24, 2008 at 9:17 PM, Renaud Detry <renaudjdetry at airpost.net> wrote:
> Hi -
>
>>> K-d trees seem very
>>> dependant on the Euclidean metric;
>>
>> kd-tree are not linked to euclidean distances in anyway. In fact they
>> have nothing to do with it.
>
> Ok, I was definitely wrong there :-)
>
> I'm still curious about this issue though. I'll take your advice with
> the CGAL doc and other documentation. One quick question though:
>
>> So I would like to propose that we include a distance functor as a
>> parameter of the nearest neighbor calculation :-D
>
> What do you think would be the requirements on that metric to allow
> nearest neighbor queries to take advantage of the underlying Kd-tree
> organization of the data?
>
> Renaud.
>
>

Sorry I was in holiday, hence the delay.

Well, it's part of the problem. To take adventage of the kd-tree
underlaying structure the metric function should operate directly of
the element of the value and not the value itself.

The rational behind this is: sometime the kd-tree will calculate the
distance between point a and b, sometime it will calculate the
distance between point a and projection of point b on a particular
axis. So the nearest neighbor search would call the function with the
element of the value already "unpacked".

I dunno if I was clear, does it even reply to your question?