Geographical distance between all points greater than a value with mysql

Question

From a list of restaurants with a latitude and a longitude, how can I get points that have at least X km between all of them?

I mean, that each restaurant doesn't has any other restaurant in a radius of X km.

I tried the next query:

SELECT 
    id,
    lat as x, 
    lng as y,
    concat(ceil((lat+90)/5),',',ceil((lng+180)/5)) as groupParam
FROM 
    restaurants 
GROUP BY groupParam

And the result is this:

result of the query

In that query I'm grouping by a rounded latitude and longitude (ex: "12,23"). So I only get a node from (lat >= 12 && lat <13) and (lng >= 23 && lng < 24).

Thats fast but not very accurate.

Thanks, Wiliam.

Hope it helps... http://stackoverflow.com/questions/11586708/get-results-that-fall-within-marker-radiuses-from-database — jsist, Aug 03 '12 at 18:26

score 0 · Answer 1 · answered Jul 21 '12 at 01:31

I did some lon/lat calculations for a hamradio database I wrote as an webapp: http://dk7sl.de/iRelais

Here is the select statement, where $x and $y are my lon/lat coordinates. maximum distance is set to 15 km. You could switch to miles if you just remove the '*1.609344' in the query. This query selects the nearest entry in the geodata table. Geodata was taken from http://www.geodatasource.com/world-cities-database/free and contains approx 2.4 million records in my mysqldb. DB-Indexes are on latitude, longitude, feature class and feature code (but that's just because I filter the entries by feature class and code)

$query = "SELECT name, (((ACOS(SIN('".$x."' * PI() / 180) * SIN(latitude * PI() / 180) + COS(".$x." * PI() / 180) * COS(latitude * PI() / 180) * COS(('".$y."' - longitude) * PI() / 180)) * 180 / PI()) * 60 * 1.1515))*1.609344 AS distance FROM geodata WHERE feature class = 'P' AND (feature code = 'PPLX' OR feature code = 'PPL') HAVING distance<='15' ORDER BY distance ASC LIMIT 1;";

maybe you can use my select statement and modify it so you get the right group of points out of your database.

Ross Smith II · Answer 2 · 2012-07-21T21:25:50.490

Answer to your original question:

I think this will provide you what you are looking for:

SELECT DISTINCT
    a.id AS a,
    b.id AS b,
    ACOS(
        SIN(a.lat) * SIN(b.lat) + COS(a.lat) * COS(b.lat) * COS(a.lon - b.lon)
    ) * 6371.01 AS km
FROM 
    restaurants a,
    restaurants b
WHERE
    b.id > a.id AND
    ACOS(
        SIN(a.lat) * SIN(b.lat) + COS(a.lat) * COS(b.lat) * COS(a.lon - b.lon)
    ) * 6371.01 >= X
ORDER BY
    ACOS(
        SIN(a.lat) * SIN(b.lat) + COS(a.lat) * COS(b.lat) * COS(a.lon - b.lon)
    );

where X is the minimum kilometers you want between them.

Unfortunately, this type of query is a CROSS JOIN returning a Cartesian Product, so with 10 restaurants, you'll have 36 comparisons, 100 you'll have 4,851, 1,000 you'll have 498,501, etc.

Answer to your revised question:

To find all restaurants that are at least X kilometers away from any other restaurant, use this:

SELECT
    a.id AS a,
    MIN(ACOS(
        SIN(a.lat) * SIN(b.lat) + COS(a.lat) * COS(b.lat) * COS(a.lon - b.lon)
    ) * 6371.01) AS km
FROM 
    restaurants a,
    restaurants b
WHERE
    b.id > a.id
GROUP BY
    a.id
HAVING
    MIN(ACOS(
        SIN(a.lat) * SIN(b.lat) + COS(a.lat) * COS(b.lat) * COS(a.lon - b.lon)
    ) * 6371.01) >= X
ORDER BY
    MIN(ACOS(
        SIN(a.lat) * SIN(b.lat) + COS(a.lat) * COS(b.lat) * COS(a.lon - b.lon)
    ) * 6371.01)

where X is the minimum kilometers you want between them.

Thanks, but I want 150 km between all of them, I mean, with (A,B,C) there can be 150km between A-B, B-C but that not guarantees A-C. — Wiliam, Jul 21 '12 at 19:54
Sorry, I don't quite follow. You want the sum of the distances between restruants A, B and C to be 150kms or greater? That isn't what you originally asked. — Ross Smith II, Jul 21 '12 at 21:12

Geographical distance between all points greater than a value with mysql

2 Answers2