Группировать координаты по близости друг к другу

Question

Группировать координаты по близости друг к другу

Я создаю REST API, поэтому ответ не может включать в себя карты Google или JavaScript.
В нашем приложении есть таблица с сообщениями, которая выглядит следующим образом:

  ID |   latitude   | longitude   | other_sutff
1 | 50.4371243   |  5.9681102  |    ...
2 | 50.3305477   |  6.9420498  |    ...
3 | -33.4510148  | 149.5519662 |    ...

У нас есть вид с картой, которая показывает все сообщения по всему миру.
Надеюсь, у нас будет много постов, и было бы смешно показывать тысячи и тысячи маркеров на карте. Поэтому мы хотим сгруппировать их по близости, чтобы у нас было что-то вроде 2-3 маркеров по континентам.

Чтобы было понятно, нам нужно это:

Изображение из https://github.com/googlemaps/js-marker-clusterer

Я провел некоторое исследование и обнаружил, что k-means, кажется, является частью решения.
Поскольку я очень плохо разбираюсь в математике, я попробовал пару библиотек php, как эта: https://github.com/bdelespierre/php-kmeans это, кажется, делает приличную работу.
Однако есть недостаток: мне приходится анализировать всю таблицу каждый раз при загрузке карты. По производительности это ужасно.

Поэтому я хотел бы знать, справился ли кто-то с этой проблемой или есть лучшее решение.

4

coordinates group-by mysql php

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Я продолжал искать и нашел альтернативу KMeans: GEOHASH

Википедия лучше меня объяснит, что это такое: Вики геохаш

Подводя итог, можно сказать, что карта мира разделена на сетку из 32 ячеек, и каждой из них присваивается буквенно-цифровой символ.
Каждая ячейка также разделена на 32 ячейки и так далее на 12 уровней.
Так что если я сделаю GROUP BY по первой букве хэша я получу кластеры для самого низкого уровня масштабирования, если я хочу большей точности, мне просто нужно сгруппировать по первым N буквам моего хэша.

Итак, я только добавил одно поле в мою таблицу и сгенерировал хеш, соответствующий моим координатам:

ID |   latitude   | longitude   | geohash      | other_sutff
1 | 50.4371243   |  5.9681102  | csyqm73ymkh2 |     ...
2 | 50.3305477   |  6.9420498  | p24k1mmh98eu |     ...
3 | -33.4510148  | 149.5519662 | 8x2s9674nd57 |     ...

Теперь, если я хочу получить свои кластеры, я просто должен сделать простой запрос:

SELECT count(*) as nb_markers FROM mtable GROUP BY SUBSTRING(geohash,1,2);

В подстроке 2 — это уровень точности, который должен быть от 1 до 12

PS: Lib я использовал для генерации хэша

4