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

Zane Selvans zane@ideotrope....
Thu Jun 11 15:55:01 CDT 2009

Does anyone have a good approach for solving this problem in a
computationally efficient way?

* Given a fixed set S of points (~10^6 of them) on a sphere, defined
as pairs of latitude/longitude values and
* Given another set of points L on the sphere.
* Find the set of points X in S having the smallest geodesic distances
(i.e. distance along the surface of the sphere) to each of the points
in L.

The best idea I've been able to come up with so far is to sort S by
latitude and longitude, and then search that sorted list for points
with lats and lons which are close to those of the points in L, and
then calculate the geodesic distances to those few points, and take
the nearest one.  But it won't behave well near the poles, or near the
longitude discontinuity...

It's unclear to me at the moment whether I can use the kd-tree data
structure for this:


and somehow define the "distance" metric to be the spherical distance...

Thanks for any suggestions!

Zane A. Selvans
Amateur Earthling
+1 303 815 6866

More information about the SciPy-user mailing list