Algorithm to divide self intersecting polygon

Question

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.

Answer 1

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.