Click here to Skip to main content
13,199,852 members (65,819 online)
Click here to Skip to main content
Add your own
alternative version

Tagged as

Stats

5.6K views
8 bookmarked
Posted 23 Jun 2015

The Orthodromic Distance Between Two Geo-points

, 23 Jun 2015
Rate this:
Please Sign up or sign in to vote.
Computational algorithms pertinent to finding the great-circle distance between 2 points on Earth

Introduction

Calculation of the great-circle (orthodromic) distance between two geo-points on the Earth surface is one of the core Geographic Information System (GIS) problems. This seemingly trivial task requires quite non-trivial algorithmic solution. Indeed, should the problem pertains to the plane geometry, then Pythagorean Theorem will provide a sort of "no-brainer" solution. But the actual GIS computations are dealing with 3d-models, namely spherical Earth representation, which requires more elaborate solution. Another level of complexity relates to more accurate ellipsoidal Earth model, which is sort of "overkill" for the majority of practical application. Spherical model results in systemic error margin within 0.3% which is acceptible for most commercial-grade apps. The second one (i.e. ellipsoidal model of the Earth ) theoretically limits error margin to the fraction of mm while dramatically increasing the computational complexity. The following solution is based on the spherical Earth model, describing 3 practical algorithms written in C#, which differ by the computational performance/accuracy [1-3].

Background

Mathematically speaking, all three algos described below result in computation of a great-circle (orthodromic) distance on Earth between 2 points, though the accuracy and performance are different. They all are based on spherical model of the Earth and provide reasonably good approximation with error margin typically not exceeding couple meters within NY City boundaries. More accurate ellipsoidal Earth model and corresponding high-accuracy Vincenty’s solution [4] exists reducing the error margin to the fraction of mm, but also substantially increasing the computational complexity beyond the reasonable level. Therefore, 3 following algorithms based on spherical Earth model has been developed and recommended for general commercial apps, having good computational performance and reasonable accuracy.

Using the code

Below you can find three algoritmic solutions pertinent to the calculation of the great-circle (orthodromic) distance between two geo-points on the Earth surface

Listing 1. Basic GIS functions to calculate distance between two geo-points on the surface

/*****************************************************************************************
Module           :  GIS.cs |Class Lib
Description      :  Calculate distance between two geo-points on surface
*****************************************************************************************
Author           :  Alexander Bell
Copyright        :  2011-2015 Infosoft International Inc
*****************************************************************************************
DISCLAIMER       :  This Module is provided on AS IS basis without any warranty
*****************************************************************************************
TERMS OF USE     :  This module is copyrighted. Please keep the Copyright notice intact.
*****************************************************************************************/
using System;

namespace BusNY
{
    internal enum UnitSystem { SI = 0, US = 1 }
    
    internal static class GIS
    {
        #region internal: properties (read-only)
        internal static double EarthRadiusKm { get {return _radiusEarthKM;} }
        internal static double EarthRadiusMiles { get { return _radiusEarthMiles; } }
        internal static double m2km { get { return _m2km; } }
        internal static double Deg2rad { get { return _toRad; } }
        #endregion

        #region private: const
        private const double _radiusEarthMiles = 3959;
        private const double _radiusEarthKM = 6371;
        private const double _m2km = 1.60934;
        private const double _toRad = Math.PI / 180;
        #endregion

        #region Method 1: Haversine algo
        /// <summary>
        /// Distance between two geographic points on surface, km/miles
        /// Haversine formula to calculate
        /// great-circle (orthodromic) distance on Earth
        /// High Accuracy, Medium speed
        /// re: http://en.wikipedia.org/wiki/Haversine_formula
        /// </summary>
        /// <param name="Lat1">double: 1st point Latitude</param>
        /// <param name="Lon1">double: 1st point Longitude</param>
        /// <param name="Lat2">double: 2nd point Latitude</param>
        /// <param name="Lon2">double: 2nd point Longitude</param>
        /// <returns>double: distance, km/miles</returns>
        internal static double DistanceHaversine(double Lat1,
                                                    double Lon1,
                                                    double Lat2,
                                                    double Lon2,
                                                    UnitSystem UnitSys ){
            try {
                double _radLat1 = Lat1 * _toRad;
                double _radLat2 = Lat2 * _toRad;
                double _dLatHalf = (_radLat2 - _radLat1) / 2;
                double _dLonHalf = Math.PI * (Lon2 - Lon1) / 360;

                // intermediate result
                double _a = Math.Sin(_dLatHalf);
                _a *= _a;

                // intermediate result
                double _b = Math.Sin(_dLonHalf);
                _b *= _b * Math.Cos(_radLat1) * Math.Cos(_radLat2);

                // central angle, aka arc segment angular distance
                double _centralAngle = 2 * Math.Atan2(Math.Sqrt(_a + _b), Math.Sqrt(1 - _a - _b));

                // great-circle (orthodromic) distance on Earth between 2 points
                if (UnitSys == UnitSystem.SI)  { return _radiusEarthKM * _centralAngle; }
                else { return _radiusEarthMiles * _centralAngle; }
            }
            catch { throw; }
        }
        #endregion

        #region Method 2: Spherical Law of Cosines
        /// <summary>
        /// Distance between two geographic points on surface, km/miles
        /// Spherical Law of Cosines formula to calculate
        /// great-circle (orthodromic) distance on Earth;
        /// High Accuracy, Medium speed
        /// re: http://en.wikipedia.org/wiki/Spherical_law_of_cosines
        /// </summary>
        /// <param name="Lat1">double: 1st point Latitude</param>
        /// <param name="Lon1">double: 1st point Longitude</param>
        /// <param name="Lat2">double: 2nd point Latitude</param>
        /// <param name="Lon2">double: 2nd point Longitude</param>
        /// <returns>double: distance, km/miles</returns>
        internal static double DistanceSLC(double Lat1,
                                        double Lon1,
                                        double Lat2,
                                        double Lon2,
                                        UnitSystem UnitSys ){
            try {
                double _radLat1 = Lat1 * _toRad;
                double _radLat2 = Lat2 * _toRad;
                double _radLon1 = Lon1 * _toRad;
                double _radLon2 = Lon2 * _toRad;

                // central angle, aka arc segment angular distance
                double _centralAngle = Math.Acos(Math.Sin(_radLat1) * Math.Sin(_radLat2) +
                        Math.Cos(_radLat1) * Math.Cos(_radLat2) * Math.Cos(_radLon2 - _radLon1));

                // great-circle (orthodromic) distance on Earth between 2 points
                if (UnitSys == UnitSystem.SI) { return _radiusEarthKM * _centralAngle; }
                else { return _radiusEarthMiles * _centralAngle; }
            }
            catch { throw; }
        }
        #endregion

        #region Method 3: Spherical Earth projection
        /// <summary>
        /// Distance between two geographic points on surface, km/miles
        /// Spherical Earth projection to a plane formula (using Pythagorean Theorem)
        /// to calculate great-circle (orthodromic) distance on Earth.
        /// central angle =
        /// Sqrt((_radLat2 - _radLat1)^2 + (Cos((_radLat1 + _radLat2)/2) * (Lon2 - Lon1))^2)
        /// Medium Accuracy, Fast,
        /// relative error less than 0.1% in search area smaller than 250 miles
        /// re: http://en.wikipedia.org/wiki/Geographical_distance
        /// </summary>
        /// <param name="Lat1">double: 1st point Latitude</param>
        /// <param name="Lon1">double: 1st point Longitude</param>
        /// <param name="Lat2">double: 2nd point Latitude</param>
        /// <param name="Lon2">double: 2nd point Longitude</param>
        /// <returns>double: distance, km/miles</returns>
        public static double DistanceSEP(double Lat1,
                                        double Lon1,
                                        double Lat2,
                                        double Lon2,
                                        UnitSystem UnitSys ){
            try
            {
                double _radLat1 = Lat1 * _toRad;
                double _radLat2 = Lat2 * _toRad;
                double _dLat = (_radLat2 - _radLat1);
                double _dLon = (Lon2 - Lon1) * _toRad;

                double _a = (_dLon) * Math.Cos((_radLat1 + _radLat2) / 2);

                // central angle, aka arc segment angular distance
                double _centralAngle = Math.Sqrt(_a * _a + _dLat * _dLat);

                // great-circle (orthodromic) distance on Earth between 2 points
                if (UnitSys == UnitSystem.SI) { return _radiusEarthKM * _centralAngle; }
                else { return _radiusEarthMiles * _centralAngle; }
            }
            catch { throw; }
        }
        #endregion
    }
}

 

Points of Interest

The algorithms mentioned above has been partially described in a context of the real-time NY City bus tracking app [6], currentlyt avilable online (click on the link image below):

History

  • Oct 2012: The topic was briefly discussed in IoT contest submission article [5].
  • Jun 2015: Extended version has been published

Reference

  1. Haversine Formula (wiki)
  2. Spherical law of cosines (wiki)
  3. Geographical distance (wiki)
  4. Vincenty solutions of geodesics on the ellipsoid
  5. Edumatter-814: School Math Calculators and Equation Solvers
  6. enRoute, Real-time NY City Bus Tracking Web App

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

DrABELL
President Infosoft International Inc
United States United States
Dr. Alexander Bell is a seasoned full-stack Software Engineer (Win/Web/Mobile). He holds PhD in EE/IT, authored 37 inventions and published 300+ technical articles. Currently focused on HTML5/CSS3, Javascript, .NET/WPF/C#, Angular.js, SQL, 'Big Data', Machine Learning, AI, IoT. Alex participated in App Innovation Contests (AIC 2102/2013) with multiple winning submissions. Portfolio samples:

  1. Real-time NY Bus Tracking Web App (IoT)
  2. Integrated Sensors Hub (IMU) Testing Web Page
  3. Semaphon™ semantic phone num-to-text converter
  4. Educational Web Portal
  5. Free Online NY Payroll Tax Calculator
  6. WebTV powered by YouTube Player powered by .NET API (#1 on Google)
  7. Top-50 Digital Cameras (by iMark-DCAM rating engine)
  8. Engineering Calculator VOLTA
  9. Big Data: Facebook and YouTube
  10. NY City Trivia Quiz
  11. NY Photo Gallery
  12. Publications by A. Bell

You may also be interested in...

Pro

Comments and Discussions

 
-- There are no messages in this forum --
Permalink | Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.171020.1 | Last Updated 23 Jun 2015
Article Copyright 2015 by DrABELL
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid