feature request: split out distance_to_dimension, distance_to_node, and compare

[Paul Harris]

I agree.  Both myself and Sylvain had wanted to implement something like
this, but I don't have the time and I haven't heard from Sylvain in a while.

If you like, please go ahead and hack something up - make sure you use the
GIT code, not the tarball, as that is what we'll be committing back to.

I have some time to share opinions on the way you implement the changes, but
thats about it at the moment...  I still have Willi's dynamic dimensions
patch to deal with (sorry Willi, really).

cheers
Paul

2009/7/7 Shane Stafford <shane at stellarscience.com>

> In some cases where a kd-tree is used to partition space between
> non-orthogonal dimensions (for example, on the surface of a sphere) it would
> be helpful to have two separate distance functors. I thought about
> implementing this myself, but then I also thought that to generalize it even
> more, perhaps the Accessor could be also be dispensed with, allowing both
> the compare and distance functors to take _Val arguments (instead of
> _Acc::result_type arguments).
>
> A tentative proposal:
>
> squared_distance_type distanceToDimension( _Val value1, _Val value2, size_t
> dimension );
>
> squared_distance_type distanceBetweenNodes( _Val value1, _Val value2 );
>
> bool compareInDimension( _Val value1, _Val value2, size_t dimension );
>
> I think the crux of the issue is that functions like
> _S_accumulate_node_distance make the assumption that the kd-tree is formed
> on a cartesian grid, and thus that the one-dimensional distances sum in a
> simple way to give the n-dimensional squared difference.
>
> To give a concrete example, consider a 2D mapping onto half of a unit
> sphere consisting of the zenith angle (-pi<phi<pi) and azimuthal angle
> (-pi/2<theta<pi/2). A kd-tree could be used to partition the space along phi
> and theta. The (great-circle) squared distance from any node to a given
> zenith phi is fairly easy to compute. The squared distance to a given
> azimuth is also straightforward to compute. However, these two quantities
> cannot be summed to give the distance along both dimensions (because the
> distance to an azimuth is dependent on the zenith angle). Also, it would be
> easier to optimize the trig by storing things like cos(phi) instead of phi
> itself, and having a compare functor that takes two node values and a
> dimension would allow optimization of the compares, which would use
> different arithmetic in different dimensions.
>
> Thoughts?
>
> Shane
>
>
> _______________________________________________
> 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/20090708/96562771/attachment.htm>