/
Algorithms

Distance between two GPS points

18. 12. 2022

Obsah článku

The approximate distance of two GPS points as the crow flies can be easily calculated by the algorithm:

PHP implementation

function getCoordsDistance(
float $lat1,
float $lng1,
float $lat2,
float $lng2
): float {
$r = 6371;
$lat1 = ($lat1 / 180) * M_PI;
$lat2 = ($lat2 / 180) * M_PI;
$lng1 = ($lng1 / 180) * M_PI;
$lng2 = ($lng2 / 180) * M_PI;
$x = ($lng2 - $lng1) * cos(($lat1 + $lat2) / 2);
$y = $lat2 - $lat1;
$d = sqrt($x * $x + $y * $y) * $r;
return round($d * 1000);
}

This function assumes that the Earth is a perfect sphere, so use the output as an estimate only. For a realistic distance calculation you still need to take into account altitude, terrain shape and local flattening.

I use this function to estimate the distance of e-shop outlets. In the Czech Republic, the average deviation is approximately 5 meters for every 1 km, which is sufficient in real operation.

Implementation in TypeScript

You may need to do the calculation on the client, that's where javascript comes in handy:

export const getCoordsDistance = (
lat1: number,
lng1: number,
lat2: number,
lng2: number
): number => {
const r = 6371;
const subLat1 = (lat1 / 180) * Math.PI;
const subLat2 = (lat2 / 180) * Math.PI;
const subLng1 = (lng1 / 180) * Math.PI;
const subLng2 = (lng2 / 180) * Math.PI;
const x = (subLng2 - subLng1) * Math.cos((subLat1 + subLat2) / 2);
const y = subLat2 - subLat1;
const d = Math.sqrt(x * x + y * y) * r;
return Math.round(d * 1000 * 100000000) / 100000000;
};

How to search for nearby places in the database

To find the surrounding locations in the database around a specific point, you can either use the expensive calculations of the function listed above directly in SQL, or you can do it smartly.

Personally, I use a combination of a pair of algorithms to find nearby locations (for example, branches to checkout from an e-store to a customer).

In the first step, you just load a square area around the selected point (you get this by simply subtracting a constant value from the desired point, and then searching the interval). This gives us a list of candidate outcomes, but we don't yet know exactly how far apart they are, and nothing about their order.

In the second step, we need to figure out if we are looking for points within a specific circle, or if we want to find more distant points on the square. Personally, I recommend cycling through this list of cadidates to calculate the distance from the starting point for each result, and ordering the results by the calculated distance.

In the third step, you can use a simple filter to remove locations that are more than the desired distance from the defined circle.

Jan Barášek   Více o autorovi

Autor článku pracuje jako seniorní vývojář a software architekt v Praze. Navrhuje a spravuje velké webové aplikace, které znáte a používáte. Od roku 2009 nabral bohaté zkušenosti, které tímto webem předává dál.

Rád vám pomůžu:

Související články

1.
6.