Как сгруппировать «близкие» друг к другу точки широты и долготы?

Существует несколько способов определения расстояния между двумя точками, но для построения точек на двухмерном графике вам, вероятно, понадобится Евклидово расстояние. Если (x1, y1) представляет вашу первую точку, а (x2, y2) - вторую, расстояние равно

d = sqrt( (x2-x1)^2 + (y2-y1)^2 )

Что касается группировки, вы можете использовать какое-то двумерное средство, чтобы определить, насколько «близки» объекты друг к другу. Например, если у вас есть три точки, (x1, y1), (x2, y2), (x3, y3), вы можете найти центр этих трех точек простым усреднением:

x(mean) = (x1+x2+x3)/3
y(mean) = (y1+y2+y3)/3

Затем вы можете увидеть, насколько близко каждый из них находится к центру, чтобы определить, должен ли он быть частью «кластера».

Существует несколько способов определения кластеров, каждый из которых использует какой-либо вариант кластеризации алгоритм. Я сейчас в спешке, и у меня нет времени подводить итоги, но просмотрите ссылку и алгоритмы, и, надеюсь, другие люди смогут предоставить более подробную информацию. Удачи!

Используйте что-то похожее на метод, который вы описали в своем вопросе, чтобы получить приблизительный набор результатов, а затем сведите его к минимуму, выполнив правильные вычисления. Если вы правильно выберете размер сетки (то есть, насколько вы округляете свои координаты), вы можете, по крайней мере, надеяться уменьшить объем работы, которую необходимо выполнить, до приемлемого уровня, хотя вам придется управлять этим размером сетки.

Например, расширение earthdistance для PostgreSQL работает путем преобразования пар широта / долгота в декартовы координаты (x, y, z), моделируя Землю как однородную сферу. PostgreSQL имеет сложную систему индексирования, которая позволяет индексировать эти координаты или прямоугольники вокруг них в R-деревьях, но вы можете скомпоновать что-то, что по-прежнему полезно и без этого.

Если вы возьмете свой (x, y, z) тройной и округлите, то есть умножьте на некоторый коэффициент и усеките до целого числа - тогда у вас будет три целых числа, которые вы можете объединить, чтобы получить "имя поля", которое идентифицирует поле в вашем " сетка ", в которой находится точка.

Если вы хотите найти все точки в пределах X км от некоторой целевой точки, вы генерируете все «имена ящиков» вокруг этой точки (после того, как вы также преобразовали вашу целевую точку в тройку (x, y, z), это легко) и удалите все прямоугольники, которые не пересекают поверхность Земли (хитрость, но использование формулы x^2+y^2+z^2=R^2 в каждом углу скажет вам), вы получите список прямоугольников, в которые могут быть включены целевые точки - так что просто ищите все баллы, соответствующие одному из этих квадратов, что также вернет вам дополнительные баллы. Итак, на заключительном этапе вам нужно рассчитать фактическое расстояние до целевой точки и устранить некоторые (опять же, это можно ускорить, работая в декартовых координатах и ​​преобразовав радиус целевого расстояния по большому кругу в секущее расстояние).

Возникновение сводится к тому, чтобы вам не пришлось искать слишком много ящиков, но в то же время не набирать слишком много дополнительных очков. Я счел полезным индексировать каждую точку на нескольких разных сетках (например, с разрешением 1 км, 5 км, 25 км, 125 км и т. Д.). В идеале вы хотите искать только одно поле, помните, что оно расширяется как минимум до 27, как только ваш целевой радиус превышает размер вашей сетки.

Я использовал этот метод для построения пространственного индекса с помощью Lucene, а не для вычислений в базах данных SQL. Он действительно работает, хотя для его настройки нужно немного возиться, а для генерации индексов требуется время, и они довольно большие. Использование R-дерева для хранения всех координат - гораздо более приятный подход, но для этого потребуется больше настраиваемого кодирования - этот метод в основном просто требует быстрого поиска по хеш-таблице (поэтому, вероятно, он будет хорошо работать со всеми базами данных NoSQL, которые являются ярости в наши дни, и ее также следует использовать в базе данных SQL).

Может быть, перебор, но мне это кажется проблемой кластеризации: distance measure определит, как рассчитывается схожесть двух элементов. Если вам нужно менее простое решение, попробуйте Data Mining: практические инструменты машинного обучения и Методы и используйте Weka или Оранжевый

Если бы я брался за это, я бы начал с сетки. Поместите каждую точку в квадрат на сетке. Ищите густонаселенные сетки. Если соседние сетки не заселены, значит, у вас приличная группа.

Если у вас есть соседние густонаселенные сетки, вы всегда можете поместить круг в центре каждой сетки и оптимизировать для площади круга vs (количество точек в круге * некоторый настраиваемый вес). Не идеально, но легко. Лучшее группирование - это гораздо более сложные проблемы оптимизации.

Если вы учитываете широту и долготу, в данных в реальном времени следует учитывать несколько факторов: препятствия, такие как реки и озера, и объекты, такие как мосты и туннели. Вы не можете просто сгруппировать их; если вы используете простой алгоритм, поскольку k означает, что вы не сможете их сгруппировать. Я думаю, вам следует использовать методы пространственной кластеризации, такие как метод разделения CLARANS.