________________________________________________________________________
______________
DDA Circle Drawing Algorithm
Purpose
The DDA (Digital Differential Analyzer) circle drawing algorithm is used
to plot points along the boundary of a circle using polar coordinates.
Parametric Form of a Circle
The circle equation in polar form:
x = x_center + r * cos(theta)
y = y_center + r * sin(theta)
Where:
o x_center, y_center: coordinates of circle center
o r: radius of the circle
o theta: angle in radians
Algorithm Steps
1. Input center, radius
a. Enter values for xcenter, ycenter, and r.
2. Plot starting pixel
a. Plot the initial pixel at (xcenter, ycenter).
3. Loop through angles
a. For theta from 0 to 2π (or 3.14159 in steps, usually with a small
increment e.g., 0.01):
1. x=xcenter+r⋅cos(θ)
i. Calculate next position:
2. y=ycenter+r⋅sin(θ)
ii. Plot pixel at calculated (x, y).
4. Repeat for all increments
a. Continue for all values of theta in the specified range.
5. Stop after completing the full circle.
Key Points
Rather than stepping through x or y, DDA circle drawing uses the
parametric equations to generate accurate coordinates along the
circle’s path.
Small angle increments are used to sample points smoothly.
Advantages of DDA Circle Drawing Algorithm
Simple and easy to implement, making it suitable for educational
purposes and basic applications.
Uses parametric equations with small increments of angle (theta),
allowing smooth and continuous plotting of points.
Can handle all types of circles since it works directly from the radius
and center without complex integer approximations.
Suitable for generating points when high precision of floating-point
calculations is acceptable.
Disadvantages of DDA Circle Drawing Algorithm
Computationally expensive because it requires repeated calculation of
trigonometric functions (cosine and sine) for each point.
Uses floating-point arithmetic, which is slower on some systems and
leads to possible rounding errors.
The method involves considerable computation at each step, making it
less efficient for real-time applications.
Plotting points may not be uniform due to how increments are taken,
potentially causing uneven spacing.
Not ideal for hardware implementation due to floating-point operations.
Less accurate and slower compared to algorithms like Bresenham's
Circle Algorithm which use integer arithmetic and symmetry.
______________________________________________________________________________
______________
Bresenham's Circle Drawing Algorithm
Introduction
Bresenham's algorithm efficiently plots a circle using integer arithmetic
by exploiting the symmetry of circles.
It avoids floating point and trigonometric calculations, making the
computations faster.
Symmetry of Circle
The circle is symmetric in all eight octants.
A point (x,y) on one octant corresponds to seven other points obtained
by reflecting across the axes.
The algorithm calculates points only for one octant and mirrors them to
the other seven octants, as shown in the figures of symmetry.
Working Principle
The circle is traced by starting at the topmost point (0,r).
At each step, the algorithm chooses between two potential pixels to
get closer to the true circle:
o Pixel to the East: (x+1,y)
o Pixel to the South-East: (x+1,y−1)
Calculation
Decision parameter P is used to choose the pixel at each step.
The initial decision parameter and its updates are based on the error
between the midpoint and circle boundary.
Steps Summary
Start with (x,y)=(0,r).
Using symmetry, plot points in all eight octants.
Update decision parameter as the algorithm moves along the
Continue until x≥y.
circumference.
Midpoint Circle Drawing Algorithm
Step 1: Input Values
Input the radius r and the circle center (xc,yc).
The first point on the circle is at (x0,y0)=(0,r) i.e., the top of the circle.
Step 2: Initialize Decision Parameter
Calculate the initial decision parameter:
o If r is not an integer, use p0=45−r
o If r is an integer, use p0=1−r.
Step 3: Iterate Through Each X Position
Starting value: k=0, current position: (xk,yk)
For each xk, perform the following test:
o If pk<0: Next point is (xk+1,yk), update pk+1=pk+2xk+1
o If pk≥0: Next point is (xk+1,yk−1), update pk+1=pk+2xk+1−2yk
This decision makes sure the plotted pixel is closest to the circle
boundary.
Step 4: Determine Symmetry Points
For each calculated point in the first octant, use symmetry to
determine the corresponding points in the other seven octants.
Apply the symmetry using a function or manually mapping to (x,y), (y,x),
and their respective negatives, etc..
Step 5: Repeat the Process
Repeat steps 3 and 4 until x≥y (i.e., when the algorithm completes a full
octant).
Step 6: Stop
Exit the algorithm when all relevant points of the circle have been
plotted.
Key Points from the Algorithm
The midpoint circle algorithm only uses integer addition and
subtraction, making it highly efficient.
The decision parameter determines which pixel best matches the ideal
circle's path.
Symmetry greatly reduces the number of calculations.
The starting position and carefully chosen decision parameters ensure
accurate and fast circle generation.
Formulas for Midpoint Circle Algorithm
Example:
Bresenham's Circle drawing for a circle with radius r=10.
Demonstrate the midpoint circle algorithm by plotting points in the
first quadrant from x=0 to x=y
Step 0
x0=0,y0=10
p0=1−r=1−10=−9
Since p0<0, choose East pixel:
x1=x0+1=1
y1=y0=10
Update decision parameter:
p1=p0+2x1+1=−9+2×1+1=−6
Step 1:
x1=1,y1=10,p1=−6
p1<0 choose East pixel:
x2=x1+1=2
y2=y1=10
Update decision parameter:
p2=p1+2x2+1 =−6+2×2+1 =−1
Step 2:
x2=2,y2=10,p2=−1
p2<0, choose East pixel (as per basic rule):
x3=x2+1=3
y3=y2=10
Update decision parameter:
p3=p2+2x3+1=−1+2×3+1=−1+6+1=6
Step 3:
x3=3,y3=10,p3=6
p3>0, choose South-East pixel:
x4=x3+1=4
y4=y3−1=9
Update decision parameter:
p4=p3+2x4−2y4+1 =6+2×4−2×9+1 =6+8−18+1 =−3
Step 4:
x4=4,y4=9,p4=−3
p4<0, choose East pixel:
x5=x4+1=5
y5=y4=9
Update decision parameter:
p5=p4+2x5+1=−3+2×5+1=−3+10+1=8
Step 5:
x5=5,y5=9,p5=8
p5>0, choose South-East pixel:
x6=x5+1=6
y6=y5−1=8
Update decision parameter:
p6=p5+2x6−2y6+1=8+12−16+1=5
Step 6:
x6=6,y6=8,p6=5
p6>0, choose South-East pixel:
x7=x6+1=7
y7=y6−1=7
Update decision parameter:
Continue using the same formula.