Editing Haversine formula

{{Short description|Formula for the great-circle distance between two points on a sphere}}
The '''haversine formula''' determines the [[great-circle distance]] between two points on a [[sphere]] given their [[longitude]]s and [[latitude]]s. Important in [[navigation]], it is a special case of a more general formula in [[spherical trigonometry]], the '''law of haversines''', that relates the sides and angles of spherical triangles.

The first [[table of haversines]] in English was published by James Andrew in 1805,<ref name="Brummelen_2013">{{cite book | first=Glen Robert | last=van Brummelen | author-link=Glen Robert van Brummelen | title=Heavenly Mathematics: The Forgotten Art of Spherical Trigonometry | date=2013 | publisher=[[Princeton University Press]] | isbn=9780691148922 | id=0691148929 | url=https://books.google.com/books?id=0BCCz8Sx5wkC&pg=PR7 | access-date=2015-11-10}}</ref> but [[Florian Cajori]] credits an earlier use by [[José de Mendoza y Ríos]] in 1801.<ref name="Ríos_1795">{{cite book | first=Joseph | last=de Mendoza y Ríos | author-link=José de Mendoza y Ríos | title=Memoria sobre algunos métodos nuevos de calcular la longitud por las distancias lunares: y aplicacion de su teórica á la solucion de otros problemas de navegacion | language=Spanish | url=https://books.google.com/books?id=030t0OqlX2AC | year=1795 | publisher=Imprenta Real | location=Madrid, Spain}}</ref><ref name="Cajori_1929">{{cite book | first=Florian | last=Cajori | author-link=Florian Cajori | title=A History of Mathematical Notations | volume=2 | orig-year=1929<!-- 1929-03 --> | publisher=[[Open court publishing company]] | location=Chicago | date=1952 | edition=2 (3rd corrected printing of 1929 issue) | page=172 | isbn=978-1-60206-714-1 | id=1602067147 | url=https://books.google.com/books?id=bT5suOONXlgC | access-date=2015-11-11 | quote=The haversine first appears in the tables of logarithmic versines of [[José de Mendoza y Rios]] (Madrid, 1801, also 1805, 1809), and later in a treatise on navigation of [[James Inman]] (1821).}} (NB. ISBN and link for reprint of second edition by Cosimo, Inc., New York,  2013.)</ref> The term ''[[haversine]]'' was coined in 1835 by [[James Inman]].<ref name="Inman_1835">{{cite book |last=Inman<!-- Rev. D.D. --> |first=James |author-link=James Inman |url=https://books.google.com/books?id=-fUOnQEACAAJ |title=Navigation and Nautical Astronomy: For the Use of British Seamen |date=1835 |publisher=W. Woodward, C. & J. Rivington |edition=3 |location=London, UK |access-date=2015-11-09 |orig-year=1821}} (Fourth edition: [https://books.google.com/books?id=MK8PAAAAYAAJ].)</ref><ref name="OED_1989_Haversine">{{OED2|haversine}}</ref>

These names follow from the fact that they are customarily written in terms of the haversine function, given by {{math|hav ''θ'' {{=}} sin<sup>2</sup>({{sfrac|''θ''|2}})}}. The formulas could equally be written in terms of any multiple of the haversine, such as the older [[versine]] function (twice the haversine). Prior to the advent of computers, the elimination of division and multiplication by factors of two proved convenient enough that tables of haversine values and [[logarithm]]s were included in 19th- and early 20th-century navigation and trigonometric texts.<ref>H. B. Goodwin, [https://books.google.com/books?id=KSNKAAAAYAAJ&lpg=PA735&pg=PA735 The haversine in nautical astronomy], ''Naval Institute Proceedings'', vol. 36, no. 3 (1910), pp. 735–746: ''Evidently if a Table of Haversines is employed we shall be saved in the first instance the trouble of dividing the sum of the logarithms by two, and in the second place of multiplying the angle taken from the tables by the same number.  This is the special advantage of the form of table first introduced by Professor Inman, of the Portsmouth Royal Navy College, nearly a century ago.''</ref><ref>W. W. Sheppard and C. C. Soule, [https://books.google.com/books?id=8S0wAAAAYAAJ Practical navigation] (World Technical Institute: Jersey City, 1922).</ref><ref>E. R. Hedrick, [https://archive.org/details/logarithmictrigo00hedriala Logarithmic and Trigonometric Tables] (Macmillan, New York, 1913).</ref>  These days, the haversine form is also convenient in that it has no coefficient in front of the {{math|sin<sup>2</sup>}} function.
[[File:Illustration of great-circle distance.svg|thumb|A diagram illustrating great-circle distance (drawn in red) between two points on a sphere, P and Q. Two [[antipodal points]], u and v are also shown.]]

==Formulation==

Let the [[central angle]] {{math|''&theta;''}} between any two points on a sphere be:
:<math>\theta = \frac{d}{r}</math>

where
* {{math|''d''}} is the distance between the two points along a [[great circle]] of the sphere (see [[great-circle distance|spherical distance]]),
* {{math|''r''}} is the radius of the sphere.

The ''haversine formula'' allows the [[haversine function|haversine]] of {{math|''&theta;''}} to be computed directly from the latitude (represented by {{math|''φ''}}) and longitude (represented by {{math|''λ''}}) of the two points:
:<math>
  \operatorname{hav}\theta =
  \operatorname{hav}\left(\Delta \varphi \right) + \cos\left(\varphi_1\right)\cos\left(\varphi_2\right)\operatorname{hav}\left(\Delta \lambda \right)
</math>

where
* {{math|''φ''<sub>1</sub>}}, {{math|''φ''<sub>2</sub>}} are the latitude of point 1 and latitude of point 2,
* {{math|''λ''<sub>1</sub>}}, {{math|''λ''<sub>2</sub>}} are the longitude of point 1 and longitude of point 2,
* <math>\Delta \varphi = \varphi_2 - \varphi_1</math>, <math>\Delta \lambda = \lambda_2 - \lambda_1</math>.

Finally, the [[haversine function]] {{math|hav(''&theta;'')}}, applied above to both the central angle {{math|''&theta;''}} and the differences in latitude and longitude, is
: <math>\operatorname{hav}\theta= \sin^2\left(\frac{\theta}{2}\right) = \frac{1 - \cos(\theta)}{2}</math>
The haversine function computes half a [[versine]] of the angle {{math|''θ''}}, or the squares of half [[chord (geometry)|chord]] of the angle on a unit circle (sphere).

To solve for the distance {{math|''d''}}, apply the archaversine ([[inverse haversine]]) to {{math|hav(''&theta;'')}} or use the [[arcsine]] (inverse sine) function:
: <math>d = r\operatorname{archav}(\operatorname{hav}\theta) = 2r\arcsin\left(\sqrt{\operatorname{hav}\theta}\right)</math>

or more explicitly:
: <math>\begin{align}
  d &= 2r \arcsin\left(\sqrt{\operatorname{hav}(\Delta \varphi ) + ( 1 - \operatorname{hav}(\Delta \varphi) - \operatorname{hav}(2 \varphi_\text{m} ))\cdot\operatorname{hav}(\Delta \lambda)}\right) \\
    &= 2r \arcsin\left(\sqrt{\sin^2\left(\frac{\Delta \varphi }{2}\right) + \left(1- \sin^2\left(\frac{\Delta \varphi }{2}\right) - \sin^2\left(\varphi_\text{m}\right)\right) \cdot \sin^2\left(\frac{\Delta \lambda}{2}\right)}\right) \\
    &= 2r \arcsin\left(\sqrt{\sin^2\left(\frac{\Delta \varphi }{2}\right) + \cos \varphi_1 \cdot \cos \varphi_2 \cdot \sin^2\left(\frac{\Delta \lambda}{2}\right)}\right) \\
    &= 2r \arcsin\left(\sqrt{\sin^2\left(\frac{\Delta \varphi }{2}\right) \cdot \cos^2\left(\frac{\Delta \lambda}{2}\right) + \cos^2\left(\varphi_\text{m}\right) \cdot \sin^2\left(\frac{\Delta \lambda}{2}\right)}\right) \\
   &= 2r \arcsin\left(\sqrt{\frac{1 - \cos\left(\Delta \varphi \right) + \cos \varphi_1 \cdot \cos \varphi_2 \cdot \left(1 - \cos\left(\Delta \lambda\right)\right)}{2}}\right)
\end{align}</math><ref name="Gade2010">{{cite journal|last1=Gade|first1=Kenneth|title=A Non-singular Horizontal Position Representation|journal=Journal of Navigation|volume=63|issue=3|year=2010|pages=395–417|issn=0373-4633|doi=10.1017/S0373463309990415|bibcode=2010JNav...63..395G }}</ref>
where
<math>\varphi_\text{m} = \frac{\varphi_2 + \varphi_1}{2}</math>.

When using these formulae, one must ensure that {{math|''h'' {{=}} hav(''&theta;'')}} does not exceed 1 due to a [[floating point]] error ({{math|''d''}} is [[real number|real]] only for {{math|0 ≤ ''h'' ≤ 1}}). {{math|''h''}} only approaches 1 for ''antipodal'' points (on opposite sides of the sphere)—in this region, relatively large numerical errors tend to arise in the formula when finite precision is used. Because {{math|''d''}} is then large (approaching {{math|π''R''}}, half the circumference) a small error is often not a major concern in this unusual case (although there are other [[great-circle distance]] formulas that avoid this problem).  (The formula above is sometimes written in terms of the [[arctangent]] function, but this suffers from similar numerical problems near {{math|''h'' {{=}} 1}}.)

As described below, a similar formula can be written using cosines (sometimes called the [[spherical law of cosines]], not to be confused with the [[law of cosines]] for plane geometry) instead of haversines, but if the two points are close together (e.g. a kilometer apart, on the Earth) one might end up with {{math|cos({{sfrac|''d''|''R''}}) {{=}} 0.99999999}}, leading to an inaccurate answer. Since the haversine formula uses sines, it avoids that problem.

Either formula is only an approximation when applied to the [[Earth]], which is not a perfect sphere: the "[[Earth radius]]" {{math|''R''}} varies from 6356.752&nbsp;km at the poles to 6378.137&nbsp;km at the equator.  More importantly, the [[radius of curvature (applications)|radius of curvature]] of a north-south line on the earth's surface is 1% greater at the poles (≈6399.594&nbsp;km) than at the equator (≈6335.439&nbsp;km)&mdash;so the haversine formula and law of cosines cannot be guaranteed correct to better than 0.5%.{{Citation needed|reason=Your explanation here|date=January 2019}} More accurate methods that consider the Earth's ellipticity are given by [[Vincenty's formulae]] and the other formulas in the [[geographical distance]] article.

==The law of haversines{{anchor|Law}}==
[[File:Law-of-haversines.svg|right|thumb|Spherical triangle solved by the law of haversines]]
Given a unit sphere, a "triangle" on the surface of the sphere is defined by the [[great circle]]s connecting three points {{math|''u''}}, {{math|''v''}}, and {{math|''w''}} on the sphere.  If the lengths of these three sides are {{math|''a''}} (from {{math|''u''}} to {{math|''v''}}), {{math|''b''}} (from {{math|''u''}} to {{math|''w''}}), and {{math|''c''}} (from {{math|''v''}} to {{math|''w''}}), and the angle of the corner opposite {{math|''c''}} is {{math|''C''}}, then the law of haversines states:<ref name="Korn_2000">{{cite book |title=Mathematical handbook for scientists and engineers: Definitions, theorems, and formulas for reference and review |first1=Grandino Arthur |last1=Korn |first2=Theresa M.|author2-link= Theresa M. Korn |last2=Korn |edition=3rd<!-- (based on 1968 edition by McGrawHill, Inc.) --> |date=2000 |orig-year=1922 |publisher=[[Dover Publications]] |location=Mineola, New York |chapter=Appendix B: B9. Plane and Spherical Trigonometry: Formulas Expressed in Terms of the Haversine Function |pages=892–893 |isbn=978-0-486-41147-7}}</ref>
: <math>\operatorname{hav}(c) = \operatorname{hav}(a - b) + \sin(a)\sin(b)\operatorname{hav}(C).</math>

Since this is a unit sphere, the lengths {{math|''a''}}, {{math|''b''}}, and {{math|''c''}} are simply equal to the angles (in [[radian]]s) subtended by those sides from the center of the sphere (for a non-unit sphere, each of these arc lengths is equal to its [[central angle]] multiplied by the radius {{math|''R''}} of the sphere).

In order to obtain the haversine formula of the previous section from this law, one simply considers the special case where {{math|''u''}} is the [[Geographic North Pole|north pole]], while {{math|''v''}} and {{math|''w''}} are the two points whose separation {{math|''d''}} is to be determined.  In that case, {{math|''a''}} and {{math|''b''}} are {{math|{{sfrac|π|2}} − ''φ''<sub>1,2</sub>}} (that is, the, co-latitudes), {{math|''C''}} is the longitude separation {{math|''λ''<sub>2</sub> − ''λ''<sub>1</sub>}}, and {{math|''c''}} is the desired {{math|{{sfrac|''d''|''R''}}}}.  Noting that {{math|sin({{sfrac|π|2}} − ''φ'') {{=}} cos(''φ'')}}, the haversine formula immediately follows.

To derive the law of haversines, one starts with the [[spherical law of cosines]]:

:<math>\cos(c) = \cos(a)\cos(b) + \sin(a)\sin(b)\cos(C). \,</math>

As mentioned above, this formula is an ill-conditioned way of solving for {{math|''c''}} when {{math|''c''}} is small.  Instead, we substitute the identity that {{math|cos(''θ'') {{=}} 1 − 2 hav(''θ'')}}, and also employ the [[trigonometric identity#Addition/subtraction theorems|addition identity]] {{math|cos(''a'' − ''b'') {{=}} cos(''a'') cos(''b'') + sin(''a'') sin(''b'')}}, to obtain the law of haversines, above.

==Proof==
One can prove the formula:
:<math>
  \operatorname{hav}\left(\theta\right) =
  \operatorname{hav}\left(\Delta \varphi \right) + \cos\left(\varphi_1\right)\cos\left(\varphi_2\right)\operatorname{hav}\left(\Delta \lambda\right)
</math>

by transforming the points given by their latitude and longitude into [[cartesian coordinate system#Three Dimensions|cartesian coordinates]], then taking their [[dot product#Geometric Definition|dot product]].

Consider two points <math>\bf p_1,p_2</math> on the [[unit sphere]], given by their latitude <math>\varphi</math> and longitude <math>\lambda</math>:

:<math>\begin{align}
{\bf p_2} &= (\lambda_2, \varphi_2) \\
{\bf p_1} &= (\lambda_1, \varphi_1)
\end{align}</math>

These representations are very similar to [[spherical coordinate system|spherical coordinates]], however latitude is measured as angle from the equator and not the north pole.  These points have the following representations in cartesian coordinates:

:<math>\begin{align}
{\bf p_2} &= (\cos(\lambda_2)\cos(\varphi_2), \;\sin(\lambda_2)\cos(\varphi_2), \;\sin(\varphi_2)) \\
{\bf p_1} &= (\cos(\lambda_1)\cos(\varphi_1), \;\sin(\lambda_1)\cos(\varphi_1), \;\sin(\varphi_1))
\end{align}</math>

From here we could directly attempt to calculate the dot product and proceed, however the formulas become significantly simpler when we consider the following fact: the distance between the two points will not change if we rotate the sphere along the z-axis.  This will in effect add a constant to <math>\lambda_1, \lambda_2</math>.  Note that similar considerations do not apply to transforming the latitudes - adding a constant to the latitudes may change the distance between the points.  By choosing our constant to be <math>-\lambda_1</math>, and setting <math>\lambda' = \Delta \lambda</math>, our new points become:

:<math>\begin{align}
{\bf p_2'}	&= (\cos(\lambda')\cos(\varphi_2), \;\sin(\lambda')\cos(\varphi_2), \;\sin(\varphi_2)) \\
{\bf p_1'}	&= (\cos(0)\cos(\varphi_1), \;\sin(0)\cos(\varphi_1), \;\sin(\varphi_1)) \\
			&= (\cos(\varphi_1), \;0, \;\sin(\varphi_1))
\end{align}</math>

With <math>\theta</math> denoting the angle between <math>{\bf p_1}</math> and <math>{\bf p_2}</math>, we now have that:

:<math>\begin{align}
\cos(\theta) &= \langle{\bf p_1},{\bf p_2}\rangle = \langle{\bf p_1'},{\bf p_2'}\rangle = \cos(\lambda')\cos(\varphi_1)\cos(\varphi_2) + \sin(\varphi_1)\sin(\varphi_2) \\
			&= \sin(\varphi_2)\sin(\varphi_1) + \cos(\varphi_2)\cos(\varphi_1) - \cos(\varphi_2)\cos(\varphi_1) + \cos(\lambda')\cos(\varphi_2)\cos(\varphi_1) \\
			&= \cos(\Delta \varphi) + \cos(\varphi_2)\cos(\varphi_1)(-1 + \cos(\lambda')) \Rightarrow \\
\operatorname{hav}\left(\theta\right)
			&= \operatorname{hav}\left(\Delta \varphi \right) + \cos(\varphi_2)\cos(\varphi_1)\operatorname{hav}\left(\lambda' \right)
\end{align}
</math>

== Example ==
[[File:Geodesic from the White House to the Eiffel Tower.svg|thumb|A geodesic (red) connecting Washington, D.C. to Paris, plotted on the [[two-point equidistant projection]], with geodesic circles (blue) at multiples of 1,000 km distance from Washington.]]

The haversine formula can be used to find the approximate distance between the [[White House]] in [[Washington, D.C.]] (latitude 38.898° N, longitude 77.037° W) and the [[Eiffel Tower]] in [[Paris]] (latitude 48.858° N, longitude 2.294° E). The difference in latitudes is <math>\Delta \varphi = {}</math>9.960° and the difference in longitudes is <math>\Delta\lambda = {}</math>79.331°. Inputting these into the haversine formula,

<math display=block>\begin{align}
\operatorname{hav}\left(\theta\right)
&= \operatorname{hav}(\Delta \varphi ) + \cos(\varphi_1)\cos(\varphi_2)\operatorname{hav}(\Delta \lambda) \\[5mu]
&= \operatorname{hav}(9.960^\circ) + \cos(38.898^\circ)\cos(48.858^\circ)\operatorname{hav}(79.331^\circ) \\[5mu]
&\approx 0.0075356 + 0.77827 \times 0.65793 \times 0.40743 \\[5mu]
&\approx 0.21616 \\[5mu]
\theta &\approx 55.411^\circ.
\end{align}</math>

The great-circle distance is this central angle, in [[radian]]s (55.411 [[Degree (angle)|degrees]] is 0.96710 radians), multiplied by the [[Earth radius|average radius of the Earth]],

<math display=block>0.96710 \times 6371.2\ \text{km} \approx 6161.6\ \text{km}.</math>

By comparison, using a more accurate ellipsoidal model of the earth, the [[Geodesics on an ellipsoid|geodesic distance]] between these landmarks can be computed as approximately 6177.45 km.<ref>This calculation was made using the open-source geodesic calculation software [https://geographiclib.sourceforge.io GeographicLib], assuming the [[WGS84]] ellipsoid. See {{cite journal |first=Charles F. F. |last=Karney |title=Algorithms for geodesics |journal=Journal of Geodesy |volume=87 |number=1 |pages=43–55 |year=2013 |doi=10.1007/s00190-012-0578-z |doi-access=free|arxiv=1109.4448 }}</ref>

== See also ==
*[[Sight reduction]]
*[[Vincenty's formulae]]
*[[Cosine distance]]

==References==
<references/>

==Further reading==
* [[U. S. Census Bureau]] Geographic Information Systems FAQ, (content has been moved to [http://www.movable-type.co.uk/scripts/GIS-FAQ-5.1.html What is the best way to calculate the distance between 2 points?])
* R. W. Sinnott, "Virtues of the Haversine", ''Sky and Telescope'' '''68''' (2), 159 (1984).
* {{cite web|url=http://mathforum.org/library/drmath/view/51879.html |title=Deriving the haversine formula|work=Ask Dr. Math|date=April 20–21, 1999|archive-url=https://web.archive.org/web/20200120134215/http://mathforum.org/library/drmath/view/51879.html|archive-date=20 January 2020|url-status=dead}}
* W. Gellert, S. Gottwald, M. Hellwich, H. Kästner, and H. Küstner, ''The VNR Concise Encyclopedia of Mathematics'', 2nd ed., ch. 12 (Van Nostrand Reinhold: New York, 1989).

==External links==
* Implementations of the haversine formula [http://rosettacode.org/wiki/Haversine_formula in 91 languages at rosettacode.org] and [http://www.codecodex.com/wiki/Calculate_Distance_Between_Two_Points_on_a_Globe in 17 languages on codecodex.com] {{Webarchive|url=https://web.archive.org/web/20180814170246/http://www.codecodex.com/wiki/Calculate_Distance_Between_Two_Points_on_a_Globe |date=2018-08-14 }}
* Other implementations in [http://blog.julien.cayzac.name/2008/10/arc-and-distance-between-two-points-on.html C++], [http://www.jaimerios.com/?p=39 C (MacOS)], [http://scifunam.fisica.unam.mx/mir/codes.html#haversine Pascal] {{Webarchive|url=https://web.archive.org/web/20190116195124/http://scifunam.fisica.unam.mx/mir/codes.html#haversine |date=2019-01-16 }}, [https://stackoverflow.com/a/4913653/1389451 Python], [https://github.com/kristianmandrup/haversine/blob/master/lib/haversine.rb Ruby], [http://www.movable-type.co.uk/scripts/LatLong.html JavaScript], [http://assemblysys.com/geographical-distance-calculation-in-php/  PHP] {{Webarchive|url=https://web.archive.org/web/20180812064108/http://assemblysys.com/geographical-distance-calculation-in-php/ |date=2018-08-12 }},[http://samoht.fr/informatique/distance-between-two-points-on-earth-surface-haversine-formula Matlab] {{Webarchive|url=https://web.archive.org/web/20200513140135/http://samoht.fr/informatique/distance-between-two-points-on-earth-surface-haversine-formula |date=2020-05-13 }}, [https://github.com/Lus71/lib_mysqludf_haversine MySQL]

[[Category:Spherical trigonometry]]
[[Category:Geodesy]]
[[Category:Distance]]