Derive decision parameters for Bresenhams circle algorithm?

Answer 1

//i failed to upload figure.if u want figure for better under standing mail me the request//

Let di = f(N) + f(S), where d can be called as "decision parameter", so that

if di<=0,

then, N(x+1,y) is to be chosen as next pixel i.e. xi+1 = xi+1 and yi+1 = yi,

and if di>0,

then, S(x+1,y-1) is to be chosen as next pixel i.e. xi+1 = xi+1 and yi+1 = yi-1.

reason-since f(N) will be positive being outside the circle while f(S) will be negative as it is inside the circle.thus it comes out.

Derivation

We know that for a circle,

x2 + y2 = r2, where r represents the radius of the circle, an input to the algorithm.

Errors can be represented as

f(N) = (xi + 1)2 + yi2 - r2, -(1)

f(S) = (xi + 1)2 + (yi - 1)2 - r2 -(2)

As di = f(N) + f(S),

di = 2(xi+1)2 + yi2 + (yi-1)2 - 2r2 -(3)

Calculating next decision parameter,

di+1 = 2(xi+2)2 + yi+12 + (yi+1-1)2 - 2r2 -(4)

from (4)- (3), we get,

di+1 di = 2((xi+2)2-(xi+1)2) + (yi+12 - yi2) + ((yi+1-1)2 + (yi-1)2)

di+1 = di + 2((xi+2+xi+1)(xi+2-xi-1)) + ((yi+1+yi)(yi+1-yi)) + ((yi+1-1+yi-1)(yi+1-1-yi+1))

di+1 = di + 2(2xi+3) + ((yi+1+yi)(yi+1-yi)) + ((yi+1-1+yi-1)(yi+1-1-yi+1))

Now, if (di<=0),

xi+1=xi+1 and yi+1=yi

so that di+1 = di + 2(2xi + 3) + ((yi+1+yi)( yi-yi)) + ((yi-1+yi-1)(yi-1-yi+1))

_

di+1 = di + 2(2xi + 3) +

((yi+1+yi)(0)) + ((yi-1+yi-1)(0))

_

di+1 = di + 4xi + 6

else

di+1 = di + 2(2xi+3) + ((yi-1+yi)(yi-1-yi)) + ((yi-2+yi-1)(yi-2-yi+1))

_ di+1 = di + 4xi+6 + ((2yi-1)(-1)) + ((2yi-3)(-1))

_ di+1 = di + 4xi+6 - 2yi - 2yi + 1 + 3

_ di+1 = di + 4(xi - yi) + 10

To know di+1, we have to know di first. The initial value of di

can be obtained by replacing x=0 and y=r in (3). Thus, we get,

do = 2 + r2 + (r - 1)2 -2r2

do = 2 + r2 + r2 + 1 -2r - 2r2

do = 3 - 2r

by jagraj sidhu(jagraj.sidhu@Yahoo.com)