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

## Class SphereUtil

• java.lang.Object
• de.lmu.ifi.dbs.elki.math.geodesy.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 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

All 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 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 Complexity: 6 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 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 Complexity: 5 trigonometric functions, 1 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, 1-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.
Constant Field Values
• #### PRECISION

private static final double PRECISION
Maximum desired precision.
Constant Field Values
• #### ONE_SIXTH

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

• #### SphereUtil

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

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

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

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

@Reference(authors="R. W. Sinnott",
title="Virtues of the Haversine",
booktitle="Sky and Telescope 68(2)",
bibkey="journals/skytelesc/Sinnott84")
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

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

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.

@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")
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

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.

@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")
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.

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.

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.

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.

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:

@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")
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.

@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")
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:
• #### 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

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