Line segment with grid intersection test ?

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

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