Split an arbitrary polygon with many line segments

Question

I am looking for a formula/algorithm that would allow me to split an arbitrary polygon into smaller polygons using line segments.

Example 1:

All the algorithms I can find split using lines (defined by segments), as opposed to actually splitting using the segments.

This is important, because I am making many such splits "all at once", and two segments that, individually, wouldn't be able to split the polygon, now can split it.

Example 2 (Segment that will cut the polygon without splitting):

Example 3 (Two segments that, together, can split the polygon in two, but separately wouldn't)

You can imagine that the polygon is an arbitrarily shaped flat piece of wood, and the segments are straight lines we cut into it with a saw, and I would like to know what the resulting pieces of wood look like (how many and their shape)

I want to extend this behaviour to any polygon shape, and any number of "cutting" segments.

I absolutely do not mind any leftover duplicate points in the results, I can easily "clean it up" afterwards to remove consecutive duplicate points.

Answer 1

Warning : I'm not 100% sure this works. If you implement it, tell me how it went.

This is how I would do it. First, you want to have an implementation of polygons that have exterior segments and interior segments. The interior segments are not part of your final calculated polygon, but are going to be needed when you calculate new polygons. You are also going to want to think of the segments as being slowly drawn from a starting point to an end point for what I'm about to describe. When you draw a segment, compute if the starting point of the segment is inside a polygon or outside.

• If it's inside, the segment is either going to cross a segment or not. If it doesn't, add the new segment as an interior segment to the polygon. Whenever it crosses another segment, iteratively select all segments (except the one we are currently drawing) that touch the crossed segment, and attribute those stored segments to the point at which it crossed. If you end up without crossing a selected segment, or if you end up outside, it means you are ending up with new interior segments. Simply calculate in which polygon each segment portion is, and add them as interior segments to the polygon. If you end up outside at this stage, start anew from the cross point. Whenever you cross a segment that has been selected, you are dividing a polygon into two polygons. You will want to store the previous segment portions as interior segments, if they exist, before going to the next step.
  1. Take the two attributed points that have the touching segments. If the first point's selected segments contain any "exterior segment" of one of the stored polygon, then you are dividing this polygon in two more parts. To store those new parts, take the two points that had an intersection as an attribute. There are two ways to go from a point to another using the selected polygon, without revisiting segments. Just brute force every possible path (using the segments) to find them. By combining the two ways with the segment portions between the two points, you get the two polygons. Don't forget to remove the old polygon.
  2. Else, you are making an interior polygon. Simply make a polygon by finding a path from one of the two points to the other, using the segment portions between the two points and the selected segments, then take the polygon that we are into and add the contour of the freshly added polygon as exterior segments, so that we have a polygon with one more hole. After you are done dividing the polygon, recalculate every interior segment as a new cut to attribute them to the right polygons, then start a new line from the last point drawn and repeat until we reach the end point.
• If it's outside, the segment is either going to cross a segment or not. If it doesn't, end the process. If it does, start the process as if the segment started at the border point.
• If it's at the border of any segment (corners included), figure out if the line is going into a polygon or outside. If it's going into a polygon, do as if the point started inside the polygon and intersected the first segment. If it's going outside, take a very close point outside and do as if the segment started here.

If you reach the end point, you are inside the polygon. Add the last segment as an interior segment to the polygon the segment is in.