Algorithm for decomposing a complex (self-intersecting) polygon into simple polygons I've been attempting to write a Bentley-Ottmann sweepline algorithm to transform a self-intersecting (complex) into a set of simple polygons.

There are some instructions on this page (see the heading entitled "Decompose into Simple Pieces") however my current implementation is falling short (see img below).



While I'm able to find all the self-intersecting points I'm not able to construct the desired outputs when there are multiple self-intersections on a single segment.

Here is what I'd expect to get


I'm struggling to find any other papers which describe the process or required data structures in any more detail. The blog post references a linked list which could mean a Doubly Connected Edge List although I'm not 100% sure, the other challenge with that is that I don't think there is a suitable js implementation of that data structure. 

Any advice on how I might reconstruct the desired output would be appreciated
Here is a thesis on exactly this topic:


  Subramaniam, Lavanya. "Partition of a Non-simple Polygon Into Simple Polygons." Master's
  thesis, University of South Alabama, 2003.
  PDF download.



&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 


&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 

Fig.10f, p.23.