I am writing an algorithm that splits complex (self-intersecting) polygons into one or many simple polygons so that they can be used in my collision detection algorithm. You can add / remove vertices and create new polygons.
For this, I recognize all segment intersections in the polygon and sort them by the lower intersection point x, to then treat each segment intersection in the correct order. However, there are two types of intersections that can occur, and I have to divide the polygon differently depending on which type has occurred. Here are two possible cases:
I already know what I should do to handle each type of intersection, but I do not know how to determine if a particular intersection is Case 1 or Case 2. Is there a way to determine this? I have all the information I need in my algorithm (vertices and their order, intersection and segments that caused them …).
Suppose there is an intersection between the segments (P_i, P_i + 1) and (P_j, P_j + 1) at point Q with j> i.
Case 1: I divide the polygon into 2 polygons, [Q, P_i+1, …, P_j , Q] and [Q, P_j+1, …, P_i, Q],
Case 2: I insert a vertex V in the polygon and the resulting polygon is [P1, …, P_i, V, P_i+1, …, P_j, Q, P_j+1, …, P1]
The missing information I need is to find out if the loop has formed [Q, P_i+1, …, P_j] is an "outer" loop (case 1) or an "inner" loop (case 2).
I've read things about the looped signed area of the polygon, but have not understood everything. I'm not looking for the most efficient algorithm, just one that would work. Many Thanks!