On Thu, Apr 2, 2015 at 9:43 AM, Adam Wulkiewicz <adam.wulkiewicz@gmail.com> wrote:
Adam Wulkiewicz wrote:
Menelaos Karavelas wrote:
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 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.
I'm using a 2 arms, one 6 degree of freedom and the other 7 dof with revolute (rotating) joints. The position of the arm can be accurately represented as an n-d point representing the angle of each joint, with no need for orientation/pose on the surface of a torus, with 1 dimension for each joint. 

Here is a simple image explaining the 2d case:
http://robotics.stanford.edu/~latombe/cs326/2009/class3/class3.htm

Therefore I don't need to worry about orientation but probably just the envelope/box which I believe is used for the data structure and the points themselves.
 
Those 2d coordinates could be phi (toroidal angle) and theta (poloidal angle) (http://fusionwiki.ciemat.es/wiki/Toroidal_coordinates).

As detailed above, this means in my current use case I can skip theta.
 
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.

I may be mistaken, but I believe the distance can be calculated by taking the angular distance separately in each dimension as linked previously, and listing them as a single tor_dist_vec, then take the sqrt(element_sum(tor_dist_vec)). Since all the distances will always be between [0,pi] I believe this will work correctly.
 

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

Thanks, these look like good links. Right now I only plan to use the coordinates to find the k nearest neighbors in cartesian space, but the information is useful to have.

Or you could consider contributing the support for another coordinate system.
I might be interested in doing this eventually. Are the instructions you have in that github repository under your account sufficiently up to date for me to follow in getting set up? https://github.com/awulkiew/temp-contributing

Thanks!
Andrew Hundt