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.

Lontson

I'm not sure your current method works in all cases, or maybe I don't understand the problem. Couldn't a line segment just clip a corner of a tile with an arbitrarily small portion of the line in the tile? – Cene

Hi Patricia: You are quite right, this is a problem that the current solution does not solve. For my algorithm I made that compromise since speed is more important than absolute accuracy. I should put your remark in the text as well – Lontson

This looks remarkably like the Bresenham line drawing algorithm from CS 101. – Janeljanela

Thank's for all the answers: I should really fresh up my algorithms basics :-P – Lontson

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.

Billon

Answer 2

Test the gradient of the line, against the tile diagonal with the same gradient sign. If it is steeper than a tile diagonal, exchange x and y coordinates in what follows.

If the gradient is shallower than the tile diagonal, the line touches or crosses a given tile, and the tile does not contain an end point, at least one of its intersections with the edges of the tile must be on an x boundary of the tile.

For each line end, collect the tile containing or tiles touching the end point.

For each x coordinate that is a tile edge between the two end point x coordinates, calculate the line's y coordinate. Collect the tiles touching that point.

I think this can all be done with at most a couple of divisions to do the gradient check. The main process is all multiplication, addition, and comparisons.

Cene

Answer 3

Given the line segment's end points, you can easily compute the equation of the line, y = mx + b. And given the length of the segment, you can compute the parametric form:

x = x0 + ft
y = y0 + gt

Given either of those equations, you can calculate the y coordinate for any given x coordinate on the line. So ...

Starting at the first end point of the line, you know that the cell containing that point is in the set. You know the x coordinates for each cell, so you can quickly determine the y coordinate at which your line segment crosses the cell boundary. If that y coordinate is above the cell's top y coordinate, then the line segment intersects the cell above the starting cell. (Substitute "below" if the line's slope is "down.)

If you repeat that test for each cell boundary along the x axis, you will get the list of all cells that the segment crosses.

Topsoil