Detect 2 different cases of polygon self-intersection (intersection occurred inside or outside)

Question

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. This can be done by adding/removing vertices and creating new polygons.

To do so I detect all segment intersections in the polygon and sort them by lower intersection x, then handle each segment intersection in order. However, there are two types of intersection that can occur, and I need to split the polygon differently depending on which type has occurred. Here is an illustration of the two possible cases:

I already know what I should do to handle each intersection type, but what I don't know is how can I detect whether a given intersection corresponds to case 1 or case 2. Is there a way to determine this? I have all the information I needed in my algorithm (vertices and their order, intersection and segments that caused them, ...).

Suppose there is an intersection between segments (P_i, P_i+1) and (P_j, P_j+1) at point Q, with j>i.

Case 1: I split the polygon in 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]

So the missing piece of information I need is to figure out whether the loop formed by [Q, P_i+1, ..., P_j] is an "outer" loop (case 1) or an "inner" loop (case 2).

I've read stuff about signed area of the polygon formed by the loop but didn't understand all of it. I'm not looking for the most efficient algorithm, just one that would work. Thanks!

Answer 1

If you split complex polygons into simple polygons at intersections; then:

• case 1: the simple polygons don't overlap

• case 2: the simple polygons overlap and one of the simple polygons is actually an "inverse polygon" (describing what to exclude and not describing what to include).

This difference can be determined by an "are all vertices in one polygon inside the other polygon or touching the other polygon" test.

Note that for case 2 you may be able to insert one polygon back into the other to end up with a single simple polygon (e.g. for your diagram you'd end up with "P1, intersection, P3, P2, intersection, P4, P5, P6").

However, there are more cases you've overlooked. For an example, starting with your second diagram (for case 2) drag P3 upward so that it's above the line from P6 to P1 (causing there to be no polygon on either side of part of the two edges involving P3). For another example, consider a "figure 8" with six vertices where there's two edges in the middle that are identical (which could be converted into a simple rectangle by deleting both middle edges).

For even more fun, consider something like this (but without the outer circle):

Mostly, the chance of getting it to work correctly for all possible cases is zero; and the only sane solution to the problem is prevention (finding a way to prevent the need to deal with complex polygons).