Digital field of view implementation

Unlikely as it seems, there are no artifacts here. You can check out the 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.

To check whether a lower segment is visible, given that we've calculated the convex hull of obstructions (I really need to put some illustrations in...), we can try pretending that the corresponding upper segment was an obstruction. If we then realize that the convex hulls intersect, this tells us that our lower segment wasn't visible anyways. Unfortunately for this method, pretending something's an obstruction when it's not could make us use more than O(N) time in the end. We have to be trickier!

The trick is to also keep in memory the two unobstructed lines from the source segment with greatest and least slope. Let's go back to the lower segment. If the top point of the lower segment is below the line of least slope (which necessarily starts from the source segment, is tangent to the upper convex hull, then tangent to the lower convex hull), then pretending the upper segment is an obstruction implies that the updated convex hulls would intersect, so in this case the lower segment is invisible. If the top point of the lower segment is above the line of least slope, then the part of the lower segment just above that line is visible. So this tells us whether the lower segment is visible (one subtlety - we need to check that at least part of the visible region is still within the parallelogram, or we will come to grief).

To update the lines of greatest and least slope, let's assume that the lower segment is an obstruction. If it is invisible, it doesn't affect anything, so let's also assume it's visible. If the line of greatest slope changes here, then the convex hulls intersect, so we'll quit anyways. The line of least slope changes, though - the point of tangency to the lower convex hull moves to the top of the lower segment, and the point of tangency to the upper convex hull has to move to the right.

And that's all there is to it!

If you were paying close attention, you'll notice that if the actual size of the grid is M*M, and we tell the algorithm it's N*N, then the running time is O(NM).