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.
Asked
Active
Viewed 312 times
1 Answers
0
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.
Frank Puffer
- 8,135
- 2
- 20
- 45
-
How are the rays from the point extended? There can be infinite number of them. Also in picture provided by me I don't see how odd/even would be differentiated. To me it looks like it would always be the same count. – Altidore Apr 02 '16 at 22:15
-
@Altidore: It does not matter, theoretically you can use any direction. However in your example, a horizontal ray would be a bad choice because it is collinear with some edges. That's one of the special cases I mentioned. – Frank Puffer Apr 02 '16 at 22:17
-
@Altidore: Just to clarify: Unllike a line that extends from a point in both directions, a ray extends only in one direction. So you only count the intersections on one side of the point. – Frank Puffer Apr 02 '16 at 22:25
-
Ok that clarified this immensly. I was wondering how there would be a different count of interesections with a line extended in both directions. Thank you. – Altidore Apr 03 '16 at 09:05