Algorithm for drawing a 4-connected line

The following is a Bresenham-like algorithm that draws 4-connected lines. The code is in Python but I suppose can be understood easily even if you don't know the language.

def line(x0, y0, x1, y1, color):
    dx = abs(x1 - x0)    # distance to travel in X
    dy = abs(y1 - y0)    # distance to travel in Y

    if x0 < x1:
        ix = 1           # x will increase at each step
    else:
        ix = -1          # x will decrease at each step

    if y0 < y1:
        iy = 1           # y will increase at each step
    else:
        iy = -1          # y will decrease at each step

    e = 0                # Current error 

    for i in range(dx + dy):
        draw_pixel(x0, y0, color)
        e1 = e + dy
        e2 = e - dx
        if abs(e1) < abs(e2):
            # Error will be smaller moving on X
            x0 += ix
            e = e1
        else:
            # Error will be smaller moving on Y
            y0 += iy
            e = e2

The idea is that to draw a line you should increment X and Y with a ratio that matches DX/DY of the theoretic line. To do this I start with an error variable e initialized to 0 (we're on the line) and at each step I check if the error is lower if I only increment X or if I only increment Y (Bresenham check is to choose between changing only X or both X and Y).

The naive version for doing this check would be adding 1/dy or 1/dx, but multiplying all increments by dx*dy allows using only integer values and that improves both speed and accuracy and also avoids the need of special cases for dx==0 or dy==0 thus simplifying the logic. Of course since we're looking for a proportion error, using a scaled increment doesn't affect the result.

Whatever is the line quadrant the two possibilities for the increment will always have a different sign effect on the error... so my arbitrary choice was to increment the error for an X step and decrement the error for an Y step.

The ix and iy variables are the real directions needed for the line (either +1 or -1) depending on whether the initial coordinates are lower or higher than the final coordinates.

The number of pixels to draw in a 4-connected line is obviously dx+dy, so I just do a loop for that many times to draw the line instead of checking if I got to the end point. Note that this algorithm draws all pixels except the last one; if you want also that final pixel then an extra draw_pixel call should be added after the end of the loop.

An example result of the above implementation can be seen in the following picture

enter image description here


For the Python-illiterate, here is a C version of 6502's code:

void drawLine(int x0, int y0, int x1, int y1) {
    int dx = abs(x1 - x0);
    int dy = abs(y1 - y0);
    int sgnX = x0 < x1 ? 1 : -1;
    int sgnY = y0 < y1 ? 1 : -1;
    int e = 0;
    for (int i=0; i < dx+dy; i++) {
        drawPixel(x0, y0);
        int e1 = e + dy;
        int e2 = e - dx;
        if (abs(e1) < abs(e2)) {
            x0 += sgnX;
            e = e1;
        } else {
            y0 += sgnY;
            e = e2;
        }
    }
}