Class SphereUtil


  • @Reference(authors="E. Williams",
               title="Aviation Formulary",
               booktitle="",
               url="http://www.edwilliams.org/avform.htm",
               bibkey="web/Williams11")
    public final class SphereUtil
    extends java.lang.Object
    Class with utility functions for distance computations on the sphere.

    Note: the formulas are usually implemented for the unit sphere.

    The majority of formulas are adapted from:

    E. Williams
    Aviation Formulary
    Online: http://www.edwilliams.org/avform.htm

    Since:
    0.5.5
    Author:
    Erich Schubert, Niels Dörre
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private static int MAX_ITER
      Maximum number of iterations.
      private static double ONE_SIXTH
      Constant to divide by 6 via multiplication.
      private static double PRECISION
      Maximum desired precision.
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private SphereUtil()
      Dummy constructor.
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static double alongTrackDistanceDeg​(double lat1, double lon1, double lat2, double lon2, double latQ, double lonQ)
      The along track distance is the distance from S to Q along the track from S to E.
      static double alongTrackDistanceDeg​(double lat1, double lon1, double lat2, double lon2, double latQ, double lonQ, double dist1Q, double ctd)
      The along track distance is the distance from S to Q along the track from S to E.
      static double alongTrackDistanceRad​(double lat1, double lon1, double lat2, double lon2, double latQ, double lonQ)
      The along track distance is the distance from S to Q along the track from S to E.
      static double alongTrackDistanceRad​(double lat1, double lon1, double lat2, double lon2, double latQ, double lonQ, double dist1Q, double ctd)
      The along track distance, is the distance from S to Q along the track S to E.
      static double bearingDegDeg​(double latS, double lngS, double latE, double lngE)
      Compute the bearing from start to end.
      static double bearingRad​(double latS, double lngS, double latE, double lngE)
      Compute the bearing from start to end.
      static double cosineFormulaDeg​(double lat1, double lon1, double lat2, double lon2)
      Compute the approximate great-circle distance of two points using the Haversine formula
      static double cosineFormulaRad​(double lat1, double lon1, double lat2, double lon2)
      Compute the approximate great-circle distance of two points using the Spherical law of cosines.
      static double cosineOrHaversineDeg​(double lat1, double lon1, double lat2, double lon2)
      Use cosine or haversine dynamically.
      static double cosineOrHaversineRad​(double lat1, double lon1, double lat2, double lon2)
      Use cosine or haversine dynamically.
      static double crossTrackDistanceDeg​(double lat1, double lon1, double lat2, double lon2, double latQ, double lonQ)
      Compute the cross-track distance.
      static double crossTrackDistanceDeg​(double lat1, double lon1, double lat2, double lon2, double latQ, double lonQ, double dist1Q)
      Compute the cross-track distance.
      static double crossTrackDistanceRad​(double lat1, double lon1, double lat2, double lon2, double latQ, double lonQ)
      Compute the cross-track distance.
      static double crossTrackDistanceRad​(double lat1, double lon1, double lat2, double lon2, double latQ, double lonQ, double dist1Q)
      Compute the cross-track distance.
      static double ellipsoidVincentyFormulaDeg​(double f, double lat1, double lon1, double lat2, double lon2)
      Compute the approximate great-circle distance of two points.
      static double ellipsoidVincentyFormulaRad​(double f, double lat1, double lon1, double lat2, double lon2)
      Compute the approximate great-circle distance of two points.
      static double haversineFormulaDeg​(double lat1, double lon1, double lat2, double lon2)
      Compute the approximate great-circle distance of two points using the Haversine formula
      static double haversineFormulaRad​(double lat1, double lon1, double lat2, double lon2)
      Compute the approximate great-circle distance of two points using the Haversine formula
      static double latlngMinDistDeg​(double plat, double plng, double rminlat, double rminlng, double rmaxlat, double rmaxlng)
      Point to rectangle minimum distance.
      static double latlngMinDistRad​(double plat, double plng, double rminlat, double rminlng, double rmaxlat, double rmaxlng)
      Point to rectangle minimum distance.
      static double latlngMinDistRadFull​(double plat, double plng, double rminlat, double rminlng, double rmaxlat, double rmaxlng)
      Point to rectangle minimum distance.
      static double sphericalVincentyFormulaDeg​(double lat1, double lon1, double lat2, double lon2)
      Compute the approximate great-circle distance of two points.
      static double sphericalVincentyFormulaRad​(double lat1, double lon1, double lat2, double lon2)
      Compute the approximate great-circle distance of two points.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • MAX_ITER

        private static final int MAX_ITER
        Maximum number of iterations.
        See Also:
        Constant Field Values
      • PRECISION

        private static final double PRECISION
        Maximum desired precision.
        See Also:
        Constant Field Values
      • ONE_SIXTH

        private static final double ONE_SIXTH
        Constant to divide by 6 via multiplication.
        See Also:
        Constant Field Values
    • Constructor Detail

      • SphereUtil

        private SphereUtil()
        Dummy constructor. Do not instantiate.
    • Method Detail

      • cosineFormulaDeg

        public static double cosineFormulaDeg​(double lat1,
                                              double lon1,
                                              double lat2,
                                              double lon2)
        Compute the approximate great-circle distance of two points using the Haversine formula

        Complexity: 6 trigonometric functions.

        Reference:

        R. W. Sinnott,
        Virtues of the Haversine
        Sky and Telescope 68(2)

        Parameters:
        lat1 - Latitude of first point in degree
        lon1 - Longitude of first point in degree
        lat2 - Latitude of second point in degree
        lon2 - Longitude of second point in degree
        Returns:
        Distance on unit sphere
      • cosineFormulaRad

        public static double cosineFormulaRad​(double lat1,
                                              double lon1,
                                              double lat2,
                                              double lon2)
        Compute the approximate great-circle distance of two points using the Spherical law of cosines.

        Complexity: 6 trigonometric functions. Note that acos is rather expensive apparently - roughly atan + sqrt.

        Reference:

        R. W. Sinnott,
        Virtues of the Haversine
        Sky and Telescope 68(2)

        Parameters:
        lat1 - Latitude of first point in degree
        lon1 - Longitude of first point in degree
        lat2 - Latitude of second point in degree
        lon2 - Longitude of second point in degree
        Returns:
        Distance on unit sphere
      • haversineFormulaDeg

        public static double haversineFormulaDeg​(double lat1,
                                                 double lon1,
                                                 double lat2,
                                                 double lon2)
        Compute the approximate great-circle distance of two points using the Haversine formula

        Complexity: 5 trigonometric functions, 1 sqrt.

        Reference:

        R. W. Sinnott,
        Virtues of the Haversine
        Sky and Telescope 68(2)

        Parameters:
        lat1 - Latitude of first point in degree
        lon1 - Longitude of first point in degree
        lat2 - Latitude of second point in degree
        lon2 - Longitude of second point in degree
        Returns:
        Distance on unit sphere
      • haversineFormulaRad

        @Reference(authors="R. W. Sinnott",
                   title="Virtues of the Haversine",
                   booktitle="Sky and Telescope 68(2)",
                   bibkey="journals/skytelesc/Sinnott84")
        public static double haversineFormulaRad​(double lat1,
                                                 double lon1,
                                                 double lat2,
                                                 double lon2)
        Compute the approximate great-circle distance of two points using the Haversine formula

        Complexity: 5 trigonometric functions, 1-2 sqrt.

        Reference:

        R. W. Sinnott,
        Virtues of the Haversine
        Sky and Telescope 68(2)

        Parameters:
        lat1 - Latitude of first point in degree
        lon1 - Longitude of first point in degree
        lat2 - Latitude of second point in degree
        lon2 - Longitude of second point in degree
        Returns:
        Distance on unit sphere
      • cosineOrHaversineDeg

        public static double cosineOrHaversineDeg​(double lat1,
                                                  double lon1,
                                                  double lat2,
                                                  double lon2)
        Use cosine or haversine dynamically. Complexity: 4-5 trigonometric functions, 1 sqrt.
        Parameters:
        lat1 - Latitude of first point in degree
        lon1 - Longitude of first point in degree
        lat2 - Latitude of second point in degree
        lon2 - Longitude of second point in degree
        Returns:
        Distance on unit sphere
      • cosineOrHaversineRad

        public static double cosineOrHaversineRad​(double lat1,
                                                  double lon1,
                                                  double lat2,
                                                  double lon2)
        Use cosine or haversine dynamically.

        Complexity: 4-5 trigonometric functions, 1 sqrt.

        Parameters:
        lat1 - Latitude of first point in degree
        lon1 - Longitude of first point in degree
        lat2 - Latitude of second point in degree
        lon2 - Longitude of second point in degree
        Returns:
        Distance on unit sphere
      • sphericalVincentyFormulaDeg

        public static double sphericalVincentyFormulaDeg​(double lat1,
                                                         double lon1,
                                                         double lat2,
                                                         double lon2)
        Compute the approximate great-circle distance of two points. Uses Vincenty's Formula for the spherical case, which does not require iterations.

        Complexity: 7 trigonometric functions, 1 sqrt.

        Reference:

        T. Vincenty
        Direct and inverse solutions of geodesics on the ellipsoid with application of nested equations
        Survey Review 23:176, 1975

        Parameters:
        lat1 - Latitude of first point in degree
        lon1 - Longitude of first point in degree
        lat2 - Latitude of second point in degree
        lon2 - Longitude of second point in degree
        Returns:
        Distance in radians / on unit sphere.
      • sphericalVincentyFormulaRad

        @Reference(authors="T. Vincenty",
                   title="Direct and inverse solutions of geodesics on the ellipsoid with application of nested equations",
                   booktitle="Survey Review 23:176",
                   url="https://doi.org/10.1179/sre.1975.23.176.88",
                   bibkey="doi:10.1179/sre.1975.23.176.88")
        public static double sphericalVincentyFormulaRad​(double lat1,
                                                         double lon1,
                                                         double lat2,
                                                         double lon2)
        Compute the approximate great-circle distance of two points. Uses Vincenty's Formula for the spherical case, which does not require iterations.

        Complexity: 7 trigonometric functions, 1 sqrt.

        Reference:

        T. Vincenty
        Direct and inverse solutions of geodesics on the ellipsoid with application of nested equations
        Survey review 23 176, 1975

        Parameters:
        lat1 - Latitude of first point in degree
        lon1 - Longitude of first point in degree
        lat2 - Latitude of second point in degree
        lon2 - Longitude of second point in degree
        Returns:
        Distance on unit sphere
      • ellipsoidVincentyFormulaDeg

        public static double ellipsoidVincentyFormulaDeg​(double f,
                                                         double lat1,
                                                         double lon1,
                                                         double lat2,
                                                         double lon2)
        Compute the approximate great-circle distance of two points.

        Reference:

        T. Vincenty
        Direct and inverse solutions of geodesics on the ellipsoid with application of nested equations
        Survey review 23 176, 1975

        Parameters:
        f - Ellipsoid flattening
        lat1 - Latitude of first point in degree
        lon1 - Longitude of first point in degree
        lat2 - Latitude of second point in degree
        lon2 - Longitude of second point in degree
        Returns:
        Distance for a minor axis of 1.
      • ellipsoidVincentyFormulaRad

        @Reference(authors="T. Vincenty",
                   title="Direct and inverse solutions of geodesics on the ellipsoid with application of nested equations",
                   booktitle="Survey Review 23:176",
                   url="https://doi.org/10.1179/sre.1975.23.176.88",
                   bibkey="doi:10.1179/sre.1975.23.176.88")
        public static double ellipsoidVincentyFormulaRad​(double f,
                                                         double lat1,
                                                         double lon1,
                                                         double lat2,
                                                         double lon2)
        Compute the approximate great-circle distance of two points.

        Reference:

        T. Vincenty
        Direct and inverse solutions of geodesics on the ellipsoid with application of nested equations
        Survey review 23 176, 1975

        Parameters:
        f - Ellipsoid flattening
        lat1 - Latitude of first point in degree
        lon1 - Longitude of first point in degree
        lat2 - Latitude of second point in degree
        lon2 - Longitude of second point in degree
        Returns:
        Distance for a minor axis of 1.
      • crossTrackDistanceDeg

        public static double crossTrackDistanceDeg​(double lat1,
                                                   double lon1,
                                                   double lat2,
                                                   double lon2,
                                                   double latQ,
                                                   double lonQ)
        Compute the cross-track distance.

        XTD = asin(sin(dist_1Q)*sin(crs_1Q-crs_12))

        Parameters:
        lat1 - Latitude of starting point.
        lon1 - Longitude of starting point.
        lat2 - Latitude of destination point.
        lon2 - Longitude of destination point.
        latQ - Latitude of query point.
        lonQ - Longitude of query point.
        Returns:
        Cross-track distance in km. May be negative - this gives the side.
      • crossTrackDistanceRad

        public static double crossTrackDistanceRad​(double lat1,
                                                   double lon1,
                                                   double lat2,
                                                   double lon2,
                                                   double latQ,
                                                   double lonQ,
                                                   double dist1Q)
        Compute the cross-track distance.
        Parameters:
        lat1 - Latitude of starting point.
        lon1 - Longitude of starting point.
        lat2 - Latitude of destination point.
        lon2 - Longitude of destination point.
        latQ - Latitude of query point.
        lonQ - Longitude of query point.
        dist1Q - Distance from starting point to query point on unit sphere
        Returns:
        Cross-track distance on unit sphere. May be negative - this gives the side.
      • crossTrackDistanceDeg

        public static double crossTrackDistanceDeg​(double lat1,
                                                   double lon1,
                                                   double lat2,
                                                   double lon2,
                                                   double latQ,
                                                   double lonQ,
                                                   double dist1Q)
        Compute the cross-track distance.
        Parameters:
        lat1 - Latitude of starting point.
        lon1 - Longitude of starting point.
        lat2 - Latitude of destination point.
        lon2 - Longitude of destination point.
        latQ - Latitude of query point.
        lonQ - Longitude of query point.
        dist1Q - Distance from starting point to query point in radians (i.e. on unit sphere).
        Returns:
        Cross-track distance on unit sphere. May be negative - this gives the side.
      • crossTrackDistanceRad

        public static double crossTrackDistanceRad​(double lat1,
                                                   double lon1,
                                                   double lat2,
                                                   double lon2,
                                                   double latQ,
                                                   double lonQ)
        Compute the cross-track distance.

        XTD = asin(sin(dist_SQ)*sin(crs_SQ-crs_SE))

        Parameters:
        lat1 - Latitude of starting point.
        lon1 - Longitude of starting point.
        lat2 - Latitude of destination point.
        lon2 - Longitude of destination point.
        latQ - Latitude of query point.
        lonQ - Longitude of query point.
        Returns:
        Cross-track distance in km. May be negative - this gives the side.
      • alongTrackDistanceDeg

        public static double alongTrackDistanceDeg​(double lat1,
                                                   double lon1,
                                                   double lat2,
                                                   double lon2,
                                                   double latQ,
                                                   double lonQ)
        The along track distance is the distance from S to Q along the track from S to E.

        ATD=acos(cos(dist_1Q)/cos(XTD))

        Parameters:
        lat1 - Latitude of starting point.
        lon1 - Longitude of starting point.
        lat2 - Latitude of destination point.
        lon2 - Longitude of destination point.
        latQ - Latitude of query point.
        lonQ - Longitude of query point.
        Returns:
        Along-track distance in radians. May be negative - this gives the side.
      • alongTrackDistanceRad

        public static double alongTrackDistanceRad​(double lat1,
                                                   double lon1,
                                                   double lat2,
                                                   double lon2,
                                                   double latQ,
                                                   double lonQ)
        The along track distance is the distance from S to Q along the track from S to E.

        ATD=acos(cos(dist_1Q)/cos(XTD))

        TODO: optimize.

        Parameters:
        lat1 - Latitude of starting point in radians.
        lon1 - Longitude of starting point in radians.
        lat2 - Latitude of destination point in radians.
        lon2 - Longitude of destination point in radians.
        latQ - Latitude of query point in radians.
        lonQ - Longitude of query point in radians.
        Returns:
        Along-track distance in radians. May be negative - this gives the side.
      • alongTrackDistanceDeg

        public static double alongTrackDistanceDeg​(double lat1,
                                                   double lon1,
                                                   double lat2,
                                                   double lon2,
                                                   double latQ,
                                                   double lonQ,
                                                   double dist1Q,
                                                   double ctd)
        The along track distance is the distance from S to Q along the track from S to E.

        ATD=acos(cos(dist_SQ)/cos(XTD))

        Parameters:
        lat1 - Latitude of starting point.
        lon1 - Longitude of starting point.
        lat2 - Latitude of destination point.
        lon2 - Longitude of destination point.
        latQ - Latitude of query point.
        lonQ - Longitude of query point.
        dist1Q - Distance S to Q in radians.
        ctd - Cross-track-distance in radians.
        Returns:
        Along-track distance in radians. May be negative - this gives the side.
      • alongTrackDistanceRad

        public static double alongTrackDistanceRad​(double lat1,
                                                   double lon1,
                                                   double lat2,
                                                   double lon2,
                                                   double latQ,
                                                   double lonQ,
                                                   double dist1Q,
                                                   double ctd)
        The along track distance, is the distance from S to Q along the track S to E.

        ATD=acos(cos(dist_SQ)/cos(XTD))

        TODO: optimize: can we do a faster sign computation?

        Parameters:
        lat1 - Latitude of starting point in radians.
        lon1 - Longitude of starting point in radians.
        lat2 - Latitude of destination point in radians.
        lon2 - Longitude of destination point in radians.
        latQ - Latitude of query point in radians.
        lonQ - Longitude of query point in radians.
        dist1Q - Distance S to Q in radians.
        ctd - Cross-track-distance in radians.
        Returns:
        Along-track distance in radians. May be negative - this gives the side.
      • latlngMinDistDeg

        @Reference(authors="Erich Schubert, Arthur Zimek, Hans-Peter Kriegel",
                   title="Geodetic Distance Queries on R-Trees for Indexing Geographic Data",
                   booktitle="Int. Symp. Advances in Spatial and Temporal Databases (SSTD\'2013)",
                   url="https://doi.org/10.1007/978-3-642-40235-7_9",
                   bibkey="DBLP:conf/ssd/SchubertZK13")
        public static double latlngMinDistDeg​(double plat,
                                              double plng,
                                              double rminlat,
                                              double rminlng,
                                              double rmaxlat,
                                              double rmaxlng)
        Point to rectangle minimum distance.

        Complexity:

        • Trivial cases (on longitude slice): no trigonometric functions.
        • Cross-track case: 10+2 trig
        • Corner case: 10+3 trig, 1 sqrt

        Reference:

        Erich Schubert, Arthur Zimek, Hans-Peter Kriegel
        Geodetic Distance Queries on R-Trees for Indexing Geographic Data
        Int. Symp. Advances in Spatial and Temporal Databases (SSTD'2013)

        Parameters:
        plat - Latitude of query point.
        plng - Longitude of query point.
        rminlat - Min latitude of rectangle.
        rminlng - Min longitude of rectangle.
        rmaxlat - Max latitude of rectangle.
        rmaxlng - Max longitude of rectangle.
        Returns:
        Distance in radians.
      • latlngMinDistRad

        @Reference(authors="Erich Schubert, Arthur Zimek, Hans-Peter Kriegel",
                   title="Geodetic Distance Queries on R-Trees for Indexing Geographic Data",
                   booktitle="Int. Symp. Advances in Spatial and Temporal Databases (SSTD\'2013)",
                   url="https://doi.org/10.1007/978-3-642-40235-7_9",
                   bibkey="DBLP:conf/ssd/SchubertZK13")
        public static double latlngMinDistRad​(double plat,
                                              double plng,
                                              double rminlat,
                                              double rminlng,
                                              double rmaxlat,
                                              double rmaxlng)
        Point to rectangle minimum distance.

        Complexity:

        • Trivial cases (on longitude slice): no trigonometric functions.
        • Corner case: 3/4 trig + 4-5 trig, 1 sqrt
        • Cross-track case: 4+2 trig

        Important: Rectangles must be in -pi:+pi, and must have min < max, so they cannot cross the date line.

        Reference:

        Erich Schubert, Arthur Zimek, Hans-Peter Kriegel
        Geodetic Distance Queries on R-Trees for Indexing Geographic Data
        Int. Symp. Advances in Spatial and Temporal Databases (SSTD'2013)

        Parameters:
        plat - Latitude of query point.
        plng - Longitude of query point.
        rminlat - Min latitude of rectangle.
        rminlng - Min longitude of rectangle.
        rmaxlat - Max latitude of rectangle.
        rmaxlng - Max longitude of rectangle.
        Returns:
        Distance on unit sphere.
      • latlngMinDistRadFull

        @Reference(authors="Erich Schubert, Arthur Zimek, Hans-Peter Kriegel",
                   title="Geodetic Distance Queries on R-Trees for Indexing Geographic Data",
                   booktitle="Int. Symp. Advances in Spatial and Temporal Databases (SSTD\'2013)",
                   url="https://doi.org/10.1007/978-3-642-40235-7_9",
                   bibkey="DBLP:conf/ssd/SchubertZK13")
        public static double latlngMinDistRadFull​(double plat,
                                                  double plng,
                                                  double rminlat,
                                                  double rminlng,
                                                  double rmaxlat,
                                                  double rmaxlng)
        Point to rectangle minimum distance.

        Previous version, only around for reference.

        Complexity:

        • Trivial cases (on longitude slice): no trigonometric functions.
        • Cross-track case: 10+2 trig
        • Corner case: 10+3 trig, 1 sqrt

        Reference:

        Erich Schubert, Arthur Zimek, Hans-Peter Kriegel
        Geodetic Distance Queries on R-Trees for Indexing Geographic Data
        Int. Symp. Advances in Spatial and Temporal Databases (SSTD'2013)

        Parameters:
        plat - Latitude of query point.
        plng - Longitude of query point.
        rminlat - Min latitude of rectangle.
        rminlng - Min longitude of rectangle.
        rmaxlat - Max latitude of rectangle.
        rmaxlng - Max longitude of rectangle.
        Returns:
        Distance in radians
      • bearingDegDeg

        public static double bearingDegDeg​(double latS,
                                           double lngS,
                                           double latE,
                                           double lngE)
        Compute the bearing from start to end.
        Parameters:
        latS - Start latitude, in degree
        lngS - Start longitude, in degree
        latE - End latitude, in degree
        lngE - End longitude, in degree
        Returns:
        Bearing in degree
      • bearingRad

        public static double bearingRad​(double latS,
                                        double lngS,
                                        double latE,
                                        double lngE)
        Compute the bearing from start to end.
        Parameters:
        latS - Start latitude, in radians
        lngS - Start longitude, in radians
        latE - End latitude, in radians
        lngE - End longitude, in radians
        Returns:
        Bearing in degree