Converting a polygon with holes into multiple simp

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:

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?

回答1:

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.

Proposal 1

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.

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.

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.

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.

Comment on your answer to proposal 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.

You have 3 holes, so the first part of the algorithm will add the 3 segments you are showing.

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.

But I will think further about it.

Proposal 2

I am now thinking about another possible algorithm.

Calculate the surface of each hole in the figure. Pick one corner of each hole.
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.
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.
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.

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.

回答2:

I'm using this answer to visualize my comment to @Stefan Mondelaers:

That's why I use constrained Delaunay triangulation. But you are right, I also think that's too much work.

Sadly the CAD really requires more than one loop, because all points in a loop have to be unique.

I think the second part of your algorithm doesn't work.

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.

Looking at this example, where orange is the outside polygon and blue are its holes. The first part of your algorithm will do this: But now the second part would only add connections between the blue polygons, for they are closest. But this wont resolve the problem with the loop holding the orange polygon, because the newly introduced point on it will be in there twice.