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 swear by Angus Johnson's Clipper library:

http://www.angusj.com/delphi/clipper/documentation/Docs/Overview/_Body.htm

It uses the Vatti algorithm, which involves some complex tree structures to keep track of intersections. It handles polygon holes, multiple overlapping polygons, merges nearly parallel lines with fixed point, and its tagging mechanisms let you do some pretty detailed tracking of what intersected what where after the fact.

Answer 2

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.