How to distinguish between an inbound and an outbound edge of a polygon?

Question

The basics of Weiler-Atherton Polygon Clipping algorithm are:

1. Start from the first edge which is going inside the clipping area.
2. When an edge of a candidate/subject polygon enters the clipping area, save the intersection point.
3. When an edge of a candidate/subject polygon exits the clipping area, save the intersection point and follow the clipping polygon.

How to distinguish between an inbound and an outbound edge of a polygon?

It seems like finding inbound edges invole another huge algorithm and thereby affects the efficiency of the algorithm.

Another question is, how can I find the first inbound intersection?

This answer seems to be shedding some light on the problem. But, sadly it doesn't work.

For example, if I reverse the direction of vectors, the angle is not negated.

https://www.wolframalpha.com/input/?i=angle+between+vector+%7B0%2C180%7D+%7B180%2C0%7D

https://www.wolframalpha.com/input/?i=angle+between+vector+%7B0%2C180%7D+%7B-180%2C0%7D

Answer 1

First, a reminder that the Weiler–Atherton algorithm uses polygons defined by vertices in a specific order, clockwise. In short, you test for edges going in or out by traversing the polygon clockwise. The first edge going in (and therefore the first inbound intersection) is simply the first edge you traverse which started outside the clipping area (see below).

Also, the algorithm is typically run in two phases. First find all intersections, these are added to a list of vertices for your polygons, inserted at the correct position. During this phase you would typically mark whether each vertex is within the other polygon. For the second phase, traverse the vertices to determine clipping polygons.

Lets try some examples. Take a triangle defined by vertices A,B,C, and a rectangle w,x,y,z. The triangle will be the clipping area, rectangle is the subject.

The list of points we have generated for the subject is therefore w,x,R,Q,y,z. The triangle list is now A,B,Q,C,R.

Starting at w, R is the first intersection, it is inbound because the previous point (x) is outside. The traversal of the area will be R,Q,C, and back to R(done).

The intersections are unlabeled here, but they will still be R and Q. The list of points we have generated for the subject is therefore w,x,R,y,Q,z. The triangle list is now A,B,C,Q,R.

The clipping traversal is R,y,Q, and R(done)

Answer 2

Let P and Q be two polygons. One can pick any vertex v of P in order to determine the position of v with respect to Q (i.e inside or outside it) via the ray casting algorithm (or any other algorithm that suits all the requirements of the problem).

You only need to determine the position of one such vertex v of P with respect to Q in this manner because the position of the other vertices of P can be inferred by iterating over the ordered set of vertices and intersection points of P.

Lets say v is outside Q. Then, by iterating over the ordered set of vertices and intersection points of P, the first intersection point one finds is laying on an entering edge. If v is inside Q, the first intersection point one finds is laying on an exiting edge. Keep in mind that one edge can be both entering and exiting, depending on the number of intersection points laying on it.

The idea behind the ray casting algorithm is simple, but one should pick vertex v of P if |V(P)|>=|V(Q)| and v of Q otherwise (in order to lower the impact the ray casting algorithm has on the overall performance, though not significantly).