Robust line of sight test on the inside of a polygon with tolerance
- by David Gouveia
Foreword
This is a followup to this question and the main problem I'm trying to solve. My current solution is an hack which involves inflating the polygon, and doing most calculations on the inflated polygon instead. My goal is to remove this step completely, and correctly solve the problem with calculations only.
Problem
Given a concave polygon and treating all of its edges as if they were
walls in a level, determine whether two points A and B are in line of
sight of each other, while accounting for some degree of floating point errors.
I'm currently basing my solution on a series of line-segment interection tests. In other words:
If any of the end points are outside the polygon, they are not in line of sight.
If both end points are inside the polygon, and the line segment from A to B crosses any of the edges from the polygon, then they are not in line of sight.
If both end points are inside the polygon, and the line segment from A to B does not cross any of the edges from the polygon, then they are in line of sight.
But the problem is dealing correctly with all the edge cases. In particular, it must be able to deal with all the situations depicted below, where red lines are examples that should be rejected, and green lines are examples that should be accepted. I probably missed a few other situations, such as when the line segment from A to B is colinear with an edge, but one of the end points is outside the polygon.
One point of particular interest is the difference between 1 and 9. In both cases, both end points are vertices of the polygon, and there are no edges being intersected, but 1 should be rejected while 9 should be accepted. How to distinguish these two? I could check some middle point within the segment to see if it falls inside or not, but it's easy to come up with situations in which it would fail.
Point 7 was also pretty tricky and I had to to treat it as a special case, which checks if two points are adjacent vertices of the polygon directly. But there are also other chances of line segments being col linear with the edges of the polygon, and I'm still not entirely sure how I should handle those cases.
Is there any well known solution to this problem?
