## Bresenham's Circle Drawing Algorithm Derivation

Bresenham circle drawing algorithm is used to determine the next pixel of screen to be illuminated while drawing a circle by determining the closest nearby pixel.

Let us first take a look how a circle is drawn on a pixel screen

(this is how pixel graph is represented)

As Circles are symmetrical so the values of y-intercept and x-intercept are
are same if circle's Center coordinates are at Origin (0,0).

Here,
Due to symmetrical property of Circle we don't need to calculate all the pixels of all the octets and quadrants
We need to find the pixels of only one octet, rest we can conclude through this.

Lets take the Octet 2 which is in quadrant 1
here both x and y are positive
here the initial pixel would be (0,y) coordinate

At point R both the value of both x and y coordinates would be same as R is at same distance of Both X and Y axis.

## Derivation of Bresenham circle algorithm:

Let's say our circle is at some random pixel P whose coordinates are (xk, yk).
Now we need to find out our next pixel.
Note- This is octet 2 so here x can never be decremented as per properties of a circle but y either needs to decremented or to be kept same. y is needed to be decided.

Here it needs to decide whether go with N or S.

For this bresenham's circle drawing algorithm will help us to decide by calculating the difference between radius and the coordinates of the next pixels.

The shortest of d1 and d2 will help us Decide our next pixel.

note-       xk+1 = x+1
As  xk+1  is the next consecutive pixel of xk
similarly
yk-1 = y-1

Equation of Circle with Radius r

(x– h)2 + (y – k)2 = r2

When coordinates of centre are at Origin i.e., (h=0, k=0)

x2 + y2 = r2    (Pythagoras theorem)

Function of Circle Equation

F(C) = x2 + y2 - r2

Function of Circle at N

F(N) = (xk+1)2 + (yk)– r           (Positive)

Here the value of F(N) will be positive because N is out-side the circle
that makes  (xk+1)+ (yk)2  Greater than r2

Function of Circle at S

#### Here the value of F(S) will be Negative because S is  in-side the circlethat makes(xk+1)2 + (yk-1)2  Less thanr2

Now we need a decision parameter which help us decide the next pixel
Say Dk
And ,   Dk = F(N)+F(S)
Here either we will get the positive or negative value of Dk

So if D< 0
that means the negative F(S) is bigger then the positive F(N), that implies Point N is closer to the circle than point S. So we will select pixel N as our next pixel.

and if   D> 0
that means positive F(N) is bigger and S is more closer as F(S) is  smaller. So we will Select S as our next pixel.

Now lets find  Dk

#### Dk=(xk+1)2 + (yk)2 – r2   +  (xk+1)2 + (yk-1)2 – r2

(replacing xk+1 with xk + 1 and yk-1 with yk -1)

= (xk + 1)2 + (yk)– r2   +  (xk + 1)+ (yk -1)– r2

= 2(xk + 1)2 + (yk)+ (yk -1)– 2r2            ----- (i)

Now lets find Dk+1
(Replacing every k with k+1)

#### Dk+1 = 2(xk+1 + 1)2 +(yk+1)2  + (yk+1 -1)2 – 2r2

= 2(xk+1 + 1)2 + (yk+1)+ (yk+1 -1)– 2r2
(Replacing  xk+1  with  xk + 1   but now we can’t replace  yk+1 because we don’t know the exact value of yk )

= 2(xk+1+ 1)2 + (yk+1)+ (yk+1 -1)– 2r2

= 2(xk+2)2 + (yk+1)+ (yk+1 -1)– 2r2          ----- (ii)

Now to find out the decision parameter of next pixel i.e. Dk+1
We need to find
Dk+1 - Dk = (ii) - (i)

#### - [ 2(xk + 1)2 + (yk)2  + (yk -1)2 – 2r2]

=    2(xk)2 + 8xk + 8 + (yk+1)+ (yk+1)2 - 2yk+1 + 1 - 2r2

#### - 2xk  - 4xk – 2  - (yk)2  - (yk)2 + 2yk  - 1  + 2r2

=  4xk + 2(yk+1)2  - 2yk+1  - 2(yk)2 - 2yk + 6

Dk+1 = Dk + 4xk + 2(yk+1)2  - 2yk+1  - 2(yk)2 - 2yk + 6       ----- (iii)

If (D< 0) then we will choose N point as discussed.
i.e. (xk+1, yk)
that means our next x coordinate is xk+1 and next y coordinate is yk i.e. yk+1 = yk, putting yk in (iii) in replace of yk+1
now,
Dk+1 = Dk + 4xk + 2(yk)2  - 2yk  - 2(yk)2 - 2yk + 6

=  Dk + 4xk + 6

If (D> 0) then we will choose S point.
i.e. (xk+1, yk-1)
that means our next x coordinate is xk+1 and next y coordinate is yk i.e. yk+1 = yk-1 putting yk-1 in (iii) in replace of yk+1
now,
Dk+1 = Dk + 4xk + 2(yk-1)2  - 2yk-1  - 2(yk)2 - 2yk + 6
Now we know
yk-1 = yk – 1
therefore,
Dk+1 = Dk + 4xk + 2(yk -1)2  - 2(yk -1)  - 2(yk)2 - 2yk + 6

= Dk + 4xk + 2(yk) 2 + 2 - 4yk  - 2yk +2  - 2(yk)2 - 2yk + 6

= Dk + 4xk - 4yk + 10

= Dk + 4(xk - yk) + 10

Now to find initial decision parameter means starting point that is (0,r) ,value of y is r
Putting (0,r) in (i)

Dk = 2(xk + 1)2 + (yk)+ (yk -1)– 2r2

D0 = 2(0 + 1)2 + r+ (r -1)– 2r2

= 2 + r2 +r2 + 1 – 2r – 2r2

= 3-2r

Hence we have derived the bresenham’s Circle drawing technique.

More>>

### Bresenham's Line Drawing Derivation

Bresenham's Line Drawing Algorithm Derivation
Bresenham Line drawing algorithm is used to determine closest points to be illuminated on the screen to form a line.

As we know a line is made by joining 2 points, but in a computer screen, a line is drawn by illuminating the pixels on the screen.

(Here pixel (1,2), (3,1) and (5,5) are illuminated and others are non-illuminated) A line from pixel (2,2) to (7,5) will be shown like this on the screen.

The slope of a line plays a major role in the line equation that's why Bresenham line drawing algorithm calculates the equation according to the slope of the line.

The slope of the line can be greater than 1 (m>1) or less than or equal to 1 (m<=1).
Now enough talking let's derive the equations.

Derivation:

Let's say we want to draw a line on the screen.
so, to draw a line we have to calculate the points or pixels to be illuminated on the screen.

Now while drawing a line a sometimes it passes through 2 pixels at the same time then we …

### Bresenham's Circle Drawing Algorithm

Bresenham’s Circle Drawing Algorithm
A circle is made up of 8 Equal Octets so we need to find only coordinates of any one octet rest we can conclude using that coordinates.
We took octet-2. Where X and Y will represent the pixel Let us make a function Circle() with parameters coordinates of Centre (Xc,Yc) and pixel point (X,Y) that will plot the pixel on screen.

We will find pixels assuming that Centre is at Origin (0,0) then we will add the coordinates of centre to corresponding X and Y while drawing circle on screen.
Circle (Xc,Yc,X,Y){
Plot (Y+Xc , X+Yc)……Octet-1 Plot (X+Xc , Y+Yc)……Octet-2 Plot (-X+Xc , Y+Yc)……Octet-3 Plot (-Y+Xc , X+Yc)…..Octet-4 Plot (-Y+Xc , -X+Yc)……Octet-5

### Mid Point Circle Drawing Derivation

Mid Point Circle Drawing Derivation (Algorithm) The mid point circle algorithm is used to determine the pixels needed for rasterizing a circle while drawing a circle on a pixel screen. In this technique algorithm determines the mid point between the next 2 possible consecutive pixels and then checks whether the mid point in inside or outside the circle and illuminates the pixel accordingly.

This is how a pixel screen is represented: A circle is highly symmetrical and can be divided into 8 Octets on graph. Lets take center of circle at Origin i.e(0,0) :

We need only to conclude the pixels of any one of the octet rest we can conclude because of symmetrical properties of circle.