Line segment with grid intersection test ?

Skybuck Flying nospam at
Wed Jun 2 17:36:57 PDT 2004


Problem description:

A line segment intersects with a grid. The cells in the grid have the same

The objective is to mark all cells that are intersected by the line segment.

It seems like a general problem which could be solved by a general

I am looking for a description of an algorithm that will work in 2D.

A very simple solution could be to just do a line segment with rectangle
intersection test for every cell.

Though this doesn't seem efficient.

A more efficient way could be to move along the line segment from cell
boundary to cell boundary.

Any hints, links, etc are appreciated ;)


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