4 ms·

You can't really use KD trees with lat/lon coordinates, at least you can't use euclidean distance there for nearest neighbor search. First, longitude wraps fro

by bzz01 12y ago

You can't really use KD trees with lat/lon coordinates, at least you can't use euclidean distance there for nearest neighbor search. First, longitude wraps from -180 to +180 at antimeridian, meaning distance calculations will fail there; second, and I'd say more importantly, one degree longitude length in meters differs a lot depending on latitude; meaning this library will be heavily biased towards longitudal neighbors when using it for locations far from equator.

thampiman 12y ago
Good point. I would need to use this distance function instead: http://www.movable-type.co.uk/scripts/latlong.html http://www.movable-type.co.uk/scripts/latlong.html On it!
- corford 12y ago
  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)
shawn-butler 12y ago
I can recommend the excellent Geographic lib::Geodesic for this having used it in the past. http://geographiclib.sourceforge.net http://geographiclib.sourceforge.net There is a python implementation available as well. http://pypi.python.org/pypi/geographiclib http://pypi.python.org/pypi/geographiclib
- thampiman 12y ago
  Thanks!
thampiman 12y ago
I've fixed this by converting the geodetic coordinates to ECEF. See v1.2 release notes here: https://github.com/thampiman/reverse-geocoder https://github.com/thampiman/reverse-geocoder

by bzz01 12y ago

thampiman 12y ago

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

corford 12y ago
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)

shawn-butler 12y ago

I can recommend the excellent Geographic lib::Geodesic for this having used it in the past. http://geographiclib.sourceforge.net http://geographiclib.sourceforge.net There is a python implementation available as well. http://pypi.python.org/pypi/geographiclib http://pypi.python.org/pypi/geographiclib

thampiman 12y ago
Thanks!

thampiman 12y ago

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