visualization - 如何对内部有和没有顶点和孔的多边形进行三角剖分 - 可以进行德劳内三角剖分吗？

Question

我遇到了以下问题：我正在研究一种算法，输出将是一个任意多边形。多边形可以是凹面的，其中有孔，也可以有边角为 180 度的顶点。

我需要对所述多边形进行三角剖分，其中包含和不包含其他顶点。delaunay三角剖分可以处理这个问题，特别是如果我只有多边形而里面没有顶点？我也许可以避免多边形内的孔，如果这可以缓解事情的话。

谢谢阅读

Answer 1

您可以使用约束三角剖分（Delaunay 与否）对多边形进行三角剖分。这里有一个使用 CGAL 的例子。

Answer 2

您可能会查看这些 Fade2D 示例：

https://www.geom.at/example4-zones-defined-areas-in-triangulations/

https://www.geom.at/boolean-operations-on-polygons-with-holes/

学生证是免费的。

Answer 3

您可以使用三角形。

通过命令行运行 Triangle，您将创建一个 ASCII .poly 文件，该文件指定输入（即您的多边形）的顶点和边以及域中的任何孔。每个孔都由其 xyz 位置定义。例如，如果我有一个正方形域，里面有一个三角形孔，我的输入可能如下所示：

7 2 0 0  # 7 vertices
1 1 -1
2 1 1
3 -1 1
4 -1 -1
5 -.5 -.5
6 .5 -.5
7 0 .5
7 0      # 7 segments: four for the square and three for the hole
1 1 2
2 2 3
3 3 4
4 4 1
5 5 6
6 6 7
7 7 5
1      # 1 hole
1 0.0 0.0

如果要细化网格（即在内部添加顶点），可以使用 -a 选项（限制三角形的最大面积）或 -q 选项（控制生成的三角形的质量但不直接限制尺寸）。关于命令行开关的文档在这里。