3
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\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, 2019 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, 2019 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, 2019 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, 2019 at 3:27

1 Answer 1

Reset to default
3
$\begingroup$

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.

          Fig10[1]
          Fig.10f, p.23.

Improve this answer
$\endgroup$
1
  • $\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, 2019 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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