Контур 2-х точечных облаков

Question

Я рассеял облака точек в 2d.Моя проблема в том, что я хотел бы получить точку границы, чтобы получить контур облаков точек.

Я знаю об этом «марширующем квадрате», однако этот алгоритм обычно используется для пикселей в 2dУ кого-нибудь есть идеи, как получить контур из двумерных облаков точек или детали алгоритма «Марширующий квадрат»?Кроме того, выпуклый корпус не работает в моем случае.

Заранее спасибо.

Answer 1

Я думаю, что алгоритм 2D "Альфа-формы" будет правильным выбором для вас.

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Alpha_shapes_2/Chapter_main.html

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

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

Вы можете попробовать Java-апплет здесь: http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html

чтобы лучше понять, как работает этот алгоритм.

Answer 2

Я бы предложил использовать Триангуляцию Делоне в качестве базового алгоритма, затем удалить все слишком большие треугольники (таким образом, разделяя облака на группы), а затем удалить все ребра, используемые более чем одним треугольником.