Как эффективно находить группы местоположений GPS, находящихся на определенном расстоянии?

Я разрабатываю приложение PHP, которое работает с набором местоположений, предоставленных через широту, долготу-координаты в таблице MySQL. Поскольку эти местоположения импортируются из внешних источников, я хочу предоставить пользователю представление «объединения», где они могут видеть группы местоположений, которые находятся в пределах X метров друг от друга, и объединять их в одно.

Проблема реализации поиска по близости обсуждалась много, например:

• Самый быстрый способ найти расстояние между двумя точками широты/долготы< /а>
• PHP/ MySQL - найти все предметы в радиусе 500 метров от фактических GPS-координат

Большинство из них используют стандартную формулу гаверсинуса для расчета расстояний:

SELECT 
  -- stuff here
  , ( 6371000 * acos( cos( radians($LAT) ) * cos( radians( stuff.lat ) ) * cos( radians( stuff.lng ) - radians($LNG) ) + sin( radians($LAT) ) * sin(radians(stuff.lat)) ) ) AS distance 
FROM 
  stuff
HAVING 
  distance < $distance

Однако это работает только в том случае, если у меня есть одна точка для поиска, но я хочу найти ВСЕ группы местоположений, которые находятся в пределах X метров друг от друга.

Моим простым решением было бы получить все местоположения в PHP-код, затем перебрать их и использовать приведенный выше запрос, чтобы найти все близлежащие местоположения для каждого местоположения. После этого я очищаю повторяющиеся группы. Но это решение имеет стоимость n², потому что я создаю n запросов, которым нужно вычислить расстояние до всех других местоположений. Вторая часть может быть улучшена с помощью ограничительной рамки, однако мне все еще нужно выполнить n запросов (чтобы получить все близлежащие местоположения для каждого местоположения).

Есть ли более производительный метод? Может быть, даже внутри одного запроса MySQL (чтобы просто вывести идентификаторы местоположений для каждой группы)?

Таблица с местоположениями - это просто «id», «name», «lat» и «lng».