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: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2015-04-02 05:35:30

Hi Andrew, Menelaos,

Menelaos Karavelas wrote:
> 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?

I think it's a 3d position with 3d orientation but I'm not sure what 
does Andrew have in mind by saying that the points are on a torus. In 
general case of points on some 3D surface (let's consider a sphere) the 
points can be stored in cartesian 3D or the coordinates could be mapped 
into the 2D surface, e.g. lat/lon for a sphere/spheroid. And AFAIS 
(http://en.wikipedia.org/wiki/Toroidal_coordinates) in the case of a 
torus one could also use 3d toroidal coordinates. If you have 3d points 
I'm assuming they're already in 3D cartesian or toroidal so you could 
just store them in the rtree as 3D cartesian points (since we doesn't 
have toroidal CS). An alternative would be to map them to the surface of 
a torus using some projection and then store them as 2d points in the rtree.

In case you had points defined in toroidal CS, you could consider adding 
this CS to the Boost.Geometry, implementing all of the required 
algorithms/strategies for this CS, etc.

>
>> 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).

This shouldn't be a problem. The points would be stored in the different 
parts of the tree but if the predicates like distance/intersection/etc. 
was calculated properly (so taking the periodicity into account) the 
result would be correct. I'm talking about spherical CS. I think that 
for 3d toroidal it could also apply but I should think more about it.

Now, I'm guessing the problem is the distance calculation, because it 
must be the shortest distance on the surface of a torus, not in 3D 
cartesian space. Do I get it right?
In case if the distance could be the simple 3D cartesian distance it 
should work out of the box.

As you probably know the rtree stores the points and bounding boxes. If 
the points was 3d cartesian points then the boxes would be 3d cartesian 
boxes. If the points was mapped into the 2d surface then the boxes would 
also lie on this surface (as spherical lon/lat or 3d cartesian). During 
the nearest query the rtree checks shortest distances to bounding boxes 
and values (points) stored in the rtree. So if you wanted to find the 
closest points to some point the rtree would need to call both:
bg::comparable_distance(query_point, bounding_box)
bg::comparable_distance(query_point, value_point).
So you could just overload both of those functions for e.g. some 
specific type of query_point and do the math there.

>
>>
>> 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.

AFAIU the points are on a surface of a torus, not a sphere? But the 
cases are similar indeed. Since we doesn't have a torus coordinate 
system you could use cartesian and store the points either in 3d or 2d. 
They'd be indexed as cartesian points without taking into account the 
periodicity. Then you could use some "special" query point type and pass 
it into the nearest predicate. Then force the rtree to calculate the 
distances the way you like by overloading bg::comparable_distance().

Or you could consider contributing the support for another coordinate 
system.

Regards,
Adam