Digital field of view implementation

Trust me, there are no artifacts here. If you don't believe me, check out my demo program at http://reflexivelos.googlecode.com/svn/trunk/los2.cpp. It has an implementation of the not-so-dumb algorithm and the clever algorithm, and they produce identical results.

Dumb algorithm

The algorithm is simple: generate each digital line in turn, and walk along each one until you hit an obstruction.

Obviously, this is extremely slow - running time is O(N⁴).

A little bit smarter

Notice that if we fix p and q, there are only two possible heights for the line at any particular x coordinate. If both of those squares are blocked, no value of s will work, and if both are empty, they don't impose any extra conditions on s. If the bottom one is blocked, then smaller values of s will be excluded, and similarly for the top. So at each x coordinate, there will be an interval of possible values for s, which can be maintained easily.

This does a little better - running time is O(N³). But best possible is O(N²)...

Between two points

Let's take a break from field of view algorithms... with a line of sight algorithm!

At this point, we need a little bit of geometric intuition. As far as digital lines in the first octant are concerned, all of the action happens at integral x coordinates - each obstruction can be thought of as a horizontal line segment of length one, as can the source and destination. We want to know whether there is a line connecting the source line segment to the destination line segment that doesn't cross any of the obstructing segments. Thus, we can restrict attention to the parallelogram formed by the source and destination segments. Just like the previous algorithm, for each value of x there are only two relevant segments intersecting the parallelogram, each of which may or may not be obstructing.

Thus, obstructions can be classified as upper obstructions and lower obstructions, depending on which edge of the parallelogram they intersect. We want to know whether there is a line going underneath all of the upper obstructions and above all of the lower obstructions, that is, whether the convex hull of the upper obstructions intersects the convex hull of the lower obstructions. This is easy to check, though - we can find the convex hulls of each set in O(N) time, and then check this condition at every integral x coordinate from 1 to n.

A Beam Casting idea

In the previous algorithm, we could have been a little bit more ambitious. Instead of simply checking if we can see the destination, why don't we check if we can see the intermediate segments (or at least, their intersections with the parallelogram we're restricting ourselves to)?

If we can do this, then we can solve the field of view problem in O(N²) time! We simply call the previous algorithm with destinations (n, 0), (n, 1), ..., (n, n). This works because the parallelograms formed from the source and each destination completely cover the first octant, so if an intermediate segment is visible, a visible part of it will be contained in one particular parallelogram, and the segment will be marked visible while running the previous algorithm with the corresponding destination.

If only it was that easy...