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

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 2

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.

Answer 3

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