Circle Drawing AlgorithmsPictures snagged from http://accad.osu.edu/~waynec/history/
Drawing Circles and ArcsSimilar to line drawingIn that you have to determine what pixels to activateBut non-linearSimple equation implementationOptimized
Cartesian form ofCircle Equations(xc, yc)rNot a very good method. Why?
Be the algorithm!
What does it do?01234567801234567891011
Polar Coordinate Form(x, y)rSimple method: plot directly from parametric equations
Trig functions are expensivePlots of first 1, 3, 5, 7, 9, 11, and 13 terms in the Taylors series for sin
Polygon Approximation(xi, yi)Calculate polygon vertices from polar equation; connect with line algorithm
The Bresenham AlgorithmsBresenham, J. E. Algorithm for computer control of a digital plotter, IBM Systems Journal, 4(1), 1965, pp. 25-30.Bresenham, J. E. A linear algorithm for incremental digital display of circular arcs. Communications of the ACM, 20(2), 1977, pp. 100-106.
- Bresenhams Midpoint Circle Algorithm0
The Circle Decision ParameterCalculate fcircle for point midway between candidate pixelsxkykIf pk < 0:If pk >= 0:
Recurrence Relation for pk
One Last Term If yk+1 = yk, then:If yk+1 = yk-1, then:
Bresenham Midpoint Circle Algorithm SummaryAt each point:If pk < 0:If pk >= 0:
Circle Example 101234567801234567891011r = 7
Symmetry Optimization(a, b)(b, a)(a, -b)(b, -a)(-b, a)(-b, -a)(-a, b)(-a, -b)Calculate points for one octant; replicate in other seven
General Ellipse EquationIn general, ellipse described by constant sum of distances from fociDifficult to solve equations and plot points (use parametric polar form?)
Special Case Ellipses(xc, yc)rxryModified midpoint algorithm possible
Drawing EllipsesGeneral ellipsesPolygon approximationRotation (well defer this until later, when we cover coordinate transformations)Aligned axesConstrained (no rotation)Midpoint algorithm
CS-321Dr. Mark L. HornickCS-321y(k) = y(c) + sqrt(r**2-(xk-xc)**2)Dr. Mark L. HornickCS-321Dr. Mark L. HornickCS-321Dr. Mark L. Hornick