Line segment with grid intersection test ?

[Skybuck Flying]

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.

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

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 ;)

Bye,
  Skybuck.




-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.