Computer Graphics - Circle and Midpoint Circle Algorithms

Circle Properties

  • Center: (xc, yc)

  • Radius: r

  • Equation: r=(x−x<em>c)2+(y−y</em>c)2r = (x - x<em>c)^2 + (y - y</em>c)^2

Coordinate Systems

  • Cartesian Coordinates: Points represented as (x, y).

  • Polar Coordinates: Points represented as (r, θ) where r is the distance from the origin and θ is the angle.

    • Transformation equations:

    • x=xc+rimesextcos(θ)x = x_c + r imes ext{cos}(θ)

    • y=yc+rimesextsin(θ)y = y_c + r imes ext{sin}(θ)

Circle Symmetry

  • Quadrant Symmetry: Split by horizontal and vertical diameters.

  • Octant Symmetry: Further divide each quadrant into eight octants for symmetry.

Midpoint Circle Drawing Algorithm

  • Assumes the circle center at (0, 0).

  • Can shift to any center (xc, yc) after computing points.

  • Steps to generate points:

    1. Start at (0, R), calculate initial decision parameter P0=1−RP_0 = 1 - R.

    2. Incrementally determine next points in the octant based on the decision parameter:

    • If P_k < 0:

      • x<em>k+1=x</em>k+1x<em>{k+1} = x</em>k + 1

      • y<em>k+1=y</em>ky<em>{k+1} = y</em>k

      • P<em>k+1=P</em>k+2xk+1+1P<em>{k+1} = P</em>k + 2x_{k+1} + 1

    • If P_k ext{ is } ext{not} < 0:

      • x<em>k+1=x</em>k+1x<em>{k+1} = x</em>k + 1

      • y<em>k+1=y</em>k−1y<em>{k+1} = y</em>k - 1

      • P<em>k+1=P</em>k+2x<em>k+1+1−2y</em>k+1P<em>{k+1} = P</em>k + 2x<em>{k+1} + 1 - 2y</em>{k+1}

    1. Repeat until x{k+1} >= y{k+1}.

    2. Apply octant symmetry to generate complete circle points.