# Line segment with grid intersection test ?

Steve Zoraster Szoraster at lgc.com
Thu Jun 3 13:04:31 PDT 2004

```Normalize everything so that the origin of the
grid is (0,0).  And cell size 1x1.

Divide the line segment into subsegments of length
say 3/4.  For each such subsegment determine whether
one end x coordinate is (n).kkkk and the other, for
example (n+1).kkkk.  That means a grid column crossing
and even tells you which column.  Compute and store
exact column intersection point. That tells you which row.
Do same for y-coordinate. Continue until run out of
all segments.....

Steven Zoraster

Normalize everything so that the origin of the
grid is (0,0).  And cell size 1x1.

Divide the line segment into subsegments of length
say 3/4.  For each such segment determine whether
one end x coordinate is (n).kkkk and the other, for
example (n+1).kkkk.  That means a grid column crossing
and even tells you which column.  Compute and store
exact intersection point. That tells you which row.
Do same for y-coordinate. Continue until run out of
all segments.....

Steven Zoraster

Normalize everything so that the origin of the
grid is (0,0).  And cell size 1x1.

Divide the line segment into subsegments of length
say 3/4.  For each such segment determine whether
one end x coordinate is (n).kkkk and the other, for
example (n+1).kkkk.  That means a grid column crossing
and even tells you which column.  Compute and store
exact intersection point. That tells you which row.
Do same for y-coordinate. Continue until run out of
all segments.....

Steven Zoraster

> -----Original Message-----
> From: Skybuck Flying [mailto:nospam at hotmail.com]
> Sent: Wednesday, June 02, 2004 9:37 AM
> To: compgeom-discuss at research.bell-labs.com
> Subject: Line segment with grid intersection test ?
>
>
> 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
> 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.
> >

-------------
The compgeom mailing lists: see