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