Splitting a 2D polygon using multiple straight cuts

Question

How can I split a polygon into smaller polygons using multiple straight cutting lines? Imagine cutting a paper with a sharp knife. I'm looking for a known algorithm to solve this or, even better, an existing javascript library.

I don't think boolean operations will solve this, but I could of course be wrong.

Answer 1

I followed the steps provided by David Eisenstat in the comments to the question and got it to work. So basically:

1. Find all line intersections

All cutting lines and every individual line in the polygon was included. The Bentley-Ottmann sweep line algorithm can be used to find the intersection points.

2. Construct the graph

This was easily done using the intersection points and their corresponding line segments.

3. Find cycles in the graph

The graph was then decomposed into a collection of oriented cycles.