c# - 计算三角多边形网格中的孔

Question

我正在 WPF 中开发可视化工具，它具有通过 3-D 形状显示切割平面的功能。例如，像这样的 3-d 几何体:

... 是用平面切割的。切割后，该算法识别沿切割平面的所有独特轮廓，并以 CW 或 CCW 缠绕顺序填充线段列表。任何简单的多边形都可以使用 Cutting Ears 算法轻松进行三角剖分和渲染，如下所示:

给定右侧三角剖分的输入，以及左侧平面上可见的内部折线，是否有一种算法可以重新配置三角剖分以构造由折线勾勒出的孔？

如果已经在 C# 或其他 CLR 语言中推出了算法，我很乐意了解它们。我正在使用 WPF 要求的 Point3D 列表来描述 MeshGeometry3D 三角形网格，但如果需要，我显然可以填充任何数据结构，或者通过研究其他语言代码或伪代码来旋转我自己的类。

编辑:查看已接受的答案；我正在使用 Poly2Tri 的 C# 实现, 一个受约束的 Delaunay 三角剖分。然而，(图像不按比例)Poly2Tri 算法(中心)失败了 780 段折线，而 Cutting Ears(右)没有，直到我剥离它们的精度输入，提供单精度值向上转换为 double 而不是 double .它现在产生与 Cutting Ears 不同的三角剖分，但尊重外部多段线的边界。

Answer 1

以边界线段为约束计算受约束的 Delaunay 三角剖分。确定一个内三角。从那里扩大区域，直到到达边界。作为一个积极的副作用，这样的三角剖分会有更好的三角形形状。