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).

Current result

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 enter image description here

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

  • $\begingroup$ 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. $\endgroup$ – Discrete lizard Jul 21 '19 at 10:58
  • $\begingroup$ 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 :) $\endgroup$ – rowanwins Jul 21 '19 at 11:56
  • $\begingroup$ 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. $\endgroup$ – Discrete lizard Jul 21 '19 at 14:09
  • $\begingroup$ 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 :) $\endgroup$ – rowanwins Jul 22 '19 at 3:27

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.

          Fig.10f, p.23.

| cite | improve this answer | |
  • $\begingroup$ Thank you @joseph-orourke . I've seen this paper however it seemed to differ in approach from the blog post above which would mean rewriting what I have thus far which I'd like to avoid :) $\endgroup$ – rowanwins Jul 23 '19 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.