You can't really use KD trees with lat/lon coordinates, at least you can't use e...

shawn-butler · on March 28, 2015

I can recommend the excellent Geographic lib::Geodesic for this having used it in the past.

http://geographiclib.sourceforge.net

There is a python implementation available as well. http://pypi.python.org/pypi/geographiclib

thampiman · on March 30, 2015

Thanks!

thampiman · on March 30, 2015

I've fixed this by converting the geodetic coordinates to ECEF. See v1.2 release notes here: https://github.com/thampiman/reverse-geocoder

thampiman · on March 28, 2015

Good point. I would need to use this distance function instead: http://www.movable-type.co.uk/scripts/latlong.html

On it!

corford · on March 28, 2015

Here's a python function we use to calculate haversine distances:

  import math
  from collections import namedtuple

  def haversine_distance(origin, destination):
      """ Haversine formula to calculate the distance between two lat/long points on a sphere """

      radius = 6371 # FAA approved globe radius in km

      dlat = math.radians(destination.lat-origin.lat)
      dlon = math.radians(destination.lng-origin.lng)
      a = math.sin(dlat/2) * math.sin(dlat/2) + math.cos(math.radians(origin.lat)) \
          * math.cos(math.radians(destination.lat)) * math.sin(dlon/2) * math.sin(dlon/2)
      c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a))
      d = radius * c

      # Return distance in km
      return int(math.floor(d))

  LatLng = namedtuple('LatLng', 'lat, lng')
  
  origin = LatLng(51.507222, -0.1275) # London
  destination = LatLng(37.966667, 23.716667) # Athens

  print "Distance (km): %d" % haversine_distance(origin, destination)