What is the fastest way to determine all cells in a regular 2d grid that are touched by a line segment

Question

I want to find all grid tiles that touch or contain parts of a given finite line segment. The grid is a 2d regular grid, thus I can deduce any tile's center from a tile position (row,colum) and vice versa I can calculate a tile position from a given floating point coordinate with two fast integer divisions. The tiles are quadratic e.g. 0.25x0.25 with 0.25 defined as the tile width. Now I need to determine all tiles that are touched by a given line segment (two 2d points given in floats define a line segment). My current approach is to split the segment into equidistant points with a distance half the tile-width (greetings to shannon). Than I collect all tiles that contain the given points and remove duplicate tiles. Since this operation is the most performance critical part of my program I was wondering whether there is a faster approach to calculate the respective tiles.

Edit: As Patricia noted my current approach does not result in a complete tile set since a tile that is only touched to a very small fraction by the line would not be included. This is acceptable for me since in my case speed is more important than accuracy, but should be noted none the less.

To make it clearer: I want all red tiles in the image but I can spare e.g. the rose ones if I gain speed for that.

Answer 1

Your problem basically comes down to drawing a line segment on a raster image.

If you can spare the pink tiles, use the Bresenham's algorithm. Otherwise, use a similar technique as is used to draw antialiased lines:

You start at the tile which contains one end of the segment and put it to the queue. Then follow with a regular BFS algorithm, putting only tiles which intersect with the segment to the queue:

In one iteration take one tile from one end of the queue, this is your next found intersecting tile. Then find all its neighbors, and put those which intersect with the segment (it's enough to test intersection with a line in this case) to the other end of the queue. The neighbors must be chosen according to the direction of the line. If it goes down-right, use the down, right and down-right tiles as neighbors, if it goes up, use only up neighbors, and so on.

You end when you reach the tile which contains the other end of the segment.