How to determine a diagonal is in or out of a concave polygon?

Question

The diagonal (a diagonal is a segment connecting nonadjacent vertices) of a concave (non-convex) polygon can be completely in or out of the polygon(or can intersect with the edges of polygon). How to determine whether it is completely in the polygon?(a method without point-in-polygon test).

Answer 1

If the diagonal has at least one intersection with the edges, it is partially in and partially out of the polygon, however, If the diagonal has no intersection with them, there are only two states: it is compeletely in or completely out of the polygon.

To determine whether it is in or out of the polygon:

Suppose polygon's vertices are sorted counterclockwise. Consider one of the endpoints of the diagonal which lies on the vertex named P[i] (the other endpoint is p[j]). Then, Make three vectors whose first points are p[i] :

V1 : p[i+1] - p[i]

V2 : p[i-1] - p[i]

V3 : p[j] - p[i]

The diagonal is completely in the polygon if and only if V3 is between V1 and V2 when we move around counterclockwise from V1 to V2.

How to determine whether V3 is between V1 and V2 when we go from V1 to V2 counterclockwise? go to here.

I've written a program using this method and it works effectively .

Answer 2

How to determine whether it is completely in the polygon?

If you want to determine whether a diagonal never leaves the polygon's boundary, just determine whether or not it intersects any lines between two adjacent vertices.

• If it does, it's partially in and partially out of the polygon.

• If not, it's either completely in or completely out of the polygon. From there, the simplest method is to use the point-in-polygon on any point on the diagonal, but if you don't want to do that, use the winding algorithm.

Answer 3

I believe John's answer misses an important case: when the diagonal is completely outside the polygon from the get-go. Imagine making the diagonal "bridge" the two towers of his "u" shaped polygon.

I had to solve this several years ago, so please forgive if my recollection is a bit spotty.

The way I solved this was to perform line intersection tests of the diagonal against every edge in the polygon. You then have two possible cases: you either had at least one intersection, or you had no intersections. If you get any intersections, the diagonal is not inside the polygon.

If you don't get any intersections, you need to determine whether the diagonal is completely inside or completely outside the polygon. Let's say the diagonal is joining p[i] to p[j], that i < j and you have a polygon with clockwise winding. You can work out if the diagonal is outside the polygon by looking at the edge joining p[i] to p[i+1]. Work out the 2D angle of this edge (using, say, the x-axis as the baseline.) Rotate your diagonal so that the p[i]-p[i+1] edge is its baseline and compute its 2D angle.

Once you've done this, the 2D angle of the diagonal will be positive if the diagonal is outside the polygon, or negative if it's inside the polygon.

Answer 4

With regard to checking for intersections between line segments (which is the first step you would likely have to do), I found the explanations on SoftSurfer to be helpful. You would have to check for an intersection between the diagonal and any of the edges of the polygon. If you are using MATLAB, you should be able to find an efficient way to check intersections for all the edges simultaneously using matrix and vector operations (I've dealt with computing intersection points in this way for ray-triangle intersections).

Answer 5

John's answer is spot on:

If you want to determine whether a diagonal never leaves the polygon's boundary, just determine whether or not it intersects any lines between two adjacent vertices. If so, it's left the polygon.

A efficient way to do this check is to run the Bentley-Ottman sweepline algorithm on the data. It's easy to implement but hard to make numerical stable. If you have less than ... say ... 20 edges in your polygons a brute force search will most likely be faster.