Graphics Reference
In-Depth Information
2.9.2
Drawing Circles
Probably the most straightforward approach to generating points on a circle is to use
a polar coordinate parameterization. If, for simplicity, we restrict the discussion to
circles of radius r centered at the origin, then this map is given by the formula
Æ (
)
q
r
cos
q
,
r
sin
q
.
The only problem with this is that the sine and cosine functions are relatively com-
plicated to evaluate. We want a speedier algorithm. One can use rational functions.
For example, there is the following rational function parameterization of the right
half of the unit circle
2
1
1
-
+
t
t
2
t
t
Ê
Á
ˆ
˜
t
Æ
,
,
-££
11
t
.
2
2
1
+
These rational polynomials can be evaluated rather efficiently using a method of
forward differences, but the problem now is that equally spaced t's do not give rise to
equally spaced points on the circle.
The DDA approach that led to a good algorithm in the case of lines is also appli-
cable to circles. By differentiating the equation
2
2
2
xy r
+=
for a circle of radius r about the origin implicitly with respect to x, one sees that
dy
dx
x
y
=-
is the differential equation for that circle. This means that a circle-generating DDA
can be written in the form
x
=+
=-
x
e
e
y
n
+
1
n
n
y
y
x
.
n
+
1
n
n
A natural choice for e is 2 -n , where 2 n-1 £ r < 2 n . Unfortunately, if one were to plot the
points that are generated by these equations, one would find that they spiral outward.
From a mathematical standpoint one should not have been surprised because the
determinant of the matrix
1
-
e
Ê
Ë
ˆ
¯
e
1
for this linear transformation is 1 +e 2 . An ad hoc way to correct this determinant
problem is to make a slight change and note that the matrix
1
-
-
e
Ê
Ë
ˆ
¯
2
e
1
e
Search WWH ::




Custom Search