How to determine a diagonal is in or out of a conc

问题:

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

回答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 .

回答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.

回答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.

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

回答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.

回答6:

I understand this question was answered many years ago, but I have a new approach which is easy to implement.

As suggested in previous answers, you should first compute for all edges of the polygon if any of them intersect with the diagonal line segment. The code to compute intersection and determine if one even exists is described here.

If all edges (excluding those that share vertices with diagonal) do not have an intersection with diagonal then you know that the diagonal is either completely inside or completely outside of the polygon meaning that the midpoint of the diagonal is also completely inside or completely outside respectively. The midpoint is the average of the diagonal's two endpoints.

We now have transformed the problem to computing whether the diagonal is inside or outside the polygon to whether the midpoint is inside or outside the polygon. Working with a single point is easier than with a line.

The way to determine if a point is within a polygon is described here and can be summarized by counting the amount of intersection of horizontal ray starting at the point and seeing how many polygon edges this ray intersects. If the ray intersects an odd amount of times then the point is inside the polygon and otherwise outside the polygon.

The reason why this implementation is easy to implement is while you iterate through all the edges to check for intersection with diagonal you can now also count if the diagonal's midpoint's ray intersects with the current edge being processed. If your for loop returns with no intersection between diagonal and edges then you can see the even/odd count to determine if diagonal is inside or outside.