Given a concave polygon, how can I determine whether a segment(edge) connecting two vertices lies within the polygon? In picture below there is an edge(red) connecting two same vertices that weren't connected in original polygon. I have no idea how determine interior and exterior. Thank you for any help.
1 Answers
0
votes
If the additional segment intersects any other segment of the polygon, it is partly inside and partly outside.
Otherwise take a point on the additional segment, for example its midpoint and check if it is inside or outside. To test if a point is inside, take any ray extending from it and count the number of intersections with polygon edges. If the number of intersections is odd, it is inside.
Sounds simple, but be prepared to handle special cases like collinear lines or intersections at vertex points. That's what will make the implementation difficult.
