Split an arbitrary polygon with many line segments

geometrypolygons

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.

Best Answer

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.

Related Solutions

[Math] How many rectangles can fit in a polygon with n-sides

As has been mentioned over at SO, this problem is very difficult from a computational perspective. It may help to see what methods have been implemented for the packing problem. There are some algorithms out there, but you may have to fine-tune one to fit your needs.

Even a naive, greedy approach may end up being pretty inefficient. Would you take into account things like rotating the shape? There are all kinds of trade-offs to be made, but your "slices" (first fit) approach may work if you need something quick and dirty.

rotate

Efficient way to find all polygons of the same shape within a set, regardless of position, scale, or rotation

Luckily I hang out with a bunch of people on Twitter and Mastodon who are way smarter than me, and they came up with some great ideas.

The core solution here is to concatenate one of the lists being compared to itself. For two equal-length sets $A$ and $B$, if $A \subset B^\frown B$ then $A$ must be the same sequence of $B$ with some rotation. This reduces the problem to a string search.

To demonstrate:

$$A = [1,2,3,5,2]$$ $$B = [3,5,2,1,2]$$ $$B' = B^\frown B = [3,5,2,\mathbf{1,2,3,5,2},1,2]$$ $$A \subset B'$$

For those not familiar with the notation (and for me when I inevitably come back to this answer in a year and I've forgotten set notation) the approach is essentially:

let a = "12352";
let b = "35212";
let b2 = b + b;
return b2.includes(a);

This can be optimised in a few ways.

First, the concatenation does not have to use $O(2n)$ memory, since the search can be performed on the original set by computing the search pointer (or array index) modulo the set length.

A KMP string search has a worst-case performance of $O(m)$ pre-processing and $O(n)$ matching, where $m$ is length of the string we're searching for and $n$ is the length of the string we're searching in. Since all polygons in each hash group need to be compared to each other, the pre-processing can be reused for repeated comparisons.

The KMP approach can then be modified a little to find a lexicographically minimal string rotation during the pre-processing step. This improves the average-case search performance a lot, because it is far more likely that $A$ and $B$ will have matching rotations. It's also a free optimisation, because it has the same $O(m)$ time complexity as the regular KMP pre-processing step.

Credit to @goopypanther for first suggesting the subset approach, and Jannis Harder (@jix) for suggesting the lexicographical rotation trick.

Best Answer

Related Solutions

[Math] How many rectangles can fit in a polygon with n-sides

Efficient way to find all polygons of the same shape within a set, regardless of position, scale, or rotation

Related Question