Генерация полигона по набору хаотичных точек

[rolan]

Приветствую. Есть задачка, а на ум решений особо не приходит. Существует неким образом отфильтрованный набор устройств. В устройствах соответственно хранится их положение и прочие параметры. Необходимо нарисовать подложки для групп устройств по определенному параметру. Т.е. грубо говоря на карте 200 устройств, и они логически сгруппированы на 7 областей, вот эти области требуется выделить сглаженной кляксой. Выделение может строиться по различным параметрам (но они схожи и в принципе всегда подходящие устройства находятся рядом - т.е. нет пересечений этих клякс, хотя это и не проблема). Т.е. заведомо наделить некий абстрактный объект геометрией не вариант - создавать полигон надо на лету. Кто может какие алгоритмы подсказать?
Да, забыл указать - область должна быть несколько шире входящих устройств.

[gamm]

Кто может какие алгоритмы подсказать?

диаграмма Вороного, пересеченная с буфером. Для тонких ценителей - еще и слияние объектов по типу. Для чисто картинки - снести на растр, сделать дистанционное преобразование, и отрисовать изолинии.

[rolan]

Кто может какие алгоритмы подсказать?

диаграмма Вороного, пересеченная с буфером. Для тонких ценителей - еще и слияние объектов по типу. Для чисто картинки - снести на растр, сделать дистанционное преобразование, и отрисовать изолинии.

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

[doujin]

Построить для каждой группы выпуклую оболочку (convex hull), и построить буфер на некоторое расстояние уже от нее. Будет гладко и "несколько шире" входящих точек. По сложности примерно то же самое, что и в предложении gamm. Но это лишь в случае, если вам подходят именно выпуклые "кляксы".

[gamm]

Но тема не закрыта, буду рад услышать еще варианты

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

[gamm]

Построить для каждой группы выпуклую оболочку (convex hull), и построить буфер на некоторое расстояние уже от нее. Будет гладко и "несколько шире" входящих точек. По сложности примерно то же самое, что и в предложении gamm. Но это лишь в случае, если вам подходят именно выпуклые "кляксы".

придется делать еще и буфер - товарищъ хочет, чтобы область была несколько больше. Кроме выпуклости получим пересечения ...

[rolan]

В целом победил.

С помощью алгоритма Грэхема получаю выпуклую оболочку, далее (на скриншоте нет) - от центра геометрии к вершинам - делаю отступы. А вот как теперь все это сгладить.. Пробовал кривую Безье - она отбрасывает часть точек, пришлось делать большИй отступ, чтоб проглотила все точки, но клякса настолько разрослась, что перекрытие с соседними более 50% площади. Нагуглил только интерполяцию сплайнами, и в частности заинтересовал сплайн Акима, пару часов с ним убил, пока тщетно - все примеры с графиками, а не обводка фигуры (ну с этим разберусь, считай только начал). Пишу в надежде, что кто-нибудь с подобным пересекался и посоветует как сгладить обводку.

[KolesovDmitry]

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