Draw a line using the Midpoint algorithm where the starting point is (32, 35) and the ending point is (41, 41).
Theory: The Mid-Point line plotting algorithm was introduced by “Pitway and Van Aken.” It is an incremental line drawing algorithm. In this algorithm, we perform incremental calculations. The calculations are based on the previous step to find the value of the next point. We perform the same process for each step.
The Midpoint Line Algorithm is designed for efficiency and simplicity when drawing lines on a pixel grid. It avoids the need for floating-point calculations or trigonometric functions, making it suitable for real-time graphics.
The decision parameter P is crucial in determining whether the next pixel should move horizontally (x) or diagonally (x and y) based on the relative positions of the endpoint and the line. When P is positive or zero, it means the midpoint is above or on the actual line, so we move diagonally. When P is negative, it means the midpoint is below the actual line, so we move horizontally.
By following this process, the algorithm efficiently plots the points that best approximate the line between the given start and end points, making it a preferred choice for line drawing in computer graphics.
Input:
• Starting point (x1, y1) and ending point (x2, y2) of the line.
Output:
• A set of pixel coordinates (x, y) approximating the line between (x1, y1) and (x2, y2).
Algorithm:
1. Initialize variables:
• x to x1, y to y1.
• Calculate differences: dx = x2 - x1, dy = y2 - y1.
• Calculate the decision parameter P: P = 2 * dy - dx.
2. Plot the starting point (x, y).
3. Loop:
• While x < x2, update the pixel coordinates and P:
• If P < 0, increment x by 1, update P.
• If P ≥ 0, increment both x and y by 1, update P.
4. Continue looping until x ≥ x2.
5. The line is complete.
The algorithm efficiently draws lines by considering the relationship between the decision parameter P and the line's slope, avoiding complex calculations like floating-point or trigonometric operations.
import matplotlib.pyplot as plt
print("Enter the value of x1")
x1 = int(input())
print("Enter the value of x2")
x2 = int(input())
print("Enter the value of y1")
y1 = int(input())
print("Enter the value of y2")
y2 = int(input())
dx = x2 - x1
dy = y2 - y1
dy2 = dy * 2
dk = dy2 - dx
dd1 = dy - dx
dd2 = 2 * dd1
if abs(dx) > abs(dy):
steps = abs(dx)
else:
steps = abs(dy)
xincrement = dx / steps
yincrement = dy / steps
xcoordinate = []
ycoordinate = []
i = 0
while i < steps:
i += 1
if dk < 0:
x1 = x1 + 1
y1 = y1
dk = dk + (2 * dy)
print("x1: ", x1, "y1:", y1)
xcoordinate.append(x1)
ycoordinate.append(y1)
else:
x1 = x1 + 1
y1 = y1 + 1
dk = dk + dd2
print("x1: ", x1, "y1:", y1)
xcoordinate.append(x1)
ycoordinate.append(y1)
plt.plot(xcoordinate, ycoordinate)
plt.xlabel("X Axis")
plt.ylabel("Y Axis")
plt.title("Mid Point Algorithm")
plt.show()