1

First I know there is similar question already asked, but it uses different structure and is in C (Divide self intersecting polygon (C Code)) , my question is a little different.

I have points of self-intersecting polygon, its edges and also I am able to find points where it intersects itself using Bentley–Ottmann algorithm.

I planned to build non-self intersecting polygons by editing edges around intersection points, but problem is when you have two edges that intersect, you don't know which two of the four sides are inside, and which are outside of polygon.

I could use ray crossing algorithm to resolve this, but it is too slow. Its time complexity is O(n), and I'd have two do it at least two times for every intersection point. So it would be extremely slow with around 200k points of polygon.

So what I'm asking is, is there any faster way to divide self intersecting polygon into non-self intersecting ones.

I need this because I am doing polygon triangulation. I already done sweep-line triangulation algorithm for triangulating non-self intersecting polygons with holes. So I just need tho have array of these polygons as input.

Community
  • 1
  • 1
fuzzomorphism
  • 79
  • 1
  • 10
  • 3
    If you've found a very similar question, but it doesn't quite solve your problem, at least link to it, so that others can potentially use it to adapt their solutions to your case. You also say that your structures are different, but don't explain what your structures are. – Servy Mar 27 '14 at 16:18
  • 3
    This question appears to be off-topic because it is about Computer Science – Niklas B. Mar 27 '14 at 16:29
  • I would suggest you to ask this on http://cs.stackexchange.com – Niklas B. Mar 27 '14 at 16:29
  • Since the end-goal appears to be triangulation of self-intersecting polygons, why not just use a triangulation method that can handle non-simple polygons from the start as opposed to trying to modify a simple only method? FIST is an ear-clipping variant that can triangulate self-intersecting polygons, though the source is in C. The source can be requested [here](http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html), and the algorithm is described in detail [here](http://pdf.aminer.org/000/750/201/fist_fast_industrial_strength_triangulation_of_polygons.pdf). – ssell Mar 27 '14 at 16:34
  • Servy I'm sorry, I edited my post, i don't explain what structures are in my algorithm because I think they do not matter so much for this question, and in other similar question structures are mentioned because they seem important. ssell thanks for suggestion, I already found about that algorithm, but I'm not sure about its time complexity, since my algorithm needs to be really fast because of large number of points. However, I'l look more into it now, and if I don't find way to modify my current algorithm, I'm going to try it. – fuzzomorphism Mar 27 '14 at 16:38

1 Answers1

2

As a preprocessing step you can calculate for each edge, which side of the edge determines the outside of the polygon. This is much cheaper than O(n) time for every intersection point. Then when two edges intersect, you can determine which two line segments are outside and which two are inside.

user2566092
  • 4,631
  • 15
  • 20