将带孔的多边形转换为多个无孔的简单多边形 [英] Converting a polygon with holes into multiple simple polygons without holes
问题描述
我正在处理 IfcFace .我给了一个带有孔的简单多边形，我需要将其转换为多个没有孔的简单多边形，以供我的CAD进一步处理.一点演示ilustration:
I am dealing with IfcFace. I'm given a simple polygon with holes and I need to convert it into multiple simple polygons without holes for my CAD to further process it. A little demo ilustration:
我最好的方法是进行约束Delaunay三角剖分，然后将三角形重新合并为更大的多边形.像这样: 但是，由于浮点精度和算法的不稳定性，delaunay三角剖分以及更多的约束部分会因输入困难而失败.我的输入有时会生成高度为1e-8且底长为1的三角形.
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.
是否有更好的更健壮的算法来实现这种转换?
Are there better more robust algorithms to achieve this conversion?
推荐答案
我认为对形状进行完全三角剖分需要大量计算.而且三角剖分还使三角形位于图形的外部，甚至部分位于内部，部分位于外部，因此正确地重新组合它们也很复杂.
I think complete triangulation of the shape is a lot of calculation for what you need. And the triangulation also gives triangles lying outside the figure and even partially inside and partially outside so recombining them correctly is also complicated.
建议1
我想到了一种完全不同的方法.
是否真的需要将图形分为2个数字才能在您的CAD程序中使用它?如果可以将其描述为一个循环中的一个数字(形成多边形的点列表)，我希望它也可以.
您需要找到连接图的不同回路且完全在图中内部的线，以便您可以使用它们来组合回路.
I thought about an entirely different approach.
Is it really required to split the figure in 2 figures to use it in your CAD program? I expect it's also OK if you can describe it as one figure in one loop (one list of points forming a polygon).
What you need is to find lines which connect the different loops of the figure and which are completely inside the figure, so that you can use them to combine the loops.
我将从比较不同循环的段对开始并搜索彼此最接近的段开始.
开始将外循环的所有段与所有内循环的所有段进行比较.
实际上，我将通过比较外循环上的点与内循环的段以及内循环上的点与外循环的段来实现它.如果x或y距离大于已经找到的最小距离，我将跳过计算来进行优化.
2个线段或最接近的点和线段将为您提供一条线，可用于组合循环(或分割图):线从其中一个(或点)的一个角垂直于其他部分.缺点是您要添加新节点，但是它高效且始终正确.
一旦找到这样的线路，就可以将连接的内部回路和新线路/段合并到一个修改的外部回路中，该外部回路包括两次新段，以关闭新回路.您可以通过将修改后的外部循环的段与其余的其他内部循环进行比较来重复该过程.
使用所有内部循环时，您只有一个循环描述了整个图形.
I would start by comparing pairs of segments of the different loops and search for segments which are closest to each other.
Start comparing all segments of the outer loop with all segments of all of the inner loops.
Practically, I would implement it by comparing points on the outer loop with segments of the inner loops and points on the inner loop with segments of the outer loop. And I would optimize by skipping calculations if x or y distance is bigger than the smallest distance already found.
The 2 segments or the point and segment closest to each other will deliver you a line that can be used to combine the loops (or to split the figure): the line from a corner of one of them (or the point) perpendicular on the other segment. The drawback is that you are adding new nodes, but it is efficient and always correct.
Once you found such line, the inner loop which is connected and the new line/segment can be combined in one modified outer loop, which includes the new segment twice to close the new loop. You can repeat the procedure by comparing the segments of that modified outer loop with the remaining other inner loops.
When all inner loops are used you have one loop describing the entire figure.
要将图形完全分割成2个图形，您需要再增加一个细分.
但是，我认为目前大多数计算机辅助设计软件都可以使用该循环来表示您的身材.这不是一个标准化的数字，因为它触动了自己，但CAD程序通常并不在乎这一点. CAD程序可以很好地表示图形的表面.
To split the figure entirely into 2 figures, you would need one more extra segment.
But I think the loop that we have at this point can be used in most CAD software to represent your figure. It's not a normalized figure because it touches itself but CAD programs usually don't care about that. It is perfectly usable for a CAD program to represent the surface of the figure.
如果您真的想将其完全分割成2个数字，则可以通过搜索2个段或更好的点(如果将比较限制在成对的段和点对中)来找到所需的多余线段和最接近的段段，从而找到所需的额外行在循环的两个方向上，所有已添加的段在循环中被分隔开.所有添加的段在循环中都是两次，因此新循环中始终会有2个部分被所有部分分开.
If you really want to completely split it in 2 figures the extra line you need can be found by searching the 2 segments or better the point and the segment closest to each other if you restrict the comparison to pairs of segments and points which are separated in the loop by all of the already added segments in both directions of the loop. All added segments are twice in the loop and so there will always be 2 parts of the new loop that will be separated by all of them.
评论您对提案1的回答
由于我没有足够的学分，我尚无权评论您的答案，因此，我会将评论添加到我自己的答案中.
I don't have the right yet to comment your answer because I don't have enough credits, so I will add the comment to my own answer.
我正在看您的示例，但我首先对它进行了误解，因此我修改了此评论.
I am looking at your example, which I misinterpreted first so, I adapted this comment.
您有3个孔，因此算法的第一部分将添加您显示的3个细分.
You have 3 holes, so the first part of the algorithm will add the 3 segments you are showing.
是的，显然，算法第二部分存在问题.您需要第4行，但是在这种情况下，没有2个部分，它们在两个方向上都被所有3个添加的段分开，或者我还是看不到它们.
我假设新循环中总会有2个部分被所有新段分开.如果存在三个或三个以上的孔，则该假设是错误的.
And, yes, you clearly have a problem case for the 2nd part of the algorithm. You need the 4th line but in this case there are no 2 parts, which are separated by all 3 added segments in both directions or I don't see them immediately anyway.
I assumed that there will always be 2 parts of the new loop that will be separated by all of the new segments. That assumption is wrong when there are 3 holes or more.
但我会进一步考虑.
提案2
我现在正在考虑另一种可能的算法.
I am now thinking about another possible algorithm.
-
计算图中每个孔的表面.选择每个孔的一个角.
Calculate the surface of each hole in the figure. Pick one corner of each hole.
在最小的2个孔的选定角上画一条线.
它可以是任意两个孔，但是采用最小的孔可以增加用更少的线切割更多孔的机会.
如果仅剩一个洞，只需在已获得的一点上画一条线即可.方向无关紧要.我会选择通过选定的点和定义该孔的最接近的其他点画一条线.
Draw a line through the chosen corners of the smallest 2 holes.
It could be any 2 holes, but taking the smallest ones increases the chance to cut more holes with less lines.
If only one hole left, just draw a line through the one point you have got. The orientation doesn't matter. I would choose to draw the line through the chosen point and the closest other point defining the hole.
检测绘制的线与图形段的所有交点，以将线缩小为一组完全在图形内部并连接图形不同环的线段.忽略在同一循环中始端结束的任何段.
如果发现的线段仅在一个点上碰到一个孔.将线段中的一个移到最靠近该点的同一孔的点，以免最后得到一个具有接触外部的孔的图形.
检查与修改后的路段是否有新的相交，如果发现任何相交，再将其拆分.
查找所有相交点需要将找到的线与图的所有线段进行比较，这也是很多计算，但是在计算相交线之前，可以通过检查线是否跨越线段的边界框来跳过计算.我将从计算与外部循环的交点开始，以便尽快为该线的其余部分提供一个边界框，因为这也有助于检查不需要为交点进行比较的部分.
您也可以通过将每个找到的线段替换为连接已连接线段的最接近端点的线段(如果尚未位于2个线段的连接点中)来进行优化.这样做可以避免为新图形创建额外的点，并增加了一步消除更多孔的机会.但是随后，您将需要再次检查新的交叉点，并重复此优化操作，直到找到更多的交叉点为止.
还有另一种可能的优化方法:检查尚未切出的孔的点是否与找到的线段接近，然后将找到的线段分为2个线段，以在同一步骤中也捕获该孔.就像以前的优化一样，这也需要再次检查新的交叉点.
Detect all intersections of the drawn line with segments of the figure to reduce the line to a set of segments which are completely inside the figure and connect different loops of the figure. Leave out any segment that start end end on the same loop.
If a hole is just touched by the found segments in one point only. Move one the segments to the point of the same hole closest to that point to avoid ending up with a figure having a hole that touches the outside.
Check for new intersections with the modified segment and split it up again if any found.
Finding all intersections requires comparing the line found to all segments of the figure which is also a lot of calculation, but you can skip calculations by checking that the line crosses the bounding box around a segment before calculating the intersection. I would start by calculating intersections with the outer loop to have as soon as possible a bounding box for the remaining part of the line because that can also help to check for sections that you don't need to compare for intersections.
You can also optimize by replacing every found segment by a segment connecting the closest end points of the connected segments (if not already in the connection point of 2 segments). Doing that avoids creating additional points for the new figures and increases the chance to get rid of more holes in one step. But then you would need to check again for new intersections and repeat this optimization until you find no more intersections.
And one more possible optimization: check for points of the holes that haven't been cut yet that are close to the found segments and split the found segment in 2 segments to catch that hole also in the same step. Just like the previous optimization, this also requires to check for new intersections again.
使用这些片段将图形分割成2个图形，并对每个仍然有孔的新图形从第2步开始重复.
Use the segments to split the figure into 2 figures and repeat from step 2 for every new figure that still has holes in it.
缺点是最终可能会得到2个以上的图形(最大(n +1)/2个图形，其中n是孔的数量)，但是如果您有很多孔而导致许多图形，则可能会重新组合其中的一些.
The drawback is that you might end up with more than 2 figures (max (n +1)/2 figures with n being the number of holes), but if you have many holes resulting in many figures it might be possible to recombine some of them.
这篇关于将带孔的多边形转换为多个无孔的简单多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
