## Class SphereUtil

• java.lang.Object
• 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 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
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.
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 lngE)
latS - Start latitude, in radians
lngS - Start longitude, in radians
latE - End latitude, in radians
lngE - End longitude, in radians