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 09:43:17

Adam Wulkiewicz wrote:
> 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.

Those 2d coordinates could be phi (toroidal angle) and theta (poloidal 
angle) (http://fusionwiki.ciemat.es/wiki/Toroidal_coordinates). They 
could be stored in the rtree as 2d cartesian points but you'd still have 
to implement your own distance function (see below). On a torus those 
angles would probably both be in range [-pi, pi] and both would have 
periodical nature (like longitude in spherical and geographical 
coordinate systems).

Now it depends, how precise must the distance be. You could calculate a 
simple cartesian distance of those coordinates (treating them as 
cartesian) but taking the periodicity into account. This however 
wouldn't be the "true"/shortest distance between points or between a 
point and a box on the surface of a torus, defined by geodesics. For 
this you'd probably have to approximate it somehow through integral 
expression, newton's method, taylor series, etc.

The results of a quick search for the definition of geodesics on torus:
http://www.rdrop.com/~half/math/torus/torus.geodesics.pdf
http://www34.homepage.villanova.edu/robert.jantzen/notes/torus/torusgeos.pdf

Regards,
Adam

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