Elegant/Clean (special case) Straight-line Grid Traversal Algorithm?

Question

I'm dusting off an old project of mine. One of the things it had to do was -- given a Cartesian grid system, and two squares on the grid, find a list of all squares that a line joining the center of those two squares would pass through.

The special case here is that all start and end points are confined to the exact center of squares/cells.

Here are some examples -- with pairs of sample starting and ending points. The shaded squares are the ones that should be returned by the respective function call

removed dead ImageShack link - example

The starting and end points are referred to by the squares they are in. In the above picture, assuming that the bottom left is [1,1], the line on the bottom right would be identified as [6,2] to [9,5].

That is, from the (center of the) square on the sixth column from the left, on the second row from the bottom to the (center of the) square on the ninth column from the left, on the fifth row from the bottom

Which really doesn't seem that complicated. However, I somehow seemed to have found some complex algorithm online and implemented it.

I do recall that it was very, very fast. Like, optimized-for-a-hundreds-or-thousands-of-times-per-frames fast.

Basically, it jumped from border to border of the squares, along the line (the points where the line crosses the grid lines). It knew where the next crossing point was by seeing which crossing point was closer -- a horizontal one or a vertical one -- and moved to that next one.

Which is sort of okay in concept, but the actual implementation turned out to be pretty not-so-pretty, and I'm afraid that the level of optimization might be way too high for what I practically need (I'm calling this traversal algorithm maybe five or six times a minute).

Is there a simple, easy-to-understand, transparent straight-line grid traversal algorithm?

In programmatic terms:

def traverse(start_point,end_point)   # returns a list of all squares that this line would pass through end 

where the given coordinates identify the squares themselves.

Some examples:

traverse([0,0],[0,4]) # => [0,0], [0,1], [0,2], [0,3], [0,4] traverse([0,0],[3,2]) # => [0,0], [0,1], [1,1], [2,1], [2,2], [3,2] traverse([0,0],[3,3]) # => [0,0], [1,1], [2,2], [3,3] 

Note that lines that move directly through corners should not include squares on the "wing" of the line.

(Good ol' Bresenham's might work here, but it's a bit backwards from what I want. As far as I know, in order to use it, I'd basically have to apply it to the line and then scan every single square on the grid for true or false. Infeasible -- or at least inelegant -- for large grids)

(I am re-looking into Bresenham, and Bresenham-based algorithms, due to a misunderstanding of mine)

---

For clarification, one possible application of this would be, if I was storing all of my objects in a game inside zones (a grid), and I have a ray, and want to see which objects the ray touches. Using this algorithm, I could test the ray to only the objects that are within the given zones, instead of every object on the map.

The actual use of this in my application is that every tile has an effect associated with it, and an object moves through a given line segment every turn. At every turn, it is necessary to check to see which squares the object has traversed through, and therefore, which effects to apply to the object.

Note that, at this point, the current implementation I have does work. This question is mostly for curiosity's purpose. There has to be a simpler way...somehow...for such a simple problem.

---

What am I looking for exactly? Something conceptually/neat and clean. Also, I've realized that due to what I am exactly specifying, all start and end points are always going to be in the center of squares/cells; so perhaps something that takes advantage of that would be neat as well.

Answer 1

What you want is a particular case of a supercover, which is all of the pixels intersected by a geometric object. The object may be a line or a triangle, and there are generalizations to higher dimensions.

Anyways, here is one implementation for line segments. That page also compares the supercover with the result of Bresenham's algorithm - they are different.
_{(source: free.fr)}

I don't know whether you consider the algorithm there as elegant/clean, but it certainly seems simple enough to adapt the code and move on to other parts of your project.

By the way, your question implies that Bresenham's algorithm is not efficient for large grids. That's not true - it generates only the pixels on the line. You don't have to do a true/false test for every pixel on the grid.

Update 1: I noticed that in the picture there are two 'extra' blue squares that I believe the line does not pass through. One of them is adjacent to the 'h' in 'This algorithm'. I don't know if that reflects an error in the algorithm or the diagram (but see @kikito's comment below).

In general, the 'hard' cases are probably when the line passes exactly through a grid point. I speculate that if you are using floating point that float point error may mess you up in these cases. In other words, algorithms should probably stick to integer arithmetic.

Update 2: Another implementation.

Answer 2

A paper on this topic can be found here. This is in regards to raytracing, but that seems quite relevant to what you are after anyway, and I assume you will be able to work with it a bit.

There is also another paper here, dealing with something similar.

Both of these papers are linked in part 4 of Jakko Bikker's excellent tutorials on raytracing (which also include his source code, so you can browse / examine his implementations).