Skip to content

06. Circle Drawing Techniques

Dated: 15-04-2025

Circle

Imagine a point \(O\) called the center of the circle, then the circle is collection of all points, equidistant from \(O\).
This distance is called the radius \(r\) and \(2 \times r = d\) is called the diameter.
The angle is \(360^\circ\) or \(2 \pi\).
The perimeter of a circle is called the circumference \(C\).

\[C = 2 \pi r\]

Circle Drawing Techniques

We need 2 inputs

  • The coordinates of the center.
  • The radius \(r\).

Circle Drawing Using Cartesian Coordinates

If a circle is centered at \((x_c, y_c)\) then equation of the circle is

\[(x - x_c)^2 + (y - y_c)^2 = r^2\]
\[\implies y = y_c \pm \sqrt{r^2 - (x - x_c)^2}\]

Algorithm

def circle1(x_c, y_c, r):
    for x in range(r - x_c, r + x_c):
        y = y_c + sqrt(r ** 2 - (x - x_c) ** 2)
        drawPixel(x, y)
        y = y_c - sqrt(r ** 2 - (x - x_c) ** 2)
        drawPixel(x, y)

This isn't good enough because of the heavy operations like squaring and square roots.
Also, it leaves some gaps in the circle as the slope1 increases.

Circle Drawing Using Polar Coordinates

For more continuous circle

\[x = x_c + r \times \cos(\theta)\]
\[y = y_c + r \times \sin(\theta)\]
def circle2(x_c, y_c, r):
    for theta in range(0, 360, 1 / r):
        x = x_c + r * cos(theta)
        y = y_c + r * sin(theta)
        drawPixel(x, y)

There are still some problems here

  • Floating calculations are expensive
  • We are calculating the whole shape even though it is symmetric

We can solve the symmetric problem by computing only 4th of the circle and then reflecting it across \(x\) and \(y\) axis.

Midpoint Circle Algorithm

We start by plotting \(p(r, 0)\) till \(x < y\) to draw the first octant.

\[x^2 + y^2 = r^2\]
\[\implies x^2 + y^2 - r^2 = 0\]
\[f_{\text{circle}}(x, y) = \begin{cases} < 0 & \text{if } (x, y) \text{ is inside the circle boundary}\\ = 0 & \text{if } (x, y) \text{ is on the circle boundary}\\ > 0 & \text{if } (x, y) \text{ is outside the circle boundary}\\ \end{cases} \]

Imagine we plot \((x_k, y_k)\), now we need to know if next point is \((x_k + 1, y_k)\) or \((x_k + 1, y_k - 1)\)

\[P_k = f_{\text{circle}}\left(x_k + 1, y_k - \frac 1 2\right)\]
\[P_k = (x_k + 1)^2 + \left(y_k - \frac 1 2\right) - r^2\]

If this midpoint, that is \(y_k - \frac 1 2\) is inside the circle then that means point is closer to \(y_k\), otherwise \(y_k - 1\).

cs602_e_6_1.svg

Midpoint (green) inside the circle suggesting that the actual point (blue) is near \(y_k\) instead of \(y_k - 1\).

\[P_{k + 1} = (x_{k + 1} + 1)^2 + \left(y_{k + 1} - \frac 1 2\right) - r^2\]
\[P_{k + 1} = (x_k + 1 + 1)^2 + \left(y_{k + 1} - \frac 1 2\right) - r^2\]

Now doing \(P_{k + 1} - P_k\) gives us

\[P_{k+1} = P_k + 2(x_k + 1) + \left( y_{k+1}^2 - y_k^2 \right) - \left( y_{k+1} - y_k \right) + 1\]
Value of \(y_{k + 1}\) depends upon \(P_k\)
  • \(P_k < 0 \implies y_{k + 1} = y_k \implies P_{k + 1} = P_k + 2(x_k + 1 ) + 1\)
  • \(P_k > 0 \implies y_{k + 1} = y_k - 1 \implies P_{k + 1} = P_k + 2(x_k + 1) - 2 (y_k – 1 ) + 1\)

The starting pixel2 starts from \((0, r)\).

\[P_0 = (0 + 1)^2 + \left(r - \frac 1 2\right) - r^2\]
\[= \frac 5 4 - r\]

We can round it off to \(1\) for integer arithmetics

\[P_0 = 1 - r\]

Algorithm

#include <stdio.h>

void drawSymmetricPoints(int xcenter, int ycenter, int x, int y) {
    // Placeholder: print the symmetric points
    printf("(%d, %d)\n", xcenter + x, ycenter + y);
    printf("(%d, %d)\n", xcenter - x, ycenter + y);
    printf("(%d, %d)\n", xcenter + x, ycenter - y);
    printf("(%d, %d)\n", xcenter - x, ycenter - y);
    printf("(%d, %d)\n", xcenter + y, ycenter + x);
    printf("(%d, %d)\n", xcenter - y, ycenter + x);
    printf("(%d, %d)\n", xcenter + y, ycenter - x);
    printf("(%d, %d)\n", xcenter - y, ycenter - x);
}

void midpointCircle(int xcenter, int ycenter, int radius) {
    int x = 0;
    int y = radius;
    int p = 1 - radius;

    do {
        drawSymmetricPoints(xcenter, ycenter, x, y);
        x = x + 1;

        if (p < 0) {
            p = p + 2 * x + 1;
        } else {
            y = y - 1;
            p = p + 2 * (x + 1) - 2 * (y - 1) + 1
        }

    } while (x < y);
}

int main() {
    midpointCircle(0, 0, 5);
    return 0;
}

References

  1. Read more about slopes. ↩

  2. Read more about pixels. ↩