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).

Answer 2

First construct the planar straight-line graph (PSLG) of the polygon. In other words, treat the polygon as a bunch of segments and split segments at each intersection. There's an edge case in that two or more segments can overlap in a nontrivial segment, not a point. In the PSLG, the intersection segment should be single, separate segments, but we're also going to need to know how many line segments had segment overlap with it. Hence, this degenerate polygon (A-B-C-D-E-F-G-A)

A-C-B-D
|    /
|   /
G--E---F

turns into

   3
*-*-*-*
|    /
|   /
*--*---* ,
     2

omitting all of the labels that say 1.

The next step is to compute the combinatorial embedding of this PSLG. This means we loop over the vertices, sorting the incident edges of each vertex by angle in counterclockwise order. In standard computational geometry fashion, we can use signed area to get a comparator that doesn't involve trig.

Now, we have a data structure like so.

   3
t-u-v-w
|    /
|   /
x--y---z ,
     2

t: t-u, t-x, t-y
u: u-v (3), u-t
v: v-w, v-u (3)
w: w-v, w-y
x: x-y, x-t
y: y-z (2), y-w, y-x
z: z-y (2)

We get a permutation on oriented edges (darts hereafter) where each one points to the next one in the list (wrapping around if need be).

t-u -> t-x
t-x -> t-u
u-v (3) -> u-t
u-t -> u-v (3)
v-w -> v-u (3)
v-u (3) -> v-w
w-v -> w-y
w-y -> w-v
x-y -> x-t
x-t -> x-y
y-z (2) -> y-w
y-w -> y-x
y-x -> y-z (2)
z-y (2) -> z-y (2)

We compute the dual of this embedding by constructing a new permutation where each dart points to the reverse of its current assignment.

t-u -> x-t
x-t -> y-x
y-x -> z-y (2)
z-y (2) -> y-z (2)
y-z (2) -> w-y
w-y -> v-w
v-w -> u-v (3)
u-v (3) -> t-u

t-x -> u-t
u-t -> v-u (3)
v-u (3) -> w-v
w-v -> y-w
y-w -> x-y
x-y -> t-x

Now, I've grouped the permutation into cycles. These cycles are the faces of the PSLG (inside the polygon in clockwise order, and the infinite face in counterclockwise order). Use a signed area test to find the infinite face.

Going back to a graph representation, do a depth-first search on the faces rooted at the infinite face, labelling each face as odd (if the sum of the numbers on the edges is odd) or even. The collection of odd cycles are the result that you're looking for.

Actually, now that I've written out this whole answer, better to just delete the even-multiplicity segments at the start to smush adjacent polygons together. This may result in multiple infinite faces, but the detection method still works.