Line Drawing Using Bresenham Algorithm

Question

Indicate which raster locations would be chosen by Bersenham’s algorithm when scan converting a line from screen co-ordinates (1,1) to (8,5).

First the straight values (initial values) must be found

                          dx=x2-x1                      8-1=  7
                          dy= y2-y1                     5-1=  4

Therefore d=2dy-dx 2*4-7= 1 initial values

The answers are found to be.

Now the question is how did we got the "d" values. With step by step explanation.

Answer 1

If you implement Wiki's integer arithmetic algorithm e.g. with Pascal and replace the plot by writeln

procedure plotLine(x0,y0, x1,y1: integer);
var
  dx,dy,D,x,y: integer;
begin
  dx:=x1-x0;
  dy:=y1-y0;

  D := 2*dy - dx;
  x := x0;
  y := y0;
  writeln(x:5, y:5, D: 5);

  for x := x0+1 to x1 do begin
    if D > 0 then begin
      y := y+1;
      D := D + (2*dy-2*dx);
      writeln(x:5, y:5, D: 5);
    end
    else begin
      D := D + (2*dy);
      writeln(x:5, y:5, D: 5);
    end;
  end;
end;

You get the output

1    1    1
2    2   -5
3    2    3
4    3   -3
5    3    5
6    4   -1
7    4    7
8    5    1

Answer 2

Here's my implementation of Bersenham’s Algorithm in Python.

# bresenham's line drawing algorithm

x0, y0 = map(int, input("Enter the start points: ").split())
x1, y1 = map(int, input("Enter the final points: ").split())

dx = x1 - x0
dy = y1 - y0

x = x0
y = y0

m = dy / dx

print(f"\nSlope = {m}\n")
print("x\t\ty\t\td")
print("-\t\t-\t\t-")
print(f"{x}\t\t{y}\t\t{dd}")

if 0 < m < 1:

    dd = 2*dy - dx

    for x in range(x0+1, x1+1):
        if dd >= 0:
            y += 1
            dd += 2 * (dy - dx)
        else:
            dd += 2 * dy
        print(f"{x}\t\t{y}\t\t{dd}")

elif m > 1:

    dd = 2*dx - dy

    for y in range(y0+1, y1+1):
        if dd >= 0:
            x += 1
            dd += 2 * (dx - dy)
        else:
            dd += 2 * dx
        print(f"{x}\t\t{y}\t\t{dd}")

If you unroll the loop you'll see exactly how dd or decision parameter gets updated at each step.