c# - 为什么 Triangle.Net 没有按预期对这些多边形进行三角剖分？

Question

我一直在使用 Triangle.Net 对某些带孔的多边形进行三角剖分时遇到问题。

问题似乎是在某些情况下，我使用轮廓定义孔并将孔设置为“真”(在首先添加外轮廓后，孔设置为假)。 Polygon.Add(contour, true);
Triangle.Net 然后通过 Point.FindInteriorPoint 在那个洞里找到一个点出于我不知道的原因，有时它会发现一个点位于那个洞的最边缘，结果是唯一被三角化的是洞，多边形的其余部分被忽略。

所以例如。具有相同外轮廓的两个多边形:
(3.5, 3.5), (-2.5, 3.5), (-2.5 -0.5), (-4.5, -0.5), (-4.5, -2.5), (3.5, -2.5) Image1

但是有一个洞定义为这个轮廓:

(2.5, 2.5), (2.5, 0.5), (0.5, 2.5)

和孔设置为true。发现这个洞的内点是 (1.5, 2.5)就在边界上。结果是外部多边形没有被三角化，但洞是。 Result

另一个有一个孔定义为这个轮廓:

(0.5, 2.5), (2.5, 2.5), (2.5, 0.5)

和孔设置为true。发现这个洞的内点是 (2, 2)这是很好的中间。结果是正确地对外部多边形进行三角剖分，并正确切出孔。 Result

它们似乎具有相同的轮廓方向，所以我不知道为什么一个可以正常工作，而另一个却没有。如果我提供第一个多边形在多边形内的点为 (2, 2)而不是仅仅将孔设置为“真”，那么多边形都被正确地三角剖分。所以我相当肯定这个问题似乎归结为在孔轮廓内找到它自己的点。

但是，如果我使用更简单的外部多边形，则更令人困惑，例如:
(3.5, 3.5), (-2.5, 3.5), (-2.5, -2.5), (3.5, -2.5) Image2

然后我可以像在第一个版本中一样定义一个洞，即使发现内点是 (1.5, 2.5) 也一切正常。 .所以现在我认为边缘点不是问题。

我现在有点失落。我真的不知道我做错了什么，也不知道去哪里找。任何建议，将不胜感激。谢谢。

Answer 1

这里发生了两种不同的事情，加在一起，这使行为变得困惑。

第一个问题是 FindInteriorPoint 的行为。这种方法有一些鲁棒性问题，可以找到轮廓边界上的点。我怀疑你没有使用 this fork包含 some robustness improvements 的 Triangle.NET这应该会产生良好的结果，尤其是在这些简单的情况下。

现在，如果您确实使用孔边界上的点指定了一个孔，我们期望会发生什么？答案是结果是随机的/不可预测的。三角形在包含标识为孔的点的最终网格中定位三角形，并删除它所连接的所有三角形，而不与任何受约束的线段交叉。哪一边(使用精确算术)取决于网格中子段端点的精确坐标，对于细化网格，这取决于计算插入的额外顶点时发生的舍入。您的案例没有任何改进，因此该位置确实正好在该段上。三角形从起点向孔位置走，直到找到包含孔点的三角形:起点的任意位置决定了它首先到达哪一侧并最终选择。因此，如果您有不同的周围域，您将获得不同的(任意)起点，并且可以获得不同的结果。