Search code examples
pythonarraysperformancedistancespherical-coordinate

Python (minimal) great-circle distance between sets of points

Is there a Python package for efficiently computing the minimal great-circle distance for each (latitude, longitude) point in array a to each (latitude, longitude) point in array b? For example scipy.spatial.distance.cdist unfortunately does not support spherical distances as far as I can see.

With many data points (e.g. a and b have ~70000 and ~1200 points, respectively), manual calculation similar to the example below becomes too slow, if repeated iterations with different a and b arrays are required. 

deg2rad = np.pi/180.0
rho_cos = (np.sin(lat1[:,None]*deg2rad)*np.sin(lat2[None,:]*deg2rad) +
      np.cos(lat1[:,None]*deg2rad)*np.cos(lat2[None,:]*deg2rad)*np.cos(np.abs(lon1[:,None] - lon2[None,:])*deg2rad))    
rho = np.arccos(rho_cos) / deg2rad
rho_min = np.nanmin(rho,axis=1)
Solution

  • Due to the fact that a great circle length is proportional to the length of its chord, the minimal great circle distance is equivalent to the minimal distance of the points embedded in euclidean 3D space.

    So I would suggest to compute the x,y,z coordinates equivalent to each latitude and longitude pair, and use the mentioned scipy function

    scipy.spatial.distance.cdist

    to find the minimal 3D euclidian distance, which can be easily converted back to great circle distance.