computational-geometry - 构建多边形的约束 alpha 形状

Question

我有一个非常具体的任务。
我需要计算一组点的alpha 形状。（你可以在那里玩已经实现的算法）

关键是我已经预定义了点的子集（我们称它们为细节），我不希望它们的结构被改变。例如，假设这些多边形是细节：

然后，根据 alpha 半径，以下船体是可以的：

以下不是：

简而言之，我希望指定点子集的结构在减小半径期间保持不变。

那么，你怎么看：

1. 我可以使用任何已经实现的算法还是应该找出一些特定的算法？
2. 在任何地方都有开源代码的 Alpha-Shape 算法的实现示例吗？（Alpha-Shape，不是Concave hull。减小半径时必须将轮廓分成几部分）

Answer 1

好吧，最后我使用约束 Delaunay 三角剖分解决了这个问题。

这个想法（Yves Daoust在对该问题的评论中分享）不仅是在构建 Alpha 形状期间使用 Delaunay 三角剖分，而且是受约束的Delaunay 三角剖分。

算法：简而言之，我：

1. 采用提升多边形的凸包
2. 计算其约束三角剖分。（约束线段是多边形的边）

在这一步中，我使用了 C# 的Triangle .NET库。我想，每一种流行的语言都有它的替代品。

3. 内置 alpha 形状：丢弃所有边长于预定义alpha的三角形

我的奋斗结果：

1. Alpha = 1000，alpha 形状只是一个凸包

2. 阿尔法 = 400

3. Alpha = 30。只有非常小的凹面会被平滑

如果您愿意，请随时给我写信以获得更深入的解释。