6 ms·

Haversine Formula

73 points by okai 7y ago

pimmen 7y ago
When you're evaluating datastructures to quickly get the nearest neighbor in constant time, and you're dealing with actual longitude and latitude, you really need to be aware of this so that you don't accidentally pick something that only works for euclidean distances.
- jacobolus 7y ago
  If you just want nearest neighbor, I would recommend storing floating point (x, y, z) coordinates, and using Euclidean distance in 3-space. (Or rather, the square of distance Δx² + Δy² + Δz²; skip the square root.) If you want to save storage space / bandwidth, you can use the stereographic projection onto a plane and then cut the precision of the floating-point numbers. Stereographic projection / inverse stereographic projection only requires 1 division per point. Latitude/longitude is quite an inefficient and cumbersome way of representing points on a sphere, though it’s convenient if navigating using the stars.
  - kardos 7y ago
    > Latitude/longitude is quite an inefficient and cumbersome way of representing points on a sphere Using lat/lon absolves you of storing projection metadata
    - jacobolus 7y ago
      https://en.wikipedia.org/wiki/Latitude#Geodetic_and_geocentric_latitudes https://en.wikipedia.org/wiki/Latitude#Geodetic_and_geocentr... “The definition must be accompanied with a specification of the ellipsoid.” etc.
- tgb 7y ago
  I think this is misleading or misstated. Haversine distance of points on a sphere is a monotonic function of euclidean distance, so one's nearest neighbor is the same in both. You must be warning people not to just take the sum of square differences on the actual latitude and longitude values.
fourier_mode 7y ago
I remember googling for this formula for doing a data mining homework in which I was given the start and end points of a taxi in geo-spatial coordinates.
- peteradio 7y ago
  Unless you're taking a taxi across the continental US, there is very little difference between Haversine and Euclidean distance calculations. Haversine is more computationally expensive. Haversine isn't even the actual distance travelled on gridded roads. Haversine is probably not the answer to what you are looking for.
  - glitcher 7y ago
    Also, the straight line distance between two points can often be misleading when used to estimate driving distances depending on the topography of the area. It just depends on how important accurate driving distance is for the use case.
  - kevinventullo 7y ago
    If you do this, you still need to do a one-time correction for the length of a degree longitude at a given latitude, or you get weird behavior even at small distances (and it gets weirder the closer you are to a pole). We learned this the hard way when our "k-nearest places" query was returning point clouds which looked like ovals!
- fegu 7y ago
  Rectilinear distance, also called taxicab distance, would probably serve better.
nsporillo 7y ago
I had to implement the Haversine distance for a data mining home work as well. We were given a list of the worlds capitals and we had to use openstreetmap api to get the latitudes and longitudes. Then we had to implement hierarchical agglomerative clustering by hand, only using the dendrogram function from scikit-learn.
LeoPanthera 7y ago
My greatest ever accomplishment was implementing this formula in a spreadsheet. I still have it! Here's the cell formula: =ACOS(COS(RADIANS(90−Selector::$Lat))×COS(RADIANS(90−N2))+SIN(RADIANS(90−Selector::$Lat))×SIN(RADIANS(90−N2))×COS(RADIANS(Selector::$Lon−O2)))×6371 ("Selector" is a table title, I seem to remember - this is an Apple Numbers spreadsheet.) 6371 is a magic number which gives the result in kilometers.
- jasmcole 7y ago
  6371km is the radius of the earth :)
scarygliders 7y ago
Yes it's very handy. I use it in my Captain's Log[0] application for Elite: Dangerous players, to show the distance your ship is to a target Lat/Lon location, amongst other handy navigation features. Written in Python, using Qt4 and Pyside. [0] https://captainslog.scarygliders.net/user-manuals/captains-log-2x/#overlay https://captainslog.scarygliders.net/user-manuals/captains-l...
Dachande663 7y ago
I added a Haversine operation to CyberChef[1] last year. Very useful equation in a very useful tool. [1] https://gchq.github.io/CyberChef/#recipe=Haversine_distance()&input=MzUuOTI1ODYwLCAtODYuODMyODkwLCA1MS41MDMzMjMsIC0wLjExOTU0Mw https://gchq.github.io/CyberChef/#recipe=Haversine_distance(...
jimmy1 7y ago
I learned the hard way the unit of measurement you use for R when calculating distance between two lat,long coordinates is what you get out. So if R is in meters, you aren't calculating the distance in miles. Hehe...should have paid attention in math class (to be fair to myself, American math education is horrible).
- JackFr 7y ago
  > (to be fair to myself, American math education is horrible) Mmmmmmm. Not magically converting meters to miles? I dunno. I kind of think that one's on you, bud.
- mhh__ 7y ago
  Always worth doing the dimensional (units) analysis first
jpatokal 7y ago
https://openflights.org/ https://openflights.org/ uses the Haversine formula (and much more!) to not just compute distance, but plot great circle flight routes on a world map: https://github.com/jpatokal/openflights/blob/master/js/greatcircle.js https://github.com/jpatokal/openflights/blob/master/js/great... There are a lot of interesting edge cases regarding routes that cross the dateline, the North Pole, etc. Most of the code was taken from Movable Type's incredible library of lat/long code: http://www.movable-type.co.uk/scripts/latlong.html http://www.movable-type.co.uk/scripts/latlong.html
- dankohn1 7y ago
  Openflights is one of my very favorite websites. Thank you! How else would I know that I’ve travelled 2.7x to the moon in the last decade. https://openflights.org/user/dankohn1 https://openflights.org/user/dankohn1
deleted 7y ago
[deleted]
man-and-laptop 7y ago
I just derived the spherical law of cosines that's the foundation of this formula using quaternions and Sympy. The quaternions were modelled as 4x4 matrices. The philosophy is that you can treat trigonometry as a triangle construction problem. You give me the specs of a triangle, and I can use physical tools like compasses, protractors and rulers to construct your triangle. This is similar to using trigonometry, except without any algebra involved, just construction tools. You can also use this philosophy to derive the algebraic formulas. When it came to formula derivation, I used the quaternions to simulate the physical construction, and I got out the formulas.
- jakeogh 7y ago
  That sounds like fun. Please drop a link if you post it.
  - man-and-laptop 7y ago
    See here: https://github.com/jkabrg/Spherical-law-of-cosines-proof-using-Sympy-and-quaternions/blob/master/derivation.ipynb https://github.com/jkabrg/Spherical-law-of-cosines-proof-usi... I'll provide more explanation later.
- theoh 7y ago
  The last figure on this page http://www.vias.org/calculus/07_trigonometric_functions_01_06.html http://www.vias.org/calculus/07_trigonometric_functions_01_0... really has that character (in 2D). I wish trigonometry in secondary school had been taught more like this (geometrically) because it would have been good preparation for vector calculus, among other things.
  - deleted 7y ago
    [deleted]
TAForObvReasons 7y ago
Of course there's a JS library for everything https://github.com/njj/haversine https://github.com/njj/haversine
- fourier_mode 7y ago
  It is a one line formula but has 186 stars and 10 contributors to it. I don't get the hype!
  - stygiansonic 7y ago
    Well, left-pad[0] has over 1000 stars and 17 contributors. 0. https://github.com/stevemao/left-pad https://github.com/stevemao/left-pad
bisrig 7y ago
And when Haversine isn't accurate enough: Vincenty's method. https://en.wikipedia.org/wiki/Vincenty%27s_formulae https://en.wikipedia.org/wiki/Vincenty%27s_formulae Also, another reference for both methods with calculators! Vicenty: http://www.movable-type.co.uk/scripts/latlong-vincenty.html http://www.movable-type.co.uk/scripts/latlong-vincenty.html Haversine: http://www.movable-type.co.uk/scripts/latlong.html http://www.movable-type.co.uk/scripts/latlong.html
- shittyadmin 7y ago
  If you need a library to do this, check out GeographicLib. It's written by C. F. F. Karney the same guy who developed an algorithm and wrote a scientific paper about improving Vincenty's formulae for performance and fixing issues at nearly antipodal points. It has good implementations in C++, C# and Javascript. https://geographiclib.sourceforge.io/html/ https://geographiclib.sourceforge.io/html/
  - damian2000 7y ago
    Minor point but I know c# has a GeoCoordinate class into the framework Dlls. It also contains methods to calculate distance between points. Many .net Devs I've worked with didn't know about it. I think it came out first in .net 4.0.
pressurefree 7y ago
Use getBounds() function With inner join on Indexed lat,lon SQL columns Instead of haversine for each marker
ruairidhwm 7y ago
MySQL also offers this natively which allows for speed improvements compared to calculating it yourself in a script: https://dev.mysql.com/doc/refman/5.7/en/spatial-convenience-functions.html https://dev.mysql.com/doc/refman/5.7/en/spatial-convenience-...

73 points by okai 7y ago

When you're evaluating datastructures to quickly get the nearest neighbor in constant time, and you're dealing with actual longitude and latitude, you really need to be aware of this so that you don't accidentally pick something that only works for euclidean distances.

jacobolus 7y ago
If you just want nearest neighbor, I would recommend storing floating point (x, y, z) coordinates, and using Euclidean distance in 3-space. (Or rather, the square of distance Δx² + Δy² + Δz²; skip the square root.) If you want to save storage space / bandwidth, you can use the stereographic projection onto a plane and then cut the precision of the floating-point numbers. Stereographic projection / inverse stereographic projection only requires 1 division per point. Latitude/longitude is quite an inefficient and cumbersome way of representing points on a sphere, though it’s convenient if navigating using the stars.
- kardos 7y ago
  > Latitude/longitude is quite an inefficient and cumbersome way of representing points on a sphere Using lat/lon absolves you of storing projection metadata
  - jacobolus 7y ago
    https://en.wikipedia.org/wiki/Latitude#Geodetic_and_geocentric_latitudes https://en.wikipedia.org/wiki/Latitude#Geodetic_and_geocentr... “The definition must be accompanied with a specification of the ellipsoid.” etc.
tgb 7y ago
I think this is misleading or misstated. Haversine distance of points on a sphere is a monotonic function of euclidean distance, so one's nearest neighbor is the same in both. You must be warning people not to just take the sum of square differences on the actual latitude and longitude values.

fourier_mode 7y ago

I remember googling for this formula for doing a data mining homework in which I was given the start and end points of a taxi in geo-spatial coordinates.

peteradio 7y ago
Unless you're taking a taxi across the continental US, there is very little difference between Haversine and Euclidean distance calculations. Haversine is more computationally expensive. Haversine isn't even the actual distance travelled on gridded roads. Haversine is probably not the answer to what you are looking for.
- glitcher 7y ago
  Also, the straight line distance between two points can often be misleading when used to estimate driving distances depending on the topography of the area. It just depends on how important accurate driving distance is for the use case.
- kevinventullo 7y ago
  If you do this, you still need to do a one-time correction for the length of a degree longitude at a given latitude, or you get weird behavior even at small distances (and it gets weirder the closer you are to a pole). We learned this the hard way when our "k-nearest places" query was returning point clouds which looked like ovals!
fegu 7y ago
Rectilinear distance, also called taxicab distance, would probably serve better.

nsporillo 7y ago

I had to implement the Haversine distance for a data mining home work as well. We were given a list of the worlds capitals and we had to use openstreetmap api to get the latitudes and longitudes. Then we had to implement hierarchical agglomerative clustering by hand, only using the dendrogram function from scikit-learn.

LeoPanthera 7y ago

My greatest ever accomplishment was implementing this formula in a spreadsheet. I still have it! Here's the cell formula: =ACOS(COS(RADIANS(90−Selector::$Lat))×COS(RADIANS(90−N2))+SIN(RADIANS(90−Selector::$Lat))×SIN(RADIANS(90−N2))×COS(RADIANS(Selector::$Lon−O2)))×6371 ("Selector" is a table title, I seem to remember - this is an Apple Numbers spreadsheet.) 6371 is a magic number which gives the result in kilometers.

jasmcole 7y ago
6371km is the radius of the earth :)

scarygliders 7y ago

Yes it's very handy. I use it in my Captain's Log[0] application for Elite: Dangerous players, to show the distance your ship is to a target Lat/Lon location, amongst other handy navigation features. Written in Python, using Qt4 and Pyside. [0] https://captainslog.scarygliders.net/user-manuals/captains-log-2x/#overlay https://captainslog.scarygliders.net/user-manuals/captains-l...

Dachande663 7y ago

I added a Haversine operation to CyberChef[1] last year. Very useful equation in a very useful tool. [1] https://gchq.github.io/CyberChef/#recipe=Haversine_distance()&input=MzUuOTI1ODYwLCAtODYuODMyODkwLCA1MS41MDMzMjMsIC0wLjExOTU0Mw https://gchq.github.io/CyberChef/#recipe=Haversine_distance(...

jimmy1 7y ago

I learned the hard way the unit of measurement you use for R when calculating distance between two lat,long coordinates is what you get out. So if R is in meters, you aren't calculating the distance in miles. Hehe...should have paid attention in math class (to be fair to myself, American math education is horrible).

JackFr 7y ago
> (to be fair to myself, American math education is horrible) Mmmmmmm. Not magically converting meters to miles? I dunno. I kind of think that one's on you, bud.
mhh__ 7y ago
Always worth doing the dimensional (units) analysis first

jpatokal 7y ago

https://openflights.org/ https://openflights.org/ uses the Haversine formula (and much more!) to not just compute distance, but plot great circle flight routes on a world map: https://github.com/jpatokal/openflights/blob/master/js/greatcircle.js https://github.com/jpatokal/openflights/blob/master/js/great... There are a lot of interesting edge cases regarding routes that cross the dateline, the North Pole, etc. Most of the code was taken from Movable Type's incredible library of lat/long code: http://www.movable-type.co.uk/scripts/latlong.html http://www.movable-type.co.uk/scripts/latlong.html

dankohn1 7y ago
Openflights is one of my very favorite websites. Thank you! How else would I know that I’ve travelled 2.7x to the moon in the last decade. https://openflights.org/user/dankohn1 https://openflights.org/user/dankohn1

deleted 7y ago

[deleted]

man-and-laptop 7y ago

I just derived the spherical law of cosines that's the foundation of this formula using quaternions and Sympy. The quaternions were modelled as 4x4 matrices. The philosophy is that you can treat trigonometry as a triangle construction problem. You give me the specs of a triangle, and I can use physical tools like compasses, protractors and rulers to construct your triangle. This is similar to using trigonometry, except without any algebra involved, just construction tools. You can also use this philosophy to derive the algebraic formulas. When it came to formula derivation, I used the quaternions to simulate the physical construction, and I got out the formulas.

jakeogh 7y ago
That sounds like fun. Please drop a link if you post it.
- man-and-laptop 7y ago
  See here: https://github.com/jkabrg/Spherical-law-of-cosines-proof-using-Sympy-and-quaternions/blob/master/derivation.ipynb https://github.com/jkabrg/Spherical-law-of-cosines-proof-usi... I'll provide more explanation later.
theoh 7y ago
The last figure on this page http://www.vias.org/calculus/07_trigonometric_functions_01_06.html http://www.vias.org/calculus/07_trigonometric_functions_01_0... really has that character (in 2D). I wish trigonometry in secondary school had been taught more like this (geometrically) because it would have been good preparation for vector calculus, among other things.
- deleted 7y ago
  [deleted]

TAForObvReasons 7y ago

Of course there's a JS library for everything https://github.com/njj/haversine https://github.com/njj/haversine

fourier_mode 7y ago
It is a one line formula but has 186 stars and 10 contributors to it. I don't get the hype!
- stygiansonic 7y ago
  Well, left-pad[0] has over 1000 stars and 17 contributors. 0. https://github.com/stevemao/left-pad https://github.com/stevemao/left-pad

bisrig 7y ago

And when Haversine isn't accurate enough: Vincenty's method. https://en.wikipedia.org/wiki/Vincenty%27s_formulae https://en.wikipedia.org/wiki/Vincenty%27s_formulae Also, another reference for both methods with calculators! Vicenty: http://www.movable-type.co.uk/scripts/latlong-vincenty.html http://www.movable-type.co.uk/scripts/latlong-vincenty.html Haversine: http://www.movable-type.co.uk/scripts/latlong.html http://www.movable-type.co.uk/scripts/latlong.html

shittyadmin 7y ago
If you need a library to do this, check out GeographicLib. It's written by C. F. F. Karney the same guy who developed an algorithm and wrote a scientific paper about improving Vincenty's formulae for performance and fixing issues at nearly antipodal points. It has good implementations in C++, C# and Javascript. https://geographiclib.sourceforge.io/html/ https://geographiclib.sourceforge.io/html/
- damian2000 7y ago
  Minor point but I know c# has a GeoCoordinate class into the framework Dlls. It also contains methods to calculate distance between points. Many .net Devs I've worked with didn't know about it. I think it came out first in .net 4.0.

pressurefree 7y ago

Use getBounds() function With inner join on Indexed lat,lon SQL columns Instead of haversine for each marker

ruairidhwm 7y ago

MySQL also offers this natively which allows for speed improvements compared to calculating it yourself in a script: https://dev.mysql.com/doc/refman/5.7/en/spatial-convenience-functions.html https://dev.mysql.com/doc/refman/5.7/en/spatial-convenience-...