SphereUtil (ELKI: Environment for DeveLoping KDD-Applications Supported by Index-Structures)

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.

Constructors
Modifier	Constructor and Description
`private`	`SphereUtil()` Dummy constructor.

Method Summary

All Methods Static Methods Concrete 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.
  
  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

Class SphereUtil

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

MAX_ITER

PRECISION

ONE_SIXTH

Constructor Detail

SphereUtil

Method Detail

cosineFormulaDeg

cosineFormulaRad

haversineFormulaDeg

haversineFormulaRad

cosineOrHaversineDeg

cosineOrHaversineRad

sphericalVincentyFormulaDeg

sphericalVincentyFormulaRad

ellipsoidVincentyFormulaDeg

ellipsoidVincentyFormulaRad

crossTrackDistanceDeg

crossTrackDistanceRad

crossTrackDistanceDeg

crossTrackDistanceRad

alongTrackDistanceDeg

alongTrackDistanceRad

alongTrackDistanceDeg

alongTrackDistanceRad

latlngMinDistDeg

latlngMinDistRad

latlngMinDistRadFull

bearingDegDeg

bearingRad