Line segment with grid intersection test ?
nospam at hotmail.com
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
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 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
> 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
> > 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 physik.rwth-aachen.de)
> Even if all the snow were burnt, ashes would remain.
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