Алгоритм быстрой группировки объектов (по местоположению)

Question

Я имею дело с большой группой лиц, которые хранят локации. Они отображаются на карте. Я пытаюсь найти эффективный способ сгруппировать близлежащие объекты в одну сущность, если смотреть из более высокого местоположения. Так, например, если вы очень высоко, при взгляде вниз вы увидите одну сущность, которая представляет группу близко расположенных сущностей в области. При достаточно близком увеличении эта сущность будет разделена на содержащиеся в ней сущности.

Есть ли эффективный алгоритм для этого? Я думал о том, чтобы просто сместить вид на основе высоты и поместить объекты в поля сетки на основе местоположения, а затем отрисовать точку блока. Меня беспокоит только то, что если все сущности находятся в верхнем правом углу этого поля, то сущность, отображаемая для их представления, может быть отцентрирована по центру вместо расположения группы сущностей.

Есть мысли или идеи?

Answer 1

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

http://arxiv.org/abs/math?papernum=0502342

http://flashorbit.com/?page_id=40

"Боиды", кажется, находятся в одном районе, когда вычисляют стада. http://www.red3d.com/cwr/boids/

Answer 2

Я считаю, что вы ищете "алгоритм кластеризации". Есть множество доступных. Хорошим началом может быть Алгоритм K-средних . В конечном счете, звучит так, будто вам нужен какой-то алгоритм иерархической кластеризации.

Answer 3

Если у вас будет предварительное назначение объектов в группы объектов или все объекты в определенном «поле зрения» автоматически попадают в «группу», то вы можете назначить «местоположение» для группы объектов, используя Алгоритм "центра масс", по сути, широта - это просто среднее значение всех содержащихся широт, и то же самое для долгот ... Сложите их и разделите на количество для обоих измерений ...

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