Scan-Converting Circles

Scan-Converting Circles
Since the circle is a frequently used component in pictures and graphs, a procedure for generating either full circles or circular arcs is included in most graphics packages. Because of the high symmetry of the circle, it is possible to scan-convert it in many ways.
A circle is defined as the set of points that are all at a given distance r from a center position (x, y) This distance relationship is expressed in Cartesian coordinates as:
x 2 + y 2 = r2
Obvious Methods
Obvious methods for scan-converting a circle are easy to derive and to implement but are slow and inefficient. The first obvious method is based on the Cartesian equation of a circle x2+y2 = R2, which yields y=?R2 ? x2. This expression is used in the loop below to determine one quarter of the circle, which is then duplicated to complete the circle.
Algorithm 1: Circle using Cartesian equation
Inputs: (x, y) circle center , R the radios
Begin
for x=0 to R do
y=sqrt(R*R - x*x )
plot(x,y), plot(-x,y), plot(x,-y), plot(-x,-y)
end
The method is slow, but a more important drawback is that the pixels are not uniformly distributed over the quarter circle. This is a result of the equal x increments of the loop figure below:

The next obvious method solves this problem. Another way to eliminate the unequal spacing shown in Figure above by employing the parametric equation x = Rcos ?, y = Rsin ?, which expresses the circle in terms of polar coordinates.





Algorithm 2: Circle using Polar Coordinate
Inputs: (x, y) circle , R radios
Begin
for theta=0 to 90 do
x = R*cos(theta), y = R*sin(theta)
SetPixel(x,y), SetPixel (-x,y)
SetPixel (x,-y), SetPixel (-x,-y)
end
This method is still very inefficient because of the use of trigonometric functions and also because some pixels may be set multiple times.