Bresenhem’s Line drawing algorithm
step-by-Step Algorithm
Here's a more detailed look at the steps of Bresenham's line
drawing algorithm:
• Input the two endpoints of the line. Save the left
endpoint as (x0, y0).
• Plot the first point (x0, y0).
• Calculate the constants Δx, Δy, 2Δy, and (2Δy - 2Δx).
• Calculate the initial decision parameter: p0 = 2Δy - Δx
• For each xk along the line, starting with k = 0:
o If pk < 0, plot (xk+1, yk) and set pk + 1 = pk + 2Δy
o Otherwise, plot (xk+1, yk+1) and set pk+1 = pk + 2Δy -
2Δx
• Repeat step 5 until you reach the end point.
Example
Let us take a look at an example to understand how this
algorithm works.
Consider the input points (3, 2) and (17, 5).First, let's
calculate our initial values −
• Δx = 17 - 3 = 14
• Δy = 5 - 2 = 3
• m = Δy / Δx = 3/14 (slope of the line)
• Initial decision parameter p = 2Δy - Δx = 2(3) - 14 = -8
Now, let's go through the algorithm step-by-step −
Advantages of Bresenham's Line Drawing Algorithm
Following are the Advantages of Bresenham's Line Drawing
Algorithm −
• Simplicity − The algorithm is easy to understand and
implement.
• Efficiency − It uses only integer arithmetic, making it fast.
• Versatility − We can use it to draw lines in any direction.
• Hardware Implementation − It is suitable for hardware
implementation due to its use of simple arithmetic
operations.
Comparison with DDA Algorithm
Bresenham's algorithm has several advantages over the
Digital Differential Analyzer (DDA) algorithm:
• Operations − Bresenham's algorithm uses only addition
and subtraction, while DDA uses multiplication and
division.
• Precision − Bresenham's algorithm is more precise and
accurate.
• Calculation Complexity − Bresenham's algorithm uses
simpler calculations than roundoff in DDA.
• Efficiency − Bresenham's algorithm is more efficient
overall.
• Optimization − Bresenham's algorithm allows for
optimization, while DDA does not.
Mid Point Circle Drawing Algorithm-
Given-
• Centre point of Circle = (X0, Y0)
• Radius of Circle = R
The points generation using Mid Point Circle Drawing
Algorithm involves the following steps-
Step-01:
Assign the starting point coordinates (X0, Y0) as-
• X0 = 0
• Y0 = R
Step-02:Calculate the value of initial decision parameter
P0 as-
P0 = 1 – R
Step-03:
Suppose the current point is (Xk, Yk) and the next point is
(Xk+1, Yk+1).
Find the next point of the first octant depending on the value
of decision parameter Pk.
Follow the below two cases-
Step-04:
If the given centre point (X0, Y0) is not (0, 0), then do the
following and plot the point-
• Xplot = Xc + X0
• Yplot = Yc + Y0
Here, (Xc, Yc) denotes the current value of X and Y
coordinates.
Step-05:
Keep repeating Step-03 and Step-04 until Xplot >= Yplot.
Step-06:
Step-05 generates all the points for one octant.
To find the points for other seven octants, follow the eight
symmetry property of [Link] is depicted by the following
figure-
Problem-01:
Given the centre point coordinates (0, 0) and radius as 10,
generate all the points to form a circle.
Solution-
Given-
• Centre Coordinates of Circle (X0, Y0) = (0, 0)
• Radius of Circle = 10
Step-01:
Assign the starting point coordinates (X0, Y0) as-
• X0 = 0
• Y0 = R = 10
• Step-02:
Calculate the value of initial decision parameter P0 as-
P0 = 1 – R
P0 = 1 – 10
P0 = -9
Step-03:
As Pinitial < 0, so case-01 is satisfied.
Thus,
• Xk+1 = Xk + 1 = 0 + 1 = 1
• Yk+1 = Yk = 10
• Pk+1 = Pk + 2 x Xk+1 + 1 = -9 + (2 x 1) + 1 = -6
Step-04:
This step is not applicable here as the given centre point
coordinates is (0, 0)
Step-05:
Step-03 is executed similarly until Xk+1 >= Yk+1 as follows-
Pk Pk+1 (Xk+1, Yk+1)
(0, 10)
-9 -6 (1, 10)
-6 -1 (2, 10)
-1 6 (3, 10)
6 -3 (4, 9)
-3 8 (5, 9)
8 5 (6, 8)
Algorithm Terminates
These are all points for Octant-1.
Here, all the points have been generated with respect to
quadrant-1-
Important Points
• Circle drawing algorithms take the advantage of 8
symmetry property of circle.
• Every circle has 8 octants and the circle drawing
algorithm generates all the points for one octant.
• The points for other 7 octants are generated by changing
the sign towards X and Y coordinates.
• To take the advantage of 8 symmetry property, the circle
must be formed assuming that the centre point
coordinates is (0, 0).
• If the centre coordinates are other than (0, 0), then we
add the X and Y coordinate values with each point of
circle with the coordinate values generated by assuming
(0, 0) as centre point.
Midpoint ellipse drawing algorithm
The Midpoint Ellipse Algorithm is used for scan converting an
ellipse whose center point is at the origin with its major and
minor axes aligned to the coordinate axes. It is an
incremental approach, much like the Midpoint Circle
Algorithm, and is based on the symmetry of the ellipse. An
ellipse can be divided into four quadrants due to its
symmetry, allowing us to calculate points for just one
quadrant and mirror them to the others
Basic Concepts of Midpoint Ellipse Drawing Algorithm
To understand the midpoint ellipse algorithm, we need to be
familiar with the equation of an ellipse –
ry2 x2 + rx2 y2 - rx2 ry2 = 0
where, ry : semi-minor axis
rx : semi-major axis
Where,
• a is the semi-major axis (the horizontal radius)
• b is the semi-minor axis (the vertical radius)
The goal of the algorithm is to plot the points of this ellipse
by using the incremental approach to determine which pixel
is closer to the actual ellipse boundary. We achieve this by
calculating the midpoint between two potential pixels and
checking if this midpoint lies inside or outside the ellipse.