Line segment with grid intersection test ?

Skybuck Flying nospam at
Wed Jun 2 18:26:41 PDT 2004


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 ! ;)


"Hans-Bernhard Broeker" <broeker at> wrote in message
news:2i67itFiutgnU1 at
> [F'up2 reduced to a single group --- should have been done by OP
> already.]
> In Skybuck Flying <nospam at> wrote:
> > A line segment intersects with a grid. The cells in the grid have the
> > dimensions.
> > The objective is to mark all cells that are intersected by the line
> > 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
> Even if all the snow were burnt, ashes would remain.

The compgeom mailing lists: see
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list