ligwww.epfl.ch/~srik/thesis (choose appendix_a.ps) - another algorithm (and a generalized one in 3D also) for doing the same thing. Thanks, Srikanth (address changed, but where is it now?)

Bresenham's algorithm

Linear interpolation algorithm using fixed points (allowing generally a more efficient implementation) - (thanks Alex J. Champandard for rectification)

Algorithm for arbitrary points

Grid Traversal algorithm

I suppose you already know the Bresenham's algorithm. If not, see the links above. To simplify the discussion, suppose we are in the first octant. Suppose the point is in square A. The next point (using Bresenham's algorithm) will be B or C, like in our algorithm. However, while Bresenham's checks B and C, our algorithm has to check the points B, C, and D.

If the Bresenham's algorithm does not change the y-coordinate
(next point is C), this means that D will not be drawn, so we pass
directly to C, and we go to the beginning again.

The other case is when Bresenham's algorithm changes the
coordinate, i.e. when the next point is B. In this case, both
C and D have also to be checked. As seen in the figure, we
can know if a point is drawn or not by the following relation:

// three cases (octant
== right->right-top for directions below):

if (error + errorprev
< ddx) // bottom square also

POINT
(y-ystep, x);

else if (error +
errorprev > ddx) // left square also

POINT (y,
x-xstep);

else{ // corner:
bottom and left squares also

POINT
(y-ystep, x);

POINT (y,
x-xstep);

}

error is the current error (in point B), while errorprev is the
previous error (in point A). Remember that the error is the
"distance" (non-normalized) from the ideal point to the grid line
below the ideal point.

// use Bresenham-like algorithm to print a line from (y1,x1) to (y2,x2)

// The difference with Bresenham is that ALL the points of the line are

// printed, not only one per x coordinate.

// Principles of the Bresenham's algorithm (heavily modified) were taken from:

// http://www.intranet.ca/~sshah/waste/art7.html

void useVisionLine (int y1, int x1, int y2, int x2)

{

int i; // loop counter

int ystep, xstep; // the step on y and x axis

int error; // the error accumulated during the increment

int y = y1, x = x1; // the line points

int ddy, ddx; // compulsory variables: the double values of dy and dx

int dx = x2 - x1;

int dy = y2 - y1;

POINT (y1, x1); // first point

// NB the last point can't be here, because of its previous point (which has to be verified)

if (dy < 0){

ystep = -1;

dy = -dy;

}else

ystep = 1;

if (dx < 0){

xstep = -1;

dx = -dx;

}else

xstep = 1;

ddy = 2 * dy; // work with double values for full precision

ddx = 2 * dx;

if (ddx >= ddy){ // first octant (0 <= slope <= 1)

// compulsory initialization (even for errorprev, needed when dx==dy)

for (i=0 ; i < dx ; i++){ // do not use the first point (already done)

x += xstep;

error += ddy;

if (error > ddx){ // increment y if AFTER the middle ( > )

y += ystep;

error -= ddx;

}

POINT (y, x);

}

}else{ // the same as above

for (i=0 ; i < dy ; i++){

y += ystep;

error += ddx;

if (error > ddy){

x += xstep;

error -= ddy;

}

POINT (y, x);

}

}

// assert ((y == y2) && (x == x2)); // the last point (y2,x2) has to be the same with the last point of the algorithm

}

Here we have supposed that if the line passes through a corner,
the both squares are drawn. If you want to remove this, you
can simply remove the *else* part dealing with the corner.

Note: The line is symmetric, i.e. a line from x0,y0 to x1,y1 is the same as a line from x1,y1 to x0,y0.

Written by Eugen Dedu

Last modified: June 05, 2001