# 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

• Could you clarify what part of your solution is incorrect? It looks like your non-simple polygon it is decomposed into 2 simple polygons. I do not think a DCEL is needed here, the algorithm probably simply means a list. Jul 21, 2019 at 10:58
• Hi @Discretelizard . I've clarified the expected output above in the question. But yes good observation that I have in-fact got two simple polygons - I hadn't actually noticed :) Jul 21, 2019 at 11:56
• I'm not exactly sure what part of the algorithm you want more explained. It seems that 2 of the 3 intersections shown have not been correctly processed (if they have been processed at all), but I don't think you need me to tell you that. Put another way, try to formulate a clear question about the algorithm. Currently, I don't see what prevents you from implementing the algorithm, other than that you appear to have some bugs. However, note that debugging an implementation is off-topic here. Jul 21, 2019 at 14:09
• I was hoping someone might be able to point me to a paper or additional information which described the steps in additional detail. At the moment I'm going off a few dot points on one blog and as far as I can tell I'm doing what it's asking but it's not working... So I appreciate it's not a clear question @Discretelizard - if I knew exactly what was going wrong I wouldn't be here :) Jul 22, 2019 at 3:27