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.<br><br>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.<br>
<br>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).<br><br>cheers<br>Paul<br>
<br><div class="gmail_quote">2009/7/7 Shane Stafford <span dir="ltr"><<a href="mailto:shane@stellarscience.com">shane@stellarscience.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;">
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).<br>
<br>
A tentative proposal:<br>
<br>
squared_distance_type distanceToDimension( _Val value1, _Val value2, size_t dimension );<br>
<br>
squared_distance_type distanceBetweenNodes( _Val value1, _Val value2 );<br>
<br>
bool compareInDimension( _Val value1, _Val value2, size_t dimension );<br>
<br>
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.<br>
<br>
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.<br>
<br>
Thoughts?<br>
<br>
Shane<br>
<br>
<br>
_______________________________________________<br>
libkdtree-devel mailing list<br>
<a href="mailto:libkdtree-devel@lists.alioth.debian.org" target="_blank">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>
</blockquote></div><br>