polygons - 将一个有孔的多边形转换为多个没有孔的简单多边形

Question

我正在处理 IfcFace .我得到了一个带孔的简单多边形，我需要将它转换为多个没有孔的简单多边形，以便我的 CAD 进一步处理它。一个小演示说明:



我最好的方法是进行约束德劳内三角剖分并将三角形重新连接成更大的多边形。像这样:

但是由于浮点精度和算法的不稳定性，delaunay 三角剖分甚至约束部分往往会在输入困难时失败。我的输入有时会生成高度为 1e-8 且底长为 1 的三角形。

是否有更好更健壮的算法来实现这种转换？

Answer 1

我认为对形状进行完整的三角剖分是您需要的大量计算。并且三角剖分还给出了位于图形外部的三角形，甚至部分内部和部分外部，因此正确地重新组合它们也很复杂。

提案 1

我想到了一种完全不同的方法。
是否真的需要将图形分成 2 个图形才能在您的 CAD 程序中使用它？如果您可以将其描述为一个循环中的一个图形(形成多边形的一组点)，我希望它也可以。
您需要的是找到连接图形的不同循环并且完全在图形内部的线，以便您可以使用它们来组合循环。

我将首先比较不同循环的成对段并搜索彼此最接近的段。
开始将外循环的所有段与所有内循环的所有段进行比较。
实际上，我将通过将外循环上的点与内循环的段以及内循环上的点与外循环的段进行比较来实现它。如果 x 或 y 距离大于已找到的最小距离，我将通过跳过计算进行优化。
2个线段或彼此最接近的点和线段将为您提供一条线，可用于组合循环(或分割图形):从其中一个(或点)的角开始的线垂直于其他部分。缺点是您正在添加新节点，但它是高效且始终正确的。
一旦找到这样的线，连接的内环和新的线/段可以组合在一个修改后的外环中，其中包括两次新段以关闭新环。您可以通过将修改后的外循环的段与其余其他内循环的段进行比较来重复该过程。
当使用所有内部循环时，您有一个循环描述整个图形。

要将图形完全拆分为 2 个图形，您还需要一个额外的部分。
但我认为我们目前拥有的循环可以在大多数 CAD 软件中用于表示您的图形。它不是标准化的数字，因为它会接触到自身，但 CAD 程序通常不关心这一点。 CAD 程序可以完美地表示图形的表面。

如果您真的想将其完全拆分为 2 个数字，则可以通过搜索 2 个线段或更好地搜索彼此最接近的点和线段来找到您需要的额外线，如果您将比较限制为在所有已添加的段在循环的两个方向上的循环。所有添加的段都在循环中两次，因此新循环中总会有 2 个部分被所有这些部分分开。

评论您对提案 1 的回答

我还没有权利评论你的答案，因为我没有足够的学分，所以我会把评论添加到我自己的答案中。

我正在看你的例子，我首先误解了它，所以我修改了这个评论。

您有 3 个孔，因此算法的第一部分将添加您显示的 3 个段。

而且，是的，您显然对算法的第二部分有问题。您需要第 4 行，但在这种情况下，没有 2 个部分，它们在两个方向上被所有 3 个添加的段分开，否则我不会立即看到它们。
我假设新循环中总会有 2 个部分被所有新段分开。当有 3 个或更多孔时，该假设是错误的。

但我会进一步考虑。

提案2

我现在正在考虑另一种可能的算法。

计算图中每个孔的表面。选择每个孔的一个角。

通过最小的 2 个孔的选定角画一条线。
它可以是任意 2 个孔，但选择最小的孔会增加用更少的线切出更多孔的机会。
如果只剩下一个洞，就在你得到的一点上画一条线。方向无关紧要。我会选择通过选定的点和定义孔的最近的其他点绘制线。

检测绘制的线与图形的线段的所有交叉点，将线减少为完全在图形内部并连接图形的不同环的一组线段。省略在同一循环中开始结束的任何段。
如果一个洞只是在一个点上被找到的线段触及。将线段移动到最靠近该点的同一孔的点，以避免最终得到具有接触外部的孔的图形。
检查与修改后的线段的新交叉点，如果找到，则再次将其拆分。
查找所有交叉点需要将找到的线与图中的所有线段进行比较，这也是大量计算，但您可以通过在计算交叉点之前检查线是否穿过线段周围的边界框来跳过计算。我将首先计算与外循环的交点，以便尽快为线的其余部分提供一个边界框，因为这也有助于检查不需要比较交点的部分。
您还可以通过将每个找到的线段替换为连接所连接线段的最近端点的线段(如果尚未位于 2 个线段的连接点中)来进行优化。这样做可以避免为新图形创建额外的点，并增加一步消除更多漏洞的机会。但是，您需要再次检查新的交叉点并重复此优化，直到找不到更多交叉点为止。
还有一种可能的优化:检查尚未切割的孔中靠近找到的线段的点，并将找到的线段分成 2 段以在同一步骤中也捕捉到该孔。就像之前的优化一样，这也需要再次检查新的交叉点。

使用线段将图形分成 2 个图形，并从步骤 2 开始对每个仍有孔的新图形重复步骤。

缺点是您最终可能会得到 2 个以上的数字(最大 (n + 1)/2 个数字，其中 n 是孔的数量)，但是如果您有许多孔导致许多数字，则可能会重新组合一些他们。