Hi Andrew.

On 02/04/2015 06:51 πμ, Andrew Hundt wrote:
I need to store a 6d set of double points on a torus and query the nearest neighbors. I believe the distance algorithm isn't too hard to implement by simply using the angle difference on each axis:

http://stackoverflow.com/questions/9505862/shortest-distance-between-two-degree-marks-on-a-circle


I would like to understand better what you have in mind: are you going to be using the first two coordinates of these points for the distance computation? The remaining 4 coordinates are just some other data?

However, I'm not sure if r-tree could handle that or how to set it up. Could you provide advice? Would I need to implement an entirely new distance strategy?

I will leave it up to Adam to talk about the r-tree in detail, but let me add 2c about this. the r-rtree does not work properly right now for points on the spherical coordinate system. The reason is that the current implementation of boxes does not take into account the periodicity of the underlying space (I mean the sphere here parametrized through longitude latitude).


I believe the basics should work with boost geometry model points because I should only be storing, querying, and taking the distance between points which if I recall correctly are among the basics implemented for higher dimensions. 


Well this is almost true (see also my question above). In order to use the r-tree for nearest neighbor queries you need to be able to compute the envelope of (subsets of) your points, and be able to compute the distance of a point (the query point) to both another point and a box. as I mention above the problem is with respect to the computation of the envelope (box) of a set of points.

Some "good" news: I am currently working on implementing envelope calculation for points on a sphere. On the other hand, defining what a box is on the sphere is not as straightforward as in the Cartesian case, so this is another issue to be taken care of.
I meant to, and will, send an email to the list about this, and everybody on the list will have the chance to comment on it.

Best,

- m.

Thanks for your help.

Cheers!
Andrew Hundt


_______________________________________________
Geometry mailing list
Geometry@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/geometry