algorithm - How can I split a Polygon by a Line?

Question

As shown below,

Is it possible to split a Polygon by a Line? (into two Polygons). If the line doesn't go all the way across the polygon it would fail.

Is this possible? If so, how would I do this?

Answer 1

I had to do this recently. Just walking the polygon won't work for concave polygons, as in your diagram. Below is a sketch of my algorithm, inspired by the Greiner-Hormann polygon clipping algorithm. Splitting is both easier and harder than polygon clipping. Easier because you only clip against a line instead of a rect or another polygon; harder because you need to keep both sides.

Create an empty list of output polygons
Create an empty list of pending crossbacks (one for each polygon)
Find all intersections between the polygon and the line.
Sort them by position along the line.
Pair them up as alternating entry/exit lines.
Append a polygon to the output list and make it current.
Walk the polygon. For each edge:
    Append the first point to the current polygon.
    If there is an intersection with the split line:
        Add the intersection point to the current polygon.
        Find the intersection point in the intersection pairs.
        Set its partner as the crossback point for the current polygon.
        If there is an existing polygon with a crossback for this edge:
            Set the current polygon to be that polygon.
        Else
            Append a new polygon and new crossback point to the output lists and make it current.
        Add the intersection point to the now current polygon.