从 vtk 中的点创建复杂的凹多边形曲面

Question

我正在做一个项目，我需要从用户定义的点生成表面以创建多边形。对于凸多边形，我可以毫无问题地使用 Delaunay2D 三角剖分方法生成曲面。但是，当我尝试为凹多边形生成曲面时，我遇到了一些问题。

例如，当我在凹多边形上定义点（如下图所示）并使用 Delaunay2D 生成曲面时，我得到的填充曲面不能准确表示多边形：

我尝试过很多其他的曲面生成方法，但一直没能找到正确的凹多边形曲面生成方法

谁能建议一种从用户定义的点为凹多边形生成曲面的方法？任何帮助将不胜感激。提前谢谢你！

Answer 1

您似乎想要一组点的“凹包”。问题是对于这将是什么没有一个自然的定义。虽然有一个明确定义的一组点的凸包，但有许多凹包。选择其中一个合适的取决于你在做什么。

例如在 GIS stackexchange 上看到这个问题。

尽管如此，我发现 Duckham 等人在“高效生成简单多边形以表征平面中一组点的形状”中描述的算法。阿尔。产生在实践中有用的凹包。该算法基本上是从点的 Delaunay 三角剖分开始，然后从三角剖分中删除外部边缘，直到没有可以删除的边长于 x，其中 x 是您选择的输入参数根据你的用例。上面链接中的论文描述了如何有效地做到这一点。

Python 实现在这里。