Robust line of sight test on the inside of a polygon with tolerance

Question

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?

Answer 1

Their is an fast and robust algorithm which uses preprocessing.

Because of your application I assume your polygon is also a simple polygone (http://en.wikipedia.org/wiki/Simple_polygon) - if so their exists an efficent algorithm for your problem (otherwise I have no idea)

Given a simple polygon P 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.

Preprocessing

1 ) Calculate the inner triangulation T of your polygon P without insert points (http://en.wikipedia.org/wiki/Polygon_triangulation). Since I assume your polygon is simple, there exists a various set of algorithms for triangulate it. Most ones with runtime O(n*log n) (n = number of points of you polygon) It's important for the rest of the algorithm to note that |T| = O(n) since P is a simple 2D polygone and we do not have inserted points into T.

2 ) (if your polygon P is not simple you cant perform this step) Calculate the Graph G (called dual graph of the triangulation).

• each triangle p of T becomes a node v[p] of G
• if p, q are adjacent triangles in T then insert an edge (v[p], v[q]) into G.

Ensure that you have an mapping p -> v[p] and a mapping v[p] -> p for all p in T. You will need this later on.

Since |T| = O(n) also |vertices(G)| = O(n)

G is a tree since we are not allowed to insert points into T. (ref: http://www.inf.fu-berlin.de/lehre/SS09/AG/skript.html) (written in german)

The algorithm

Given points A and B, assuming the preprocessing is done.

1) find the two triangles p and q where p contains A and q contains B. Naive this runs in O(n) by checking for each triangle p in T whether A, B is in p via 3 "left of line"-checks. I think their could be an even more efficient method if you create a tree-search-structure on T during the preprocessing step

2) use a breath first search in G from v[p] to find v[q] (G is a tree)(http://en.wikipedia.org/wiki/Breadth-first_search)

• during the search, if we go through a node v[u] check for the triangle u if the segment AB intersects with u.
  • if the segment AB does not intersect with u: we abort our search through v[u], because we can't look from A to B through u.
  • if the segment AB does intersect with u: we continue the breath first search in u. Note that if we have reached v[u] in the algorithm means that there exists and path from p to u, such that we can look through each triangle of the path if we look from A to B. Thus we can also look though the path and through u if we look from A to B (since we are looking through a path of adjacent triangles).
• we are reaching v[q] (perform the check above also for v[q]) iff we can look from A to B

We have only to perform at most one segment-triangle intersection-test for each triangle in T - thus O(n) Also the number of steps of the search is O(n) since G is a tree. In most cases the number of steps needed should be much smaller since we are using a breath first search approach and stop the search in each direction very early (no sight, solution found).

Note You can even speed up step 2 by using an A*-ansatz for the search. (http://en.wikipedia.org/wiki/A*_search_algorithm)

References I used a script of an algorithmic geometrie lecture of the FU Berlin to distillate the algorithm (written in german). (the one I presented here is modified since you are only want to perform a sight-check between two point. The lecture present a method to find a sub-polygon which can be seen from a given point) http://www.inf.fu-berlin.de/lehre/SS09/AG/skript/s13.pdf, (http://www.inf.fu-berlin.de/lehre/SS09/AG/skript.html)

Answer 2

How to distinguish these two?

Distinguishing between these two is a common need in triangulation algorithms, for both of those are vertex-to-vertex diagonals, one internal the other external. Typically one writes a primitive inside predicate, something like this. Let (a,b,c) be three consecutive vertices of the polygon in ccw order, and the potential diagonal bx. Then bx is internal iff the area of triangle abx is >= 0, and at the same time the area of triangle xbc is >= 0. Here one uses signed area computations. Of course treating the = case is delicate in floating point.

I use this method in my book, Comptutational Geometry in C.