Algorithm for drawing a 4-connected line

Question

I'm looking for an algorithm (coded in Java would be nice, but anything clear enough to translate to Java is fine) to draw a 4-connected line. It seems that Bresenham's algorithm is the most widely used, but all the understandable implementations I've found are 8-connected. OpenCV's cvline function apparently has a 4-connected version, but the source code is, to me, as a mediocre and nearly C-illiterate programmer, impenetrable. Various other searches have turned up nothing.

Thanks for any help anyone can provide.

Answer 1

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

Answer 2

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;
        }
    }
}

Answer 3

The digital straight line that connects fractional coordinates might be different than that connecting integer coordinates. For an example, consider the image below which shows the 4-connected digital straight lines between the points (1, 1) - (6, 3), (1, 0.6) - (6, 2.6), and (1, 1.4) - (6, 3.4).

example image

While all start points and end points lie on the pixels (1, 1) and (6, 4) the digital straigt 4-connected lines are different.

The code below computes the 4-connected digital straight line between a fractional start and end point. Actually, the code works also for n dimensions and computes the 2n-connected digital straight line.

import numpy as np

def points_on_line(start, end):

    idx = np.round(np.array(start)).astype(int)
    end_idx = np.round(np.array(end)).astype(int)
    points = [idx]

    if np.all(idx == end_idx):
        return points

    diff = np.array(end, dtype=float) - np.array(start, dtype=float)
    direction = (diff / np.abs(diff)).astype(int)
    coord = np.array(start, dtype=float)

    while np.any(idx != end_idx):
        # compute how far we need to go to reach the side of the pixel at idx
        t = (idx + direction / 2 - coord) / diff
        i = np.argmin(t)
        coord += t[i] * diff
        idx = idx.copy()
        idx[i] += direction[i]
        points.append(idx)

    return points