Bresenham lines w/o diagonal movement

Question

Is there a modified Bresenham algorithm, where the step from one pixel to the next one isn't allowed to be diagonally, just horizontally or vertically? Or any other algorithm which does that? (PHP preferred)

Right:
0 0 0 1
0 0 1 1
0 1 1 0
1 1 0 0

Wrong:
0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 0

Answer 1

Should be a trivial modification - let's say you're in the quadrant I - i.e. going up and to the right. Instead of doing a diagonal, do an up... and then a right.

Instead of:

  for x from x0 to x1
             plot(x,y)
             error := error + deltaerr
             if error ≥ 0.5 then
                 y := y + 1
                 error := error - 1.0

Something like this:

for x from x0 to x1
         plot(x,y)
         error := error + deltaerr
         if error ≥ 0.5 then
             y := y + 1
             plot(x,y)
             error := error - 1.0

Answer 2

James' answer is pretty cool, but as he commented, it skews the line a bit. Another simple modification of the original Bresenham draws a line without diagonal steps that is closer to the "real" line.

This is an implementation of the original Bresenham algorithm:

public void line(int x0, int y0, int x1, int y1, int value) {
    int xDist =  Math.abs(x1 - x0);
    int yDist = -Math.abs(y1 - y0);
    int xStep = (x0 < x1 ? +1 : -1);
    int yStep = (y0 < y1 ? +1 : -1);
    int error = xDist + yDist;

    plot(x0, y0, value);

    while (x0 != x1 || y0 != y1) {
        if (2*error > yDist) {
            // horizontal step
            error += yDist;
            x0 += xStep;
        }

        if (2*error < xDist) {
            // vertical step
            error += xDist;
            y0 += yStep;
        }

        plot(x0, y0, value);
    }
}

The modification is simply to do either a horizontal or vertical step, not both, depending on whether the error indicator is nearer to a horizontal or vertical step:

public void lineNoDiag(int x0, int y0, int x1, int y1, int value) {
    int xDist =  Math.abs(x1 - x0);
    int yDist = -Math.abs(y1 - y0);
    int xStep = (x0 < x1 ? +1 : -1);
    int yStep = (y0 < y1 ? +1 : -1);
    int error = xDist + yDist;

    plot(x0, y0, value);

    while (x0 != x1 || y0 != y1) {
        if (2*error - yDist > xDist - 2*error) {
            // horizontal step
            error += yDist;
            x0 += xStep;
        } else {
            // vertical step
            error += xDist;
            y0 += yStep;
        }

        plot(x0, y0, value);
    }
}

This effectively chooses the kind of step that minimizes the error, thus resulting in a line that is closer to the real line.

The code is in Java, but it should be easily portable to PHP. I haven't thoroughly tested it, but it should work just as well as the original Bresenham. It may even be a tad faster.

Answer 3

I have found that Franz D's answer produces lines that do not closely match the original when close to the horizontal or vertical. While the function below is not perfect, I have found it produces nicer results.

Function BresenhamLineNew : Void( x0 : Int, y0 : Int, x1 : Int, y1 : Int )

    Local dx : Int = Abs( x1 - x0 )
    Local dy : Int = Abs( y1 - y0 )

    Local sx : Int = -1
    Local sy : Int = -1

    If x0 < x1 Then sx = 1
    If y0 < y1 Then sy = 1

    Local err : Int = dx - dy
    Local e2 : Int

    While True

        DrawRect x0, y0, 1, 1

        If x0 = x1 And y0 = y1 Then Exit

        e2 = 2 * err

        If dy > dx
            If e2 > -dy
                err = err - dy
                x0 = x0 + sx
            Elseif e2 < dx
                err = err + dx
                y0 = y0 + sy
            Endif
        Else
            If e2 < dx
                err = err + dx
                y0 = y0 + sy
            Elseif e2 > -dy
                err = err - dy
                x0 = x0 + sx
            Endif
        Endif

    Wend

End Function