Line segment with grid intersection test ?

[Skybuck Flying]

Actually.

I am looking for a "geometry" solution.

Not a graphical solution.

Graphical solutions can get away with some inprecision.

I need the result to be exact/precise so that it can be used for further
calculations etc.

Usenet does not have a geometry newsgroup so I posted it to graphics since
it seems the next best thing and game development.

I also CC-ed the computional mailing list.

Usenet could use a computational geometry group ! ;)

Skybuck.

"Hans-Bernhard Broeker" <broeker at physik.rwth-aachen.de> wrote in message
news:2i67itFiutgnU1 at uni-berlin.de...
> [F'up2 reduced to a single group --- should have been done by OP
> already.]
>
> In comp.graphics.algorithms Skybuck Flying <nospam at hotmail.com> wrote:
>
> > 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.
>
> You're right, and it is.  Such algorithms go by the name "scan
> conversion", and include classics like Bresenham's integer-only scan
> conversion.  The vital clue is that your regular grid of cells is
> essentially equivalent to a pixelated screen, so what you're doing is
> equivalent to drawing a line segment on such a device.
>
> The only major difference between your task and plain vanilla line
> segment scan conversion is that you seem to require end points at
> arbitrary positions inside a cell/pixel.  I.e. you're looking for a
> sub-pixel resolution in scan conversion.
>
> The best choice really is to walk along the line and determine for
> each cell you're in, whether the edge leaves it through a horizontal
> or vertical edge, or exactly at a corner, or ends inside that cell.
> The test to carry out is whether the eligible corner is to the right
> or to the left of the line.
>
> -- 
> Hans-Bernhard Broeker (broeker at physik.rwth-aachen.de)
> Even if all the snow were burnt, ashes would remain.




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