Determine if Line Segment Between Polygon Vertices is “Inside” Polygon

2
votes

I'm trying to find an efficient algorithm that can check if a line between two vertices in a simple (edit: simple concave) polygon contains points that lie outside the domain of the polygon. The closest question I could find is this one: https://stackoverflow.com/a/36378838/12135804

But I'm not sure the answer is quite right. It might be, in which case if someone could clarify that would be great.

The basic idea is illustrated in the below picture: enter image description here

Where I would like the red line to fail and the green line to succeed. I know one can't naively test the midpoint as that wont work in every case, but finding any point on the line outside the polygon's domain should disqualify it.

I appreciate any and all help!

Edit: Forgot to include cross-post link to mathematics stack exchange: https://math.stackexchange.com/q/4040059/892519

2
algorithmgeometrypolygoncomputational-geometryline-segment
Do you mean "convex hull"? Search for that, it's a solved problem. ;) – Ulrich Eckhardt
No, edited to be more clear. This is for concave polygons. The above algorithm wouldn't really be applied to convex polygons since any line between two vertices would automatically lie within the polygon. That being said, it would still technically work for convex polygons as I wouldn't mind lines that are part of the polygon. – Optimum
Do a hit test on point very near endpoint of your line (shifted slightly inwards to the line center) so if line is AB then test point C = A + 0.000001*(B-A) ... – Spektre
I think that would work, since both points could be subjected to a point-in-polygon test and if one fails then bingo. – Optimum

2 Answers

0
votes

Let's assume that the topmost point is A and the others are named B, C ... counter-clockwise, so we know what we're talking about.

If you take the red segment B-D, the one point in between is on the left. If you take the green segment D-F, the one point in between is on the right. Now, a more interesting segment would be B-E, where C is on the left while D is on the right.

In order to determine left and right, use the vector product. The length depends on the sin function, so if you get a value less than zero it's one side and more than zero is the other side.

0
votes

After a lot of googling, I finally found this answer to a stackoverflow question from ~12 years ago: https://stackoverflow.com/a/693877/12135804

Assuming the edges in the polygon follow a certain order, a simple ccw test can be created using a line's starting point (p), the next ccw point in the polygon from that starting point as an inflection point (q), and the endpoint of the line (r). For the red line BD, the test would check if B,C,D is ccw (it's not). For the green line DF, test if D,E,F is ccw (it is!). This would work even if the points are non-consecutive. However, this would fail when the order of the red-green lines is reversed. For instance, if the red line became DB, the test would check D,E,B, which would pass the ccw test.

I think a more robust solution is to search for the pair of two edges in the concave polygon that share the endpoints of the line to test. For both pairs, calculate the angle between the two edges to the x-axis. Calculate the angle of the line to the x-axis as well. If the line is within the polygon, the line's angle should lie between the max and min of the polygon edges' angles for both endpoints.

Whether to test the obtuse or acute range of angles depends on some factors, I think. The red line's angle at B w.r.t. to the x axis would be in the obtuse bound between AB and BC, and the same is true at point C. Visually, it's plain to see the acute bound is what needs to be used for the max/min test at both points. If the baseline to compute the bounds from can be chosen logically, then it can be done.

Of course, this doesn't work if the line crosses outside the polygon on the way between both endpoints, but this does handle the degenerate case for a normal line-polygon intersection test. Assuming it works in every degenerate case, that is.

I won't mark this an answer because I can't prove it.

Edit: Well, I came back to thinking about this again and decided to search for questions similar to the angular bounding I posed above, and found this: https://stackoverflow.com/a/17497339/12135804

This answer satisfies not knowing the orientation of the lines! However, it assumes the minimum bound between A and B should be tested. This doesn't work for concave vertices, when AxB is < 0. In this case, a line attached to the vertex shared by lines A and B will return true if it's pointing outside the polygon, and conversely false if it's inside. I think flipping the result based on the sign of AxB should be enough to account for this, though. (a hunch that is verified in this related answer: https://stackoverflow.com/a/43384516/12135804)