de.lmu.ifi.dbs.elki.math.geodesy

Class SphereUtil

java.lang.Object

de.lmu.ifi.dbs.elki.math.geodesy.SphereUtil

@Reference(authors="Ed Williams",
           title="Aviation Formulary",
           booktitle="",
           url="http://williams.best.vwh.net/avform.htm")
public final class SphereUtil
extends 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:

Ed Williams
Aviation Formulary
Online: http://williams.best.vwh.net/avform.htm

TODO: add ellipsoid version of Vinentry formula.

Author:

Erich Schubert, Niels Dörre

Field Summary

Fields

Modifier and Type	Field and 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 and Description
private	SphereUtil() Dummy constructor.

Method Summary

Methods

Modifier and Type	Method and 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 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 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 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 Complexity: 6 (2 of which emulated) trigonometric functions.
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	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 Complexity: 5 trigonometric functions, 2 sqrt.
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, 2 sqrt.
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 (2 of which emulated) trigonometric functions. Reference:

R. W. Sinnott,
Virtues of the Haversine
Sky and telescope, 68-2, 1984

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 (2 of which emulated) 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, 1984

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

@Reference(authors="Sinnott, R. W.",
           title="Virtues of the Haversine",
           booktitle="Sky and telescope, 68-2, 1984")
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, 2 sqrt. Reference:

R. W. Sinnott,
Virtues of the Haversine
Sky and telescope, 68-2, 1984

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="Sinnott, R. W.",
           title="Virtues of the Haversine",
           booktitle="Sky and telescope, 68-2, 1984")
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, 2 sqrt. Reference:

R. W. Sinnott,
Virtues of the Haversine
Sky and telescope, 68-2, 1984

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

@Reference(authors="T. Vincenty",
           title="Direct and inverse solutions of geodesics on the ellipsoid with application of nested equations",
           booktitle="Survey review 23 176, 1975",
           url="http://www.ngs.noaa.gov/PUBS_LIB/inverse.pdf")
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, 1975",
           url="http://www.ngs.noaa.gov/PUBS_LIB/inverse.pdf")
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

@Reference(authors="T. Vincenty",
           title="Direct and inverse solutions of geodesics on the ellipsoid with application of nested equations",
           booktitle="Survey review 23 176, 1975",
           url="http://www.ngs.noaa.gov/PUBS_LIB/inverse.pdf")
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, 1975",
           url="http://www.ngs.noaa.gov/PUBS_LIB/inverse.pdf")
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 S to E. ATD=acos(cos(dist_1Q)/cos(XTD)) TODO: optimize.

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 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 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 and Hans-Peter Kriegel",
           title="Geodetic Distance Queries on R-Trees for Indexing Geographic Data",
           booktitle="Advances in Spatial and Temporal Databases - 13th International Symposium, SSTD 2013, Munich, Germany")
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, 2 sqrt

Reference:

Erich Schubert, Arthur Zimek and Hans-Peter Kriegel
Geodetic Distance Queries on R-Trees for Indexing Geographic Data
Advances in Spatial and Temporal Databases - 13th International Symposium, SSTD 2013, Munich, Germany

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 and Hans-Peter Kriegel",
           title="Geodetic Distance Queries on R-Trees for Indexing Geographic Data",
           booktitle="Advances in Spatial and Temporal Databases - 13th International Symposium, SSTD 2013, Munich, Germany")
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 + (haversine:) 5 trig, 2 sqrt
• Cross-track case: 4+3 trig

Reference:

Erich Schubert, Arthur Zimek and Hans-Peter Kriegel
Geodetic Distance Queries on R-Trees for Indexing Geographic Data
Advances in Spatial and Temporal Databases - 13th International Symposium, SSTD 2013, Munich, Germany

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 and Hans-Peter Kriegel",
           title="Geodetic Distance Queries on R-Trees for Indexing Geographic Data",
           booktitle="Advances in Spatial and Temporal Databases - 13th International Symposium, SSTD 2013, Munich, Germany")
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, 2 sqrt

Reference:

Erich Schubert, Arthur Zimek and Hans-Peter Kriegel
Geodetic Distance Queries on R-Trees for Indexing Geographic Data
Advances in Spatial and Temporal Databases - 13th International Symposium, SSTD 2013, Munich, Germany

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