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.

Answer 2

It's possible, but if the polygon is not convex then splitting it across a line potentially leads to more than two polygons.

Traverse the polygons edges, and for each edge determine whether it intersects the line. Find the first such edge which does so. Continue traversing until you find another such edge, but add each you encounter along the way to a new polygon (including the part of the first edge which was split by the line which is on "this side" and likewise for the last edge). Finally, add a closing edge to the new Polygon. Now continue processing edges - on the other side of the line, creating another Polygon in the same manner. You now have two polygons split across the line. The same technique will work, if you are careful, with splitting a non-convex polygon into multiples polygons.

Beware of corner cases such as the line crossing a vertex of the polygon, and the line not intersecting the polygon at all.

Edit: As xan points out, this won't handle all non-convex cases properly. This can be fixed with a small modification to the algorithm. Before you add the closing edge as described above, you must first check if any further edge of the original polygon would intersect that closing edge; if so, you close only up to that edge and continue processing further edges from that point.