我正在处理IfcFace http://www.buildingsmart-tech.org/ifc/IFC4/Add2/html/schema/ifctopologyresource/lexical/ifcface.htm。我得到了一个带孔的简单多边形，我需要将其转换为多个不带孔的简单多边形，以便 CAD 进一步处理它。一个小演示图：
My best approach is to do a constrained delaunay triangulation and rejoin the triangles into bigger polygons. Like so:
But the delaunay triangulation and even more the constraining part tends to fail for difficult input because of floating point precision and algorithmic instabilities. My input sometimes generates triangles with height 1e-8 and base length 1.
是否有更好更稳健的算法来实现这种转换？
我认为形状的完整三角测量需要进行大量计算才能满足您的需求。而且三角剖分还给出了位于图形外部的三角形，甚至部分位于内部、部分位于外部的三角形，因此正确地重新组合它们也很复杂。
提案1
我想到了一种完全不同的方法。
是否真的需要将图形分成 2 个图形才能在 CAD 程序中使用？我希望如果您可以将其描述为一个循环中的一个图形（形成多边形的点列表），也可以。
您需要的是找到连接图形的不同循环并且完全位于图形内部的线，以便您可以使用它们来组合循环。
我将首先比较不同循环的成对段并搜索彼此最接近的段。
开始将外循环的所有段与所有内循环的所有段进行比较。
实际上，我将通过比较外循环上的点与内循环的段以及内循环上的点与外循环的段来实现它。如果 x 或 y 距离大于已找到的最小距离，我将通过跳过计算进行优化。
两条线段或彼此最接近的点和线段将为您提供一条线，可用于组合循环（或分割图形）：从其中一个线段（或点）的角开始的线垂直于其他部分。缺点是您要添加新节点，但它很高效并且始终正确。
一旦找到这样的线，所连接的内循环和新线/段就可以合并到一个修改后的外循环中，其中包含新段两次以关闭新循环。您可以通过将修改后的外循环的段与其余其他内循环的段进行比较来重复该过程。
当使用所有内部循环时，您将拥有一个描述整个图形的循环。
要将图形完全分成 2 个图形，您将需要多一个额外的部分。
但我认为我们目前拥有的循环可以在大多数 CAD 软件中使用来表示您的图形。它不是标准化图形，因为它会触及自身，但 CAD 程序通常不关心这一点。它非常适合 CAD 程序来表示图形的表面。
如果您确实想将其完全分成 2 个数字，则可以通过搜索 2 个线段找到您需要的额外线，或者如果您将比较限制为分开的线段和点对，则可以更好地找到彼此最接近的点和线段。由循环的两个方向上所有已添加的段组成的循环。所有添加的段在循环中都会出现两次，因此新循环中始终会有 2 个部分被所有部分分隔开。
评论您对提案 1 的回答
我还没有权利评论你的答案，因为我没有足够的学分，所以我会将评论添加到我自己的答案中。
我正在看你的例子，我首先误解了它，所以我改编了这个评论。
您有 3 个洞，因此算法的第一部分将添加您显示的 3 个部分。
是的，您显然对算法的第二部分有一个问题案例。您需要第四条线，但在这种情况下，没有 2 个部分，它们被两个方向上所有 3 个添加的线段分隔开，否则我不会立即看到它们。
我假设新循环中始终有 2 个部分被所有新段分隔开。当有 3 个或更多孔时，该假设是错误的。
但我会进一步考虑。
建议2
我现在正在考虑另一种可能的算法。
计算图中每个孔的表面积。选取每个孔的一个角。
通过最小 2 个孔的选定角画一条线。
可以是任意 2 个孔，但采用最小的孔可以增加用更少的线切割更多孔的机会。
如果只剩下一个洞，只需在已有的一个点上画一条线即可。方向并不重要。我会选择通过所选点和定义孔的最近的其他点绘制线。
检测所绘制的线与图形的线段的所有交点，以将线减少为完全位于图形内部并连接图形的不同环的一组线段。省略在同一循环上开始结束的任何段。
如果找到的线段仅在一个点接触到一个孔。将其中一个线段移动到同一个孔中最接近该点的点，以避免最终形成一个具有接触外部的孔的图形。
检查与修改后的路段是否有新的交叉点，如果发现则再次将其分割。
查找所有交点需要将找到的线与图形的所有线段进行比较，这也需要大量计算，但您可以通过在计算交点之前检查线是否穿过线段周围的边界框来跳过计算。我将首先计算与外循环的交点，以便尽快为线的剩余部分提供边界框，因为这也可以帮助检查不需要比较交点的部分。
您还可以通过将每个找到的线段替换为连接所连接线段的最近端点的线段（如果尚未位于 2 个线段的连接点中）来进行优化。这样做可以避免为新人物创建额外的点，并增加一步消除更多洞的机会。但随后您需要再次检查新的交叉点并重复此优化，直到找不到更多交叉点。
还有一种可能的优化：检查尚未切割的孔中靠近找到的线段的点，并将找到的线段分成两段，以便在同一步骤中捕获该孔。就像之前的优化一样，这也需要再次检查新的交叉点。
使用线段将图形分成 2 个图形，并对每个仍然有孔的新图形重复步骤 2。
缺点是您最终可能会得到超过 2 个数字（最大 (n +1)/2 个数字，其中 n 是孔的数量），但如果您有很多孔导致许多数字，则可能会重新组合一些数字他们。
