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: Andrew Hundt (athundt_at_[hidden])
Date: 2015-04-02 12:03:46

On Thu, Apr 2, 2015 at 9:43 AM, Adam Wulkiewicz <adam.wulkiewicz_at_[hidden]>
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:
>
>
> 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.
>
> 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