[Boost-bugs] [Boost C++ Libraries] #11929: haversine method is accurate

Subject: [Boost-bugs] [Boost C++ Libraries] #11929: haversine method is accurate
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2016-01-21 19:03:03

#11929: haversine method is accurate
----------------------------------------+---------------------------
 Reporter:  Charles Karney <charles@…>  |      Owner:  barendgehrels
     Type:  Bugs                        |     Status:  new
Milestone:  To Be Determined            |  Component:  geometry
  Version:  Boost 1.58.0                |   Severity:  Problem
 Keywords:  distance                    |
----------------------------------------+---------------------------
 The following code illustrates a problem with the "haversine" strategy
 for computing great circle distances.  It computes the distance
 between two nearly antipodal points.  The relative error in the result
 is 5e-9, much bigger than you should get with doubles.

 {{{#!c++
 #include <iostream>
 #include <cmath>
 #include <boost/geometry.hpp>

 namespace bg = boost::geometry;
 typedef bg::model::point<double, 2,
                          bg::cs::spherical_equatorial<bg::degree> > pt;

 int main() {
   double pi = std::atan2(0, -1);
   bg::model::segment<pt> seg;
   bg::read_wkt("SEGMENT(0.000001 0, 180 0)", seg);
   double
     // arc length (converted to degrees
     dist = bg::distance(seg.first, seg.second) * (180/pi),
     // the correct distance (in degrees)
     dist0 = 180 - 0.000001,
     err = (dist - dist0) / dist0;
   std::cout << "relative error " << err << "\n";
 }
 }}}

 Running this code gives
 {{{
 relative error 5.55556e-09
 }}}

 Discussion:
 * Surely it's a bad idea to embed the algorithm name "haversine" into
   the API.  Computing great circle distances is really
   straightforward.  Users shouldn't need to worry about the underlying
   method.  Maybe "great_circle" is a better name.
 * The use of haversines made sense when the log haversine function was
   tabulated and you needed trigonometric identities involving products
   to facilitate computations with log tables.  Nowadays there are
   better formulas.
 * As this example illustrates, it's subject to a loss of accuracy with
   antipodal points (it takes the arcsine of a number close to 1.)
 * A good formula to use is given in the Wikipedia article on
   [https://en.wikipedia.org/wiki/Great-circle_navigation#cite_note-2

 great-circle navigation]
   (this is the formula used by Vincenty in the spherical limit
   -- but it surely doesn't originate with him).

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/11929>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.