Circles A brute force algorithm would be to use the circle equation:
r2 = (x - xc)2 + (y - yc)2 or y = yc ± (r2 - (x - xc)2)1/2
But this is very expensive and gives nonuniform pixel spacing.
Second try: use Polar Coordinates:
x = xc + r cos q step q y = yc + r sin q >
Could set step size yr and get uniform density about 1 pixel apart. But this is still computationally expensive ( computing sin, cos ). Use the Decision Variable Method (Bresenham). We can compute in one octant then use symmetry. So can compute 1 point then plot 8 points as below:
Assume xc = yc = 0 (simple offset) so x2 + y2 = R2
use the 2nd octant and go from x = 0 to x = y = (R / 2)1/2.
so will step x by 1 and choose y. In general have
Can discard points 1, 4, 6 since x increases. Also, discard 1, 2, 3 since y decreases, so we need to choose between 5, 7, 8. The slope of the circle must lie between the slope of the lines defined as pi -> x with x = 5, 7, 8. The slope of pi -> 5 = 0, pi -> 8 = -1, pi -> 7 = undefined. The slope of a circle in the second octant: dy / dx = -x / y so at x = 0, slope = 0 and at x = y, slope = -1. Hence use points. 5, 8 and reject 7.
so have:
y2 = r2 - (xi + 1)2
d1 = y i2 - y2 = yi2 - r2 + (xi + 1)2
d2 = y2 - (y i - 1)2 = r2 - (xi + 1)2 - (yi - 1)2
(1) pi = d1 - d2 = 2(xi + 1) 2 + yi2 + (yi - 1)2 - 2r2
if pi < 0 choose yi {d2> d1}
else choose yi - 1 {d2 < d1, pi> 0}
Now, as before (with the line equation), we can derive
Pi+1 = Pi + 4x i + 6 + 2(yi+12 - yi2) - 2(yi+1 - yi)
so if Pi < 0, {choose yi} {yi+1="yi}" pi+1="Pi" + 4xi + 6
else {pi > 0, choose yi-1} {yi+1="yi-1}" pi+1="P" i + 4(xi yi) + 10
now compute p1 from (1): at x1, y1 x1="0," y1="r" so p 1="3" 2r
Circle Algorithm:
Note integer Addition/Subtraction, multiplication by power of 2. The aspect ratio for monitors is usually 4/3 = 1.33. If the pixels are not "square" then a correction must be made, else the circle will look like an ellipse. For example, in the CGA Mode 6, the pixel resolution is 640/200 = 3.2, so the correction = 3.2/1.33= 2.40.
Look at ellipse - use same method but equation is ay^2 + bx^2 - ab = 0. Ellipse has 4 fold symmetry so use 1st quadrant so x1 = 0 , xf = a½
>Must determine pixel choices from slope:
So initially choice is between 5 & 8 and then between 7 & 8.
Find change over point.
Slope = dy / dx = -bx/ay (x, y both positive in 1st quadrant)
so when ay < bx then slope < 1 and choose between 7, 8
{Note: complete derivation for ellipse in Dr. Dobb's Journal, May
1985 p.40-48}
We can use the Decision variable method to display any function
of form y = f(x). (Remember: changes in slope) Generally easier
to use Line segments but not as pretty or fast.
>May want to plot ARCS or part of curve. Can do as above
just compute initial, final pts. Example: Start at x1 and only
use 1st and 2nd octant symmetry.
Output Primitives menu
HyperGraph
Table of Contents.
HyperGraph Home
page.