Line segment with grid intersection test ?
nospam at hotmail.com
Wed Jun 2 17:36:57 PDT 2004
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 research.bell-labs.com with the line:
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.
More information about the Compgeom-announce