Bresenham Line Drawing Algorithm Implemented In Python

Last updated Sept. 13, 2022

Bresenham Line Drawing Algorithm Implemented in Python

In the previous article, we took a look at one of the line drawing algorithms in computer graphics which was the Digital Differential Analyzer. In this article, however, we will take a look at another line drawing algorithm that is an improvement on the DDA. 

1. Digital Differential Analyzer
2. Bresenham Line Drawing Algorithm
3. Midpoint Line Drawing Algorithm

Bresenham Line Algorithm uses only integer numbers and integer arithmetic to determine all intermediate points throughout the space between start and end points. Bresenham Line Algorithm is an optimistic and incremental scan conversion Line Drawing Algorithm. The algorithm calculates all intermediate points over the interval between the start and endpoints. The algorithm is implemented entirely with integer numbers and integer arithmetic. It only uses addition and subtraction and avoids heavy operations like multiplication and division. Heavy operations like multiplication and division are avoided in favor of addition and subtraction only.

To implement the algorithm using python we'll need a python package called matplotlib for visualization of the plotted points. The package can be installed via:

pip install matplotlib

The following is the code for line generation:

import matplotlib.pyplot as plt
plt.title("Bresenham Algorithm")
plt.xlabel("X Axis")
plt.ylabel("Y Axis")

def bres(x1,y1,x2,y2):
    x,y = x1,y1
    dx = abs(x2 - x1)
    dy = abs(y2 -y1)
    gradient = dy/float(dx)

    if gradient > 1:
        dx, dy = dy, dx
        x, y = y, x
        x1, y1 = y1, x1
        x2, y2 = y2, x2

    p = 2*dy - dx
    print(f"x = {x}, y = {y}")
    # Initialize the plotting points
    xcoordinates = [x]
    ycoordinates = [y]

    for k in range(2, dx + 2):
        if p > 0:
            y = y + 1 if y < y2 else y - 1
            p = p + 2 * (dy - dx)
        else:
            p = p + 2 * dy

        x = x + 1 if x < x2 else x - 1

        print(f"x = {x}, y = {y}")
        xcoordinates.append(x)
        ycoordinates.append(y)

    plt.plot(xcoordinates, ycoordinates)
    plt.show()


def main():
    x1 = int(input("Enter the Starting point of x: "))
    y1 = int(input("Enter the Starting point of y: "))
    x2 = int(input("Enter the end point of x: "))
    y2 = int(input("Enter the end point of y: "))

    bres(x1, y1, x2, y2)

if __name__ == "__main__":
    main()

The instructions are further illustrated below: