[SciPy-user] Efficiently searching the surface of a sphere

[Robert Kern]

On Thu, Jun 11, 2009 at 16:48, Zane Selvans<zane at ideotrope.org> wrote:
> Zane Selvans <zane <at> ideotrope.org> writes:
>
>> It's unclear to me at the moment whether I can use the kd-tree data
>> structure for this:
>>
>> http://docs.scipy.org/doc/scipy/reference/spatial.html
>>
>> and somehow define the "distance" metric to be the spherical distance...
>
> Hmm.  Maybe on second thought, the right thing to do is just convert all the
> points in question to 3D cartesian coordinates at the beginning, and use the
> kd-tree as it is.  The distances involved will change, but the nearest-neighbors
> should still be the same points.

That's probably the most straightforward thing to do at this time. You
may also consider using a spherical Voronoi diagram. Robert Renka's
FORTRAN STRIPACK code would do the trick:

  http://www.netlib.org/toms/772

-- 
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless
enigma that is made terrible by our own mad attempt to interpret it as
though it had an underlying truth."
  -- Umberto Eco