**BRESENHAWTS CIRCLE DRAWING ALGORITHM**

The Bresenham's circle drawing algorithm considers the eight-way
symmetry of the circle to generate. It plots 1/8

^{th}part of the circle, i.e. 90° to 45°, a shown in the figure below. As circle is drawn from 90° to 45°, the x moves in positive direction and y moves in the negative direction.
To achieve best approximation to the true circle we have to select those
pixels in the raster that fall the least distance from the true circle.

Let us observe the 90° to 45° portion of the
circle. It can be noticed that if points are generated from 90°
to 45°,
each new point closest to the true circle can be found by applying either of
the two options:

• Increment in positive x direction by one unit
or

• Increment in positive x direction and
negative y direction both by one unit

Let us assume point P (x

_{k}, y_{k}) in the above fig as a last converted pixel. Now we have two options either to choose pixel A (x_{k }+ 1, y_{k}) or pixel B (x_{k}+ 1, y_{k}-1). The closer pixel amongst these two can be determined as follows:
The distances of pixels A and B from the origin are given as D

_{A}= √((x_{k}+1)^{2}+ y_{k}^{2})
D

_{B}= √ (x_{k}+1)^{2}+ (y_{k}-1)^{2})
Now, the distances of pixels A and B from the true circle are given as

δ

_{A}= D_{A}- r
δ

_{B}= -(r -D_{B}) =_{ }D_{B}- r^{}
However, to avoid square root term in derivation of decision variable,
i.e. to simplify the computation and make algorithm more efficient the δ

_{A}and δ_{B}are defined as
δ

_{A}= D_{A}^{2}- r^{2}
δ

_{B}= D_{B}^{2}- r^{2}
We can observe from the figure that δ

_{A}is always positive and δ_{B}always negative. Therefore, we can define decision variable d_{k}as
d

_{k}= δ_{A}+ δ_{B}
= 2(x

_{k}+1)^{2}+y_{k}^{2}+(y_{k}-1)^{2}-2r^{2}
and we can say that, if d

_{k}< 0. i.e., δ_{A}< δ_{B }then only x is incremented by 1 unit: otherwise x is incremented by 1 unit and y is decremented by 1 unit.
For d

_{k}< 0, x_{k+1}= x_{k}+ 1 and y_{k+1}= y_{k}
For d

_{k}≥ 0, x_{k+1}= x_{k}+ 1 and y_{k+1}= y_{k}-1
d

_{k+1}= 2(x_{k+1 }+ 1)^{2}+ y_{k+1}^{2}+ (y_{k+1}- 1)^{2}- 2r^{2}
d

_{k+1}- d_{k}= 2(x_{k+1}+ 1)^{2}+ y_{k+1}^{2}+ (y_{k+1}- 1)^{2}-2(x_{k}+ 1)^{2}- y_{k}^{2}- (y_{k}- 1)^{2}
x

_{k+}i = x_{k}+ 1 in all cases
d

_{k+1}= d_{k}+ 2(x_{k}+2)^{2}+ y_{k+1}^{2}+ (y_{k+1}-1)^{2}- 2(x_{k}+1)^{2}- y_{k}^{2}- (y_{k}-1)^{2}
= d

_{k}+ 2x_{k}^{2}+ 8x_{k}+ 8 + y_{k+1}^{2}+ (y_{k+1}– 1)^{2}- 2x_{k}^{2}- 4x_{k}- 2 - y_{k}^{2}-(y_{k}- 1)^{2}
= d

_{k}+ 4x_{k}+ 6 + y_{k+1}^{2}+ (y_{k+1}- 1 )^{2}- y_{k}^{2}- (y_{k}- 1 )^{2}
= d

_{k}+ 4x_{k}+ 6 + y_{k+1}^{2}+ y^{2 }_{k+1}- 2y_{k+1}+1 - y_{k}^{2}- y_{k}^{2}+ 2y_{k}- 1
= d

_{k}+ 4x_{k}+ 6 +2(y_{k+1}^{2}- y_{k}^{2}) - 2(y_{k+1}- y_{k})
For d

_{k}< 0, d_{k+1}= d_{k}+ 4x_{k}+ 6
For d

_{k}≥ 0, d_{k+1}= d_{k}+ 4x_{k}+ 6+ 2((y_{k}-1 )^{2}- y_{k}^{2})) - 2(y_{k}-1 - y_{k}) = d_{k}+ 4x_{k}+ 6+ 2(y_{k}^{2}-2y_{k}+1 - y_{k}^{2})) + 2
= d

_{k }+ 4x_{k}+ 8 - 4y_{k}+ 2
= d

_{k }+ 4x_{k }- 4y_{k }+ 10
= d

_{k }+ 4(x_{k}-y_{k)}+10
The equation for d

_{k }at starting point i.e. at x = 0 and y = r can be simplified as follows
d

_{0}= 2(0+1)^{2 }+ r^{2 }+ (r-1)^{2}- 2r^{2}
= 2 + r

^{2 }+ r^{2 }- 2r + 1 – 2r^{2 }
= 3 - 2r

Algorithm to plot 1/8

^{th}of the circle
1. Read the radius
(r) of the circle.

2. d = 3-2r

3. x = 0, y = r

4. do

{

plot(x, y)
if(d<0)then

{

d = d + 4x + 6

}

else

{

d = d + 4(x-y) +
10 y = y-1

}

x = x+ 1

} while (x < y)

5. Stop

## No comments:

## Post a Comment