Line segment with grid intersection test ?

David Strip david.strip at
Wed Jun 2 17:41:49 PDT 2004

Skybuck Flying wrote:

> Hi,
> Problem description:
> A line segment intersects with a grid. The cells in the grid have the same
> dimensions.
> The objective is to mark all cells that are intersected by the line segment.

Look at Bresemham's line drawing algorithm. It does almost what you want. The
Bresemham algorithm would identify the vertices you come closest to. You can
change the marking step to utilized a slightly different decision that will mark
the appropriate grid cells. (At first I thought you might be able to take a dual
grid and use the straight bresenham algorithm on a line plotted in the dual
space, but that doesn't work).

The compgeom mailing lists: see
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list