Mid Point Line Drawing Algorithm

A Midpoint line drawing algorithm is a computer graphics algorithm used to draw a straight line between two points in a 2D space. It is similar to the Bresenham algorithm in that it also uses incremental calculations to plot the pixels that make up the line.

The algorithm works by determining a midpoint between the start and end points of the line and then using this midpoint to decide which pixel to plot next. This decision is based on the sign of the difference between the actual and ideal line slopes.

The algorithm starts by calculating the slope of the line and determining the first pixel to plot. Then, it iteratively computes the next pixel to plot by calculating the midpoint between the current pixel and the endpoint of the line. The algorithm then checks which of two possible pixels is closer to the ideal line and plots that pixel.

The midpoint line drawing algorithm is a popular alternative to the Bresenham algorithm, and it produces smooth and accurate lines. However, it requires more floating-point operations than the Bresenham algorithm, making it less efficient.

Rules of Mid Point Line Drawing Algorithm

ΔX = Xn – X0
ΔY =Yn – Y0

Dinitial = 2ΔY – ΔX
ΔD = 2(ΔY – ΔX)

Repeat until endpoint reached
if Dinitial < 0 then
Xk+1 = Xk+1
Yk+1 = Yk
Dnew = Dinitial+2ΔY

if Dinitial >= 0 then
Xk+1 = Xk+1
Yk+1 = Yk+1
Dnew = Dinitial+ΔD

Example

Problem => starting coordinates (X₀, Y₀) = (20, 10) and ending coordinates (X_n, Y_n) = (30, 18)

Step 1:

ΔX = Xn – X0 = 30-20 = 10

ΔY =Yn – Y0 = 18-10 = 8

D_initial = 2ΔY – ΔX = 2*8-10 = 6

ΔD = 2(ΔY – ΔX) = 2(8-10) = -4

Step 2:

Comparing Di with 0 then Di >= 0 then

X_k+1 = X_k+1 = 20+1 = 21
Y_k+1 = Y_k+1 = 10+1 = 11
D_new = D_initial+ΔD = 6-4 = 2

Step 3:

Comparing Di with 0 then Di >= 0 then

X_k+1 = X_k+1 = 21+1 = 22
Y_k+1 = Y_k+1 = 11+1 = 12
D_new = D_initial+ΔD = 2-4 = -2

Step 4:

Comparing Di with 0 then Di < 0 then

X_k+1 = X_k+1 = 22+1 = 23

Y_k+1 = Y_k = 12 = 12

D_new = D_initial+2ΔY = -2 + 2*8 = 14

Step 5:

Dinitial	Dnew	Xk+1	Yk+1
		20	10
6	2	21	11
2	-2	22	12
-2	14	23	12

Advantages of the Midpoint line drawing algorithm:

1. Accuracy: The algorithm produces accurate and precise results, especially for lines with small slopes, as it calculates the coordinates of the pixels that should be colored to approximate the line.
2. Smooth lines: The midpoint algorithm produces smoother lines compared to the Bresenham algorithm, which can sometimes produce jagged lines.
3. Flexibility: The algorithm can be easily adapted to draw lines with different styles, such as dashed or dotted lines, by modifying the decision-making process for selecting the next pixel to plot.
4. Easy to implement: The midpoint algorithm is relatively easy to implement and does not require a large amount of memory or processing power.

Disadvantages of the Midpoint line drawing algorithm:

1. Less efficient: The midpoint algorithm requires more floating-point operations than the Bresenham algorithm, which can make it less efficient, especially for larger images or real-time applications.
2. Limited to straight lines: Like the Bresenham algorithm, the midpoint algorithm can only draw straight lines, and cannot be used to draw curved or irregular shapes.
3. Limited to 2D: The algorithm is limited to two-dimensional (2D) graphics and cannot be used for three-dimensional (3D) graphics or more complex visualizations.
4. Floating-point errors: The algorithm uses floating-point calculations, which can introduce rounding errors that affect the accuracy of the final image.