Эффективный алгоритм расчета площадей на географической карте с наибольшей плотностью пятен

Question

Допустим, у меня есть географическая карта, где точки представлены широтой \ долготой.У меня есть несколько точек на этой карте, и точки могут быть добавлены \ удалены \ перемещены в любое время.

Что мне нужно, так это получить "самые горячие точки" - области, которые содержат наибольшее количествоточки, разделенные на площади - или, другими словами, области с наибольшей плотностью точек.

Мне нужна эффективная структура данных, а также алгоритм, который пересчитывает самые горячие точки при любом изменении.Вычислительная сложность и сложность памяти должны быть минимальными, поскольку число точек может быть очень большим.

Я хочу знать и вести список самых горячих точек в порядке убывания - сначала самая людная область, затемменее людные районы.Можно иметь список ограниченного размера - например, 100 самых горячих точек.

Конечно, для предотвращения 100% плотности в одной изолированной точке, существует минимальная область (определяемая как константа).

Определение «область» здесь - это любая воспринимаемая область на карте, которая содержит точки.Это может быть целая карта, но алгоритм, конечно, не должен воспринимать это как горячую точку =)

Спасибо, вперед!Если это нужно уточнить, пожалуйста, скажите ...

Answer 1

То, что вы делаете, статистически известно как «двумерная оценка плотности» (поэтому вы знаете, где искать).

Одним из распространенных методов является «сглаживание ядра». Представьте себе диск на каждой из ваших точек данных. Сглаживание ядра по области - это количество дисков, перекрывающихся в каждой точке. Это сглаживание ядра с использованием равномерного ядра фиксированного радиуса.

Вам не нужно использовать единообразные ядра и они не должны быть одинакового размера во всех точках - теперь это «адаптивное сглаживание пропускной способности ядра».

Это дает вам сетку, которую вы можете довольно легко обновить, особенно если у вас конечное ядро ​​(вы можете использовать гауссово (нормальное) ядро, которое бесконечно, но будет вырезано в вашей области обучения). Каждый раз, когда вы добавляете или убираете точку, вы добавляете или убираете вклад ее ядра в плотность.

Так что это половина проблемы - теперь у вас есть сетка плотностей. Затем вы можете использовать алгоритмы кластеризации, чтобы разделить его и найти отдельные пики в соответствии с любыми критериями а) определяет «пик» и б) определяет его отдельно от соседнего пика. Кто-то уже предложил алгоритмы кластеризации. Я сделал это (десять лет назад), используя функции кластеризации в «R», статистическом пакете. Скорость не является ее сильной стороной, хотя ...

Возможно, вы захотите перенести это на http://stats.stackexchange.com

Answer 2

Это слишком долго для комментария, но вот только идея о том, как я "поиграю" с этим и посмотрим, смогу ли я придумать что-нибудь интересное.Но одно можно сказать наверняка: можно сделать следующее: очень быстро.

Может ли это быть легко переведено на какую-то дискретную проблему?Сначала вы «выровняете» все свои координаты по большой карте (вы определяете, насколько велик каждый квадрат, и вы делаете каждую карту входа в одну такую ​​точку).Затем вы получите что-то вроде этого:

0000000000000000000000000000
00XX000000000000000000X00000
00X00000000000000X0000000000
0000000000000000000000000000
0000000000000000000000000000
000000X00000000X000000000000
0000000000000000000000000000
000000000000X000000000X00000
00000000000000000000000X0000
0000000000000000000000000000

Затем вы вычислите каждую запись и количество соседних соседей:

0000000000000000000000000000
0033000000000000000001000000
0030000000000000010000000000
0000000000000000000000000000
0000000000000000000000000000
0000001000001001000000000000
0000000000000000000000000000
0000000000001010000000200000
0000000000000000000000020000
0000000000000100000000000000

Затем вы можете увеличить размерваш квадрат, скажем, два, и, следовательно, разделите вашу карту:

(карта не верна, просто дать представление о том, о чем я думаю)

09001001000000
00000000000000
00100001100000
00000110002000
00000002000000
00000100000000

Затем вы пересчитываете соседних соседей и т. Д.

Для меня это позволило бы найти точку доступа в зависимости от вашего «разрешения»: вы просто искали бы самые большие числа, и это были бы ваши «точки доступа».

Потому что в этом случае:

0000X00000
0000XX0000
0000000000
0000000000
0Y0Y000000
0000000000
0Y0Y000000

Либо «X» может быть самой горячей точкой (три интересные точки расположены близко друг к другу), либо «Y» (четыре точки расположены близко друг к другу,но они не так близки, как для «X»).

Поскольку вы сказали, что вам нужна скорость, я бы просто превратил это в дискретную проблему и представлял свои графики как массивы.Затем я бы учел переменный размер "области".

Выглядит как забавная задача для работы:)

Answer 3

Тип используемого алгоритма будет зависеть от распределения точек.Вы вполне можете столкнуться с гораздо более сложной проблемой разделения групп на «области».Поскольку вам, кажется, что-то нужно для начала, я рекомендую вам прочитать Выпуклые оболочки и , вычисляющие площадь двухмерного многоугольника и , как определить, является ли точканаходится в многоугольнике .