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 .