Geometry Boost List: Re: [geometry] R-tree query nearest nodes with torus distance strategy

Subject: Re: [geometry] R-tree query nearest nodes with torus distance strategy
From: Menelaos Karavelas (menelaos.karavelas_at_[hidden])
Date: 2015-04-02 01:56:07

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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/geometry