Midpoint Line Drawing Algorithm In Python

Last updated Sept. 14, 2022

Midpoint Line Drawing Algorithm

The Mid Point Line Drawing Algorithm tries to produce the points between the starting and ending coordinates given the starting and ending coordinates of a line. In the previous articles, we covered two of the line drawing algorithms.

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

The midpoint algorithm draws lines incrementally. Incremental calculations are used in this algorithm. To determine the value of the next point, computations are based on the previous step. For each stage, we follow the same procedure. The mid-point subdivision algorithm allows us to approximate a line between any two points with high accuracy. The line is constantly divided at its midpoints by the mid-point subdivision line drawing method.

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:

# Midpoint line generation Algorithm
import matplotlib.pyplot as plt
plt.title("Midpoint Line Algorithm")
plt.xlabel("X Axis")
plt.ylabel("Y Axis")

def midpoint(x1, y1, x2, y2):
    dx = x2 - x1
    dy = y2 - y1

    # Initialize the decision parameter
    d  = dy - (dx/2)
    x = x1
    y = y1

    print(f"x = {x}, y = {y}")
    # Initialize the plotting points
    xcoordinates = [x]
    ycoordinates = [y]

    while (x<x2):
        x = x + 1
        # East is Chosen
        if (d<0):
            d = d + dy

        # North East is Chosen
        else:
            d = d + (dy - dx)
            y = y + 1

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

if __name__=="__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: "))

    midpoint(x1, y1, x2, y2)

The instructions are further illustrated below: