feature request: split out distance_to_dimension, distance_to_node, and compare
Shane Stafford
shane at stellarscience.com
Tue Jul 7 14:08:06 UTC 2009
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
More information about the libkdtree-devel
mailing list