Scribd
Upload
96 views5 pages

Midpoint Circle Algorithm Guide

The document discusses the midpoint circle algorithm for generating circles. It begins by defining a circle mathematically using an equation relating the distance from the center point to all other points. It then introduces the midpoint circle algorithm which uses incremental calculations of a decision parameter at pixel midpoints to determine the next pixel position, rather than direct calculation of each y-value. The decision parameter is the circle function evaluated at pixel midpoints. Based on whether this parameter is positive or negative, the next pixel is determined to be above or below. This allows generation of the circle using recursive expressions without recalculating at each step. Eight-way symmetry is also utilized to further reduce computations.

Uploaded by

Monish Narwani
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
96 views5 pages

Midpoint Circle Algorithm Guide

The document discusses the midpoint circle algorithm for generating circles. It begins by defining a circle mathematically using an equation relating the distance from the center point to all other points. It then introduces the midpoint circle algorithm which uses incremental calculations of a decision parameter at pixel midpoints to determine the next pixel position, rather than direct calculation of each y-value. The decision parameter is the circle function evaluated at pixel midpoints. Based on whether this parameter is positive or negative, the next pixel is determined to be above or below. This allows generation of the circle using recursive expressions without recalculating at each step. Eight-way symmetry is also utilized to further reduce computations.

Uploaded by

Monish Narwani
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 5

TRINAD G SOMANI

D7A/54

AIM:To study and implement circle generating algorithm.

THEORY:A circle is defined as a set of points that are all at a given distance r from a center
positioned at. (xc,yc).
This is represented mathematically by the equation

------------- (1)
Using equation (1) we can calculate the value of y for each given value of x as

---------------- (2)
Thus one could calculate different pairs by giving step increments to x and calculating
the corresponding value of y. But this approach involves considerable computation at
each step and also the resulting circle has its pixels sparsely plotted for areas with
higher values of the slope of the curve.
Midpoint Circle Algorithm uses an alternative approach, wherein the pixel positions
along the circle are determined on the basis of incremental calculations of a decision
parameter.
Let

-------------- (3)
Thus f(x,y)=0 represents the equation of a circle.
In Midpoint Circle Algorithm, the decision parameter at the kth step is the circle function
evaluated using the coordinates of the midpoint of the two pixel centres which are the
next possible pixel position to be plotted.

Let us assume that we are giving unit increments to x in the plotting process and
determining the y position using this algorithm. Assuming we have just plotted the kth
pixel at ( Xk,Yk), we next need to determine whether the pixel at the position ( Xk+1,Yk ) or
the one at ( Xk+1 , Yk-1) is closer to the circle.

Our decision parameter pk at the kth step is the circle function evaluated at the midpoint
of these two pixels.
The coordinates of the midpoint of these two pixels are ( Xk+1, Yk-1/2).
Thus pk

--------------- (4)
Successive decision parameters are obtained using incremental calculations, thus
avoiding a lot of computation at each step. We obtain a recursive expression for the
next decision parameter i.e. at the k+1th step, in the following manner.
Using Equ. (4), at the k+1th step, we have:

Now if Pk <=0, then the midpoint of the two possible pixels lies within the circle, thus
north pixel is nearer to the theoretical circle. Hence, Yk+1= Yk . Substituting this value of
in Equ. (6), we have

If pk > 0 then the midpoint of the two possible pixels lies outside the circle, thus south
pixel is nearer to the theoretical circle. Hence, Yk+1= Yk-1. Substituting this value of in
Equ. (6), we have

For the boundary condition, we have x=0, y=r. Substituting these values in (4), we have

For integer values of pixel coordinates, we can approximate P0=1-r,


Thus we have:

Drawing the circle:


We can reduce our calculation drastically (8 th fraction ) by making use of the fact that a
circle has 8 way symmetry. Thus after calculating a pixel position (x,y) to be plotted, we
get 7 other points on the circle corresponding to it. These are:
(x,y); (x,-y); (-x,y); (-x,-y); (y,x); (y,-x); (-y,x); (-y,-x)

CONCLUSION:Thus circle drawing algorithm and midpoint algorithm is studied and


implemented in C.

You might also like