Computer Graphics - Circle and Midpoint Circle Algorithms

Circle Properties

• Center: (xc, yc)

• Radius: r

• Equation: r = (x - xc)^2 + (y - yc)^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 = x_c + r imes ext{cos}(θ)

  • 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 P_0 = 1 - R.

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

  • If P_k < 0:

    • x{k+1} = xk + 1

    • y{k+1} = yk

    • P{k+1} = Pk + 2x_{k+1} + 1

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

    • x{k+1} = xk + 1

    • y{k+1} = yk - 1

    • P{k+1} = Pk + 2x{k+1} + 1 - 2y{k+1}

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

  2. Apply octant symmetry to generate complete circle points.