How is the Euclidean distance calculated

Distance calculation

Martin Kompf

With the growing popularity of GPS devices and tools such as Google Earth or GeoPosition, it is easy to determine the geographic coordinates of points of interest on the earth's surface. This article shows how to use these coordinates to determine the exact straight line distance between two points.

Note: The English notation is used in this article to represent decimal numbers, i.e. the decimal separator is the point.

Geographic coordinates

The surface of the earth resembles the surface of a sphere. Every point on the earth's surface can thus be clearly described by two coordinates: longitude and latitude.

Fig. 1: A point P on the earth's surface can be identified by its longitude and latitude

The geographical latitude (English: Latitude, abbreviated: lat) describes the angle that spans between the center of the earth, the sought-after point P and the equator (blue area in Fig. 1). Points on the equator always have latitude 0, while the north pole has 90 degrees and the south pole -90 degrees latitude. The curve that leads through points of equal width is called the circle of latitude.

The geographical longitude (English: Longitude, abbreviated: lon) describes the angle that results between the center of the earth, the sought point P and the prime meridian (yellow area in Fig. 1). A meridian or longitude leads through the north pole, south pole and all points of the same length. The meridian that leads through the old Greenwich observatory was arbitrarily assigned the value 0 and is therefore the prime meridian. Points east of Greenwich have a longitude between 0 and 180 degrees, west of it between 0 and -180 degrees. The meridians -180 and 180 degrees are identical and represent the extension of the prime meridian.

Examples of geographic coordinates

Easiest distance calculation

The first thing to do is to determine the distance between Rüsselsheim train station and the Opel bridge. The simplest variant is to first take a map of Rüsselsheim with the circles of latitude and longitude drawn in (Fig. 2).

Fig. 2: On the map of Rüsselsheim the longitude and latitude form a rectangular grid

As you can see, the longitude and latitude are straight lines on the map and run parallel or at right angles to each other. To determine the distance for this relatively small area, one can therefore simply view the earth's surface as a plane and use the Pythagorean theorem:

distance = sqrt (dx * dx + dy * dy) with distance: distance in km dx = 71.5 * (lon1 - lon2) dy = 111.3 * (lat1 - lat2) lat1, lat2, lon1, lon2: latitude, longitude in degrees

If you specify longitude and latitude in degrees, the distance results in kilometers. The constant 111.3 is the distance between two circles of latitude in km and 71.5 is the average distance between two circles of longitude in our latitudes.

Improved method

While the distance between two circles of latitude is always 111.3 km, the distance between two circles of longitude varies depending on the geographical latitude: At the equator it is also 111.3 km, at the poles, however, 0. More precisely, the distance is calculated using the formula

111.3 * cos (lat)

This can be incorporated into the calculation formula. A value is selected as the value for lat that lies exactly between lat1 and lat2.

When calculating using a computer, it should be noted that although most programming languages ​​provide the cosine function, this usually expects the angle in radians. The conversion from degrees to radians takes place according to the relationship:

1 ° = π / 180 rad ≈ 0.01745

The complete, improved formula for calculating the distance is then:

distance = sqrt (dx * dx + dy * dy) with distance: distance in km dx = 111.3 * cos (lat) * (lon1 - lon2) lat = (lat1 + lat2) / 2 * 0.01745 dy = 111.3 * (lat1 - lat2) lat1, lat2, lon1, lon2: latitude, longitude in degrees

Exact distance calculation for the spherical surface

Unfortunately, these simple methods fail at greater distances. The reason for this is obvious if you look at a map of Europe, for example (Fig. 3):

Fig. 3: A large area like Europe can no longer be described by the geometry of the plane

The circles of longitude and latitude no longer form a right-angled grid. The reason for this is the spherical shape of the earth. However, it is impossible to roll a spherical surface into a plane without distortion. While you can still ignore the distortion on small maps such as a city map, a map of Europe can no longer be produced in this way.

You have to resort to the methods of spherical trigonometry and take into account what was said at the beginning about the definition of length and width.

Fig. 4: The distance calculation on the spherical surface is done with the help of the spherical triangle

Fig. 4 shows the earth again as a sphere, but now with two points P1 and P2 drawn in, the distance between which is to be determined. This (shortest) distance is also known as the great arc. The points P1 and P2 together with the north pole form a spherical triangle. Two sides of this and the angle they include are known: The side length is equal to the distance of the point from the North Pole, i.e. 90 degrees minus its geographical latitude. The included angle is calculated from the difference between the geographical longitudes of the two points.

It is now possible to determine the length of the third side, which represents the great circular arc you are looking for. The side cosine law is used:

cos (g) = cos (90 ° - lat1) * cos (90 ° - lat2) + sin (90 ° - lat1) * sin (90 ° - lat2) * cos (lon2 - lon1) with g: wanted great arc lat1, lat2, lon1, lon2: latitude, longitude

Since cos (90 ° - a) = sin (a) and sin (90 ° - a) = cos (a), the formula is simplified to:

cos (g) = sin (lat1) * sin (lat2) + cos (lat1) * cos (lat2) * cos (lon2 - lon1)

To get the distance in kilometers, you have to form the arccosine and multiply the result by the earth's radius:

dist = 6378.388 * acos (sin (lat1) * sin (lat2) + cos (lat1) * cos (lat2) * cos (lon2 - lon1)) with dist: distance in km

The formula applies to specifying angles in radians, which is the standard for most programming languages. If, on the other hand, you calculate with a calculator that is set to degrees, then instead of 6378.388 the value 6378.388 * π / 180 = 111.324 should be used.

Evaluation of the methods

Which of the three methods presented is used depends on various factors:

  • Distance of the points
  • Required accuracy
  • Calculation costs (i.e. consumption of time, CPU cycles, ...)

The question of cost differences is no longer so relevant on fast PCs. However, if you have to type in the formulas on the calculator every time, the time required plays a major role.

To compare the accuracy, the formulas are now calculated on the one hand to determine the distance between Rüsselsheim train station and Opel bridge and on the other hand between Berlin and Lisbon:

The calculations were made with a program written in C ++ (source code on GitHub).

For short distances, the three variants are practically equivalent in terms of their accuracy. With distances on a European scale, however, there are drastic differences, so that one should always use the exact method that takes the spherical surface into account.

Supplement 1: Distance calculation for ellipsoids

The previous considerations have always assumed that the earth is a sphere. However, this is not the case. Rather, it represents an irregularly shaped geoid. This shape can best be approximated by an ellipsoid of revolution. An ellipsoid of revolution is determined by two radii, which is why most tables also contain two values ​​for the earth's radius: At the equator and at the pole.

Unfortunately there is no simple formula for the ellipsoid analogous to the side cosine law for the sphere. Calculating distances on the surface of an ellipsoid is much more complicated. Besides, there is no such thing as “the Earth's ellipsoid”, but dozens of them. Depending on where you are on the surface of the earth, you come to different results for the optimal ellipsoid parameters in order to achieve the closest possible approximation to the real surface of the earth. These ellipsoid parameters (major and minor semiaxis, shift of the center point) are often summarized under the term "map datum" or "geodetic datum", of which there are several hundred different. A de facto standardization was only achieved through the spread of the global positioning system (GPS), which uses the reference ellipsoid WGS84.

The development of a tool to determine the exact distance for all possible ellipsoids and map dates is therefore a more complex matter. Fortunately, such tools already exist, in this article PROJ.4 - Cartographic Projections Library should be the tool of choice. Proj.4 is completely available in source code and as a binary distribution for Linux and Windows. There is also a partial porting from Proj.4 to Java with the Java Map Projection Library.

The command line program included in the package is used to calculate the distance geod. The call

geod + ellps = WGS84 + units = km -I

then expects the input of the coordinates of the two points in the format as decimal degrees, for example

49.9917 8.41321 50.0049 8.42182

The last value of the output is then the distance in kilometers. The WGS84 ellipsoid is used for the calculation, i.e. the entered coordinates must be determined in the WGS84 system. This is always the case for the original GPS coordinates, unless the GPS device itself has already carried out a coordinate transformation.

When checking the example, the short distance in Rüsselsheim again results in 1,593 km. The distance Berlin - Lisbon is now calculated as 2318,217 km. The ball method is therefore about 500 meters off, which means an error of 0.02% in relation to the great distance.

Supplement 2: Use of other map grids

The simplified methods of plane trigonometry are completely sufficient to determine short distances. One shortcoming of the given formulas, however, is the need to multiply with the "crooked" values ​​for the distances between the longitudes and latitudes. In addition, the distances between the longitudinal circles are not constant. It would be much nicer if you had coordinates available that do not have these disadvantages, i.e. can be converted directly into distance information.

Such coordinate systems already exist, of course. The best known are the Gauß-Krüger coordinate system in Europe and the UTM coordinate system worldwide. Both coordinate systems allow small areas to be mapped in such a way that they can be covered with a right-angled coordinate system.

These coordinates are then no longer measured in degrees, but in meters. Instead of latitude and longitude, they are usually referred to as high value and legal value or northing and easting.

The GeoPosition tool enables the conversion of geographic coordinates into UTM. For the two well-known places in Rüsselsheim the following results:

Since the coordinates are given in meters and are in the same UTM zone, the distance can be calculated immediately using the Pythagorean theorem and the known value of 1,593 km is obtained again.

In fact, these coordinates are so easy to use that most topographic maps, which only depict a relatively small area, have a UTM coordinate system printed on them instead of "crooked" geographic coordinates.

Links on the subject