I'm trying to find an efficient test/algorithm that can determine if any line segment between two vertices in a simple, concave polygon contains points that lie outside the domain of the polygon. I haven't had much luck in my endeavor though.
The basic idea is illustrated in the below picture:
https://i.stack.imgur.com/vaFII.png (don't have enough rep to embed, sorry :/ )
Where I would like the red line to fail because it is "outside" and the green line to succeed as it is well within the polygon.
The closest questions I could find are these on stack overflow:
Midpoint-Ray Test (?): https://stackoverflow.com/a/36378838/12135804
Projection/Intersections: https://stackoverflow.com/a/31961253/12135804
For the first one, I'm not sure the answer is quite right. It might be, in which case if someone could clarify or provide a proof that would be great. For the projection method in the second question it obviously fails because both red and green lines fall under the degenerate case. The intersection count method has the same problem, as both red and green lines intersect twice (or none, depending on your definition).
I think the key is to, for the line segment in question, find any point along its length such that it lies outside the polygon's domain. This would be true for even the most convoluted, simple, concave polygon. The trick is finding that point either very fast or with some linear algebra that I've yet to encounter.
I appreciate any and all help!
Disclaimer: this is modified from a question on stackoverflow (https://stackoverflow.com/q/66374077/12135804) and posted here. My justification is it felt appropriate, being both a geometry problem and an algorithm problem. I tried to follow guidelines here: https://meta.stackexchange.com/a/75012. I apologize if anyone disagrees and this violates any rules.