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

Robert Kern robert.kern@gmail....
Thu Jun 11 16:55:22 CDT 2009

On Thu, Jun 11, 2009 at 16:48, Zane Selvans<zane@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:


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

More information about the SciPy-user mailing list