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

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?

• Google BSP trees (not the Quake level format). They're exactly what you need for this kind of problem. – 3Dave Jul 8 '12 at 17:21
• @DavidLively Can you elaborate? I looked it up but failed to see the correlation. From what I read, a BSP tree stores an organizes all the polygons in a scene according to a certain requirement, but in this case I only have one polygon. – David Gouveia Jul 8 '12 at 21:09
• a 2D tree splits based on edges. By clipping a line segment that connects your source and target points against the tree, you can see if it lies entirely inside or outside of the polygons that were used to generate the tree, or of it crosses a boundary in which case there is no direct line of sight. – 3Dave Jul 8 '12 at 23:15

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)

• Thank you a lot for your answer! It makes sense and seems like a proper solution. I'll hold back on implementing it for now though because since my goal is to get rid of the current pre-processing step where I inflate the polygon, it would not make sense to replace it with an even more complicated step of triangulation and graph creation. I'll try to work on the line segment intersection solution first, and leave this as a last resort. – David Gouveia Jul 8 '12 at 21:04
• Also, I'm using the line-of-sight test as part of implementing pathfinding on a visibility graph. But ironically, the requirements for this algorithm are essentially having a triangulated navigation mesh, and performing a sort of pathfinding on it, which is what I initially had and dropped in favor of the visibility graph. Surely there must be a way to create a visibility graph for a polygon, without having to generate a navigation mesh, in which case I'd just perform the pathfinding directly on the navigation mesh. – David Gouveia Jul 8 '12 at 21:16
• I'm marking this as a proper solution to the general problem, although it was not practical in my situation. Personally I think I've managed to solve the problem by sticking with the line segment intersection tests, and adding a few epsilons and special cases checks here and there. I'm currently testing the solution. – David Gouveia Jul 10 '12 at 20:53

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.

• Maybe it's because I'm really tired at the moment, but although the two examples I gave had the three vertices being consecutive, that is not necessarily the case. I'll have to think about this tomorrow with a fresh mind, but I'm not sure I understood how to apply the idea. – David Gouveia Jul 7 '12 at 4:35
• Your examples 1 and 9 (and 6) start on a vertex, and so my analysis applies to those (and only those). I was only addressing segments that have one endpoint at a vertex. – Joseph O'Rourke Jul 8 '12 at 2:11
• Okay, I was actually misunderstanding the part about the consecutive vertices, but I got it now. I'll try to implement it today. But I'm still thinking about the overall algorithm, and what order should I handle things. For example, first handle adjacent vertices as a special case so that they're not treated as diagonals, then diagonals as you said, then everything else. And about the line-segment intersection test, I should probably detect if they're collinear first, and treat collinear segments as if they're not intersecting. – David Gouveia Jul 8 '12 at 13:32
• I implemented this, but ran into some trouble. Here's the relevant code and a picture explaining the problem. Basically it works for many cases, but is failing for a few. – David Gouveia Jul 8 '12 at 23:26