Я занимаюсь разработкой приложения PHP, которое работает с набором местоположений, предоставленных через Локатор, Долгота-Координаты в таблице MySQL. Поскольку эти местоположения импортируются из внешних источников, я хочу предоставить пользователю представление «слияния», где они могут видеть группы местоположений, которые находятся в пределах X метров друг от друга, и объединять их в одно.
Проблема реализации поиска близости было обсуждено много, например:
Большинство из них используют стандартную формулу haversine для расчета расстояний:
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'.