Subject: Re: [geometry] R-tree query nearest nodes with torus distance strategy
From: Menelaos Karavelas (menelaos.karavelas_at_[hidden])
Date: 2015-04-02 01:56:07
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?
> 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).
> 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.
> Thanks for your help.
> Andrew Hundt
> Geometry mailing list
Geometry list run by mateusz at loskot.net