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:
>> 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
> 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
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:
> 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
> Or you could consider contributing the support for another coordinate
Geometry list run by mateusz at loskot.net