Построить ограниченную альфа-форму многоугольников

Question

У меня довольно специфическая задача.
Мне нужно вычислить альфа-форму набора точек.(Вы можете резвиться с уже реализованным алгоритмом там )

Дело в том, что у меня есть предопределенные подмножества точек (давайте назовем их детали), и я не хочу, чтобы их структура изменялась.Например, предположим, что эти многоугольники являются деталями:

Тогда, в зависимости от альфа-радиуса, в порядке следующие корпуса:

И следующее:

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

Итак, как вы думаете:

1. МайЯ использую какой-либо из уже реализованных алгоритмов, или я должен выяснить какой-то конкретный?
2. Есть ли где-нибудь реализованный пример алгоритма Alpha-Shape с открытым исходным кодом?(Альфа-форма, а не вогнутый корпус. При уменьшении радиуса контур должен разделяться на несколько частей)

Answer 1

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

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

Алгоритм: Вкратце, я:

1. Взял выпуклый корпус из продвинутых полигонов
2. Вычислили его ограниченную триангуляцию. (Ограничивающие сегменты - это ребра многоугольника)

На этом шаге я использовал библиотеку Triangle .NET для C #. Я думаю, у каждого популярного языка есть альтернативы этому.

3. Встроенная альфа-форма: отбрасывает все треугольники, где любое ребро длиннее, чем предопределено альфа

Результаты моей борьбы:

1. Альфа = 1000, альфа-форма - просто выпуклая оболочка

2. Альфа = 400

3. Альфа = 30. Сглаживаются только очень маленькие вогнутости

Не стесняйтесь, пишите мне для более глубокого объяснения, если хотите.