Как лучше сгруппировать объекты на плоскости?

Question

[mystdeim]

Стоит задача сгруппировать объеты на плоскости.
Для примера: из этого:

Нужно получить, что-то похожее на это:

Пока на ум пришла идея -- разбить на гексагоны и перебором пройтись по всем точкам. Но возможны случаи, когда объекты с разной плотностью заполняют всю плоскость и если я буду просто делить на равные промежутки, то получу сетку с жирными точками, расположенных на одинаковом расстоянии друг от друга, выглядит так себе. Подскажите какие есть алгоритмы группировки?

Answer 1

[Сергей Протько]

Я так понимаю что вам нужен алгоритм кластеризации, при условии что вам не известено количество класстеров.

Есть так же вариант реализовать автоопределение количества кластеров для k-means. Мы задаем три рандомных центра класстера, проводим класстеризацию (при этом центры класстеров смещаются), далее мы либо оставляем все как есть, либо делим эти три класстера еще на два. Эти два центра либо будут смещаться и образовывать свои класстера, либо сойдутся в одну точку. Таким образом можно довольно легко вроводить класстеризацию не зная точно количества класстеров.

Правда есть более эффективные алгоритмы для этого.

Answer 2

[Виталий Желтяков]

Вам нужно группировать точки по радиусу взаимодействия. То есть перебираете все точки и если в радиусе взаимодействия есть другая точка, то группируете их. Это простой цикл.

Comments

[mystdeim]

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

[Сергей Протько]

@mystdeim делим на класстера, находим их центры, в зависимости от количества объектов в класстере рисуем жирную точку.

[Виталий Желтяков]

@mystdeim Радиус взаимодействия - это параметр, варьируя который можно изменять отображение картины.

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

[mystdeim]

Понятно, буду пробовать

Answer 3

[Ололёша Ололоев]

Да, именно кластеризация вам и нужна. В вашем случае полезным может быть DBSCAN (если уместно "отметание" шума) или FOREL

Comments

[mystdeim]

FOREL - то что нужно. Подскажите, как быть в такой ситуации: большая группа сформирована у края. Получается так, что уменьшая сферу центр будет в одном и том же месте и алгоритм остановится, найдя только один кластер.

[Ололёша Ололоев]

Я думаю, что многие алгоритмы кластеризации в верхнем левом углу найдут только один кластер

[mystdeim]

Модифицировал немного FOREL, оказалось то что нужно!