Line segment with grid intersection test ?

[David Strip]

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
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.