News Archive
PhpRiot Newsletter
Your Email Address:

More information

Spatial Indexes: Calculating Distance

Note: This article was originally published at Planet PHP on 9 March 2011.
Planet PHP

Spatial Indexes: Calculating Distance

MontrAal, Canada Wednesday, March 9th 2011, 07:17 EST

During my "Geolocation and Mapping with PHP" talk that I've given a few times I briefly touch on the subject of indexes on data-sets of spatial data. This isn't as simple as just solving Pythagoras theorem and this article is meant to clarify this.

The flat Earth model

Pythagoras theorem can be used to calculate the distance between two points quite easily; you take the square root of the square of the absolute vertical distance plus the square of the absolute horizontal distance; in short:

d = as(|x1 - x2|A + |y1 - y2|A)

or in PHP:

$d = sqrt(pow(abs($x1 - $x2), 2) + pow(abs($y1 - $y2), 2));

If you take for example London's coordinates (51.50AN, 0.13AW) and Amsterdam's coordinates (52.37AN, 4.90AE) we can calculate the distance with:

d = as(|-0.13 - 4.90|A + |51.50 - 52.37|A) d = as(5.03A + 0.87A) d = as(26.0578) d a... 5.10

And on a map:

But what does a difference of "5.10A" actually mean? How far is this in useful units, such as meters?

If we show the whole map of which the above is an extract, we come to:

The distance around the equator, and through the poles is roughly the same, 40.000km (please be aware that the blue line only shows half of it, the other half is going through the anti-meridian at 180AW/E). 5.03A in East-West difference is then about 40 000 ao (5.03/360) = 559 km and the North-South difference about 20 000 ao (0.87/180) = 97 km. Using those numbers within the Pythagoras theorem we end up with a distance of as(559A + 97A) = 567 km. Although the calculation is correct, the answer is still wrong. The real distance is closer to 360 km.

The spherical Earth model

If we look at the Earth in its original (mostly) spherical 1 shape, then it's clear that 10A longitude (East/West) at 60AN is going to be less of a distance than 10AE/W at the equator. It's actually fairly easy to calculate how much 1A longitude is at 60AN by using cos(60) * 1/360 * 6371 * 2I 2. Or in PHP:

This returns 55.597 km per A for 60AN. The same distance in degrees on the Equator gives 6371 * 2 * M_PI / 360 = 111.195.

The following diagram shows ones more that latitudinal degrees always correspond with the same distance in kilometer, whereas longitudinal degrees differ.

In the diagram the line A is a line from 0AN, 90AW to 10AN, 90AW. It has the same length as line B, from 30AN, 90AW to 40AN, 90AW: a 36th of the circumference of the Earth through the poles. Line C, from 0AN, 30AW to 0AN, 20AW has the same length. Line D however, from 50AN, 30AW to 50AN, 20AW is shorter by a factor of cos(50A) a... 0.64.

If we look again at the distance between London and Amsterdam, ignore the differences in latitude and instead pick the average, we see:

Which is a bit shorter than the expected 360km, but that's because we conveniently forgot about the difference in latitude.

Sadly, we can't use Pythagoras's theorem to calculate the real distance with the latitude difference taken account as well. This is because the theorem is meant for Euclidean geometry, and a sphere does not follow the rules of this geometry. Instead we need to use a formula that is called the great-circle distance

Truncated by Planet PHP, read more at the original (another 2340 bytes)