I'm looking for code that will decompose a non-simple (intersecting edges) polygon into simple polygons. I know there are several implementations that will triangulate a complex polygon, but that doesn't fit my needs. The following link mentions how to do this: http://geometryalgorithms.com/Archive/algorithm_0108/algorithm_0108.htm (Towars the middle of the page is what I am after). However this looks to be reasonably complex code to implement and I don't want to reinvent the wheel if this already exists somewhere. Any help appreciated.

I didn't read it that carefully, but it says on that page that they've implemented that method, and that there is C++ code at the bottom of the page (which there is). I don't know if this is a complete implementation of what you want, but I guess it'd provide some of the framework for what you require.

Dan

Compute all edge-edge intersections. If a point of intersection of two edges is interior to one (or both) of the edges, split that edge into two edges (split both edges). You can do this step efficiently using a sweep algorithm. The sample application MeshEnvelope uses such a method (although with exact rational arithmetic).

What you have now is a vertex-edge graph for which you need to compute the minimal cycle basis.