How to distinguish the incoming and outgoing edges of a polygon?

Question

The basics of the Weiler-Atherton Polygon Clipping algorithm are:

• Start at the first edge that is inside the clipping region.
• When the edge of the candidate / subject polygon enters the clipping area, save the intersection point.
• When the edge of the candidate / subject polygon leaves the clipping area, save the intersection point and follow the cropping polygon.

How to distinguish the incoming and outgoing edges of a polygon?

It seems that the search for incoming boundaries calls another huge algorithm and thereby affects the efficiency of the algorithm.

Another question: how can I find the first incoming intersection?

This answer seems to shed light on the problem . But unfortunately, this will not work.

For example, if I change the direction of the 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

Firstly, a reminder that the Weiler-Atherton algorithm uses polygons defined by vertices in a certain order clockwise. In short, you verify that the edges go or go by moving the polygon clockwise . The first intersection (and therefore the first incoming intersection) is simply the first intersection of the edge that started outside the clipping region (see below).

In addition, the algorithm is usually performed in two stages. First find all the intersections, they are added to the list of vertices for your polygons inserted in the correct position. At this point, you usually indicate whether each vertex is inside another polygon. For the second phase, cross the vertices to determine the cutting polygons.

Let's try some examples. Take the triangle defined by the vertices A, B, C and the rectangle w, x, y, z. The triangle will be the clipping region, the rectangle is the object.

Thus, the list of points that we created for the subject is w, x, R, Q, y, z. The list of triangles is now A, B, Q, C, R.

Starting with w, R is the first intersection, it is incoming, since the previous point (x) is outside. Traversing the area will be R, Q, C and back to R (done).

The unmarked ones intersect here, but they will still be R and Q. Thus, the list of points that we created for the subject is w, x, R, y, Q, z. The list of triangles is now A, B, C, Q, R.

Cropping bypass is R, y, Q and R (done)

Answer 2

Let P and Q be two polygons. You can select any vertex v of P to determine the position of v with respect to Q (that is, inside or outside) through the ray casting algorithm (or any other algorithm that satisfies 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 way, since the position of other vertices from P can be inferred by iterating over an ordered set of vertices and intersection points of P

Suppose v is outside of Q Then, iterating over the ordered set of vertices and intersection points P , the first intersection point found is on the input edge. If v is inside Q , the first intersection point that can be found lies at the exit from the edge. Keep in mind that one edge can be both input and output, depending on the number of intersection points lying on it.

The idea of ​​the ray casting algorithm is simple, but you need to select the vertex v of P if |V(P)|>=|V(Q)| and v of Q otherwise (to reduce the impact of the ray logging algorithm on overall performance, although not significantly).

Answer 3

You don’t have to start work with the first incoming intersection, it’s great when you look at the polygons drawn on a piece of paper and you can drop the pen where you want, but, as you noticed, it will take more effort to find when coding.

You just need to make sure that you get all the intersections calculated for your two polygons, first going around the line segments of the source polygons, checking for intersections with the polygon clipping segments. At this moment it does not matter, inside or outside.

Once you have all the intersections and points of your two polygons in order (I think I had two lists that could communicate with each other), go around the points around your original polygon. If your first source polygon point is inside the clip polygon, which is the first point of your solution polygon, if not the first point of your solution polygon, this is the first intersection with the clip polygon.

As soon as you have the first solution, each point from there will be the next decision point. When you click the intersections, you switch to another polygon and continue moving until you return to your first solution point.

It has been some time since I encoded this, but if I remember correctly that you can catch you when the polygons are completely inside each other (in this case containing your solution) and make sure that you are prepared for several polygons of the solution, if you have odd polygon shapes.