# Deriving The Midpoint Circle Drawing Algorithm

The midpoint circle drawing algorithm is a graphics algorithm for approximating the pixels needed to draw a circle given a radius and a centre coordinate. It is an extension to Bresenham’s line algorithm.

The algorithm calculates all points for the circle in the first (i.e., the north to north-east) octant. All remaining points can be found by translating these coordinates.

To skip straight to the final algorithm, scroll down. Alternatively, continue on to the derivation.

## Derivation

The equation of a circle in terms of `x`

, `y`

and a radius , `r`

is:

```
square(x) + square(y) = suqare(r)
```

This equation can be transformed into:

```
f(x, y) = 0 = square(x) + square(y) - suqare(r)
```

It follows that for any pair `(x, y)`

:

if `(x, y)`

is **on** the line, `f(x, y) = 0`

if `(x, y)`

is **off** the line, `f(x, y) != 0`

- if
`f(x, y) < 0`

,`(x, y)`

is on the ‘*negative*half-plane’ - if
`f(x, y) > 0`

,`(x, y)`

is on the ‘*positive*half-plane’

To simplify the problem, we initially assume that the centre of the circle to be drawn is at `(0, 0)`

.
The real centre points can be reintroduced later as an offset to the final result.

Starting from the point directly above the centre (i.e., `(0, R)`

), we move clockwise calculating points on the circle until we reach a 45^o angle (i.e., when `x = y`

).
This is illustrated in the image above.

Within this area, `x`

will *always* increment by 1.
We need to figure out if `y`

will move *across* (i.e., if `y = y`

), or if `y`

will move *across and down* (i.e., if `y = y - 1`

).
Selecting between these two candidates is the same as in Bresenham’s algorithm: we calculate the value of `f(x, y)`

at a midpoint `M`

.
The value of `M`

is determined in terms of the last-calculate point on the line, `(xp, yp)`

.

```
M = (xp + 1, yp - 0.5)
```

If `f(M) < 0`

, `M`

is in the negative half-plane of the line.
This means `M`

is *below* the line, indicating that the line is closer to the *upper* candidate point (i.e., where `y`

doesn’t change).
Hence, we choose the candidate `(xp + 1, yp)`

as the next point on the line.

If `f(M) > 0`

, `M`

is in the positive half-plane of the line.
This means `M`

is *above* the line, indicating that the line is closer to the *lower* candidate point (i.e., where `y`

changes).
Hence, we choose the candidate `(xp + 1, yp - 1)`

as the next point on the line.

In other words:

- if
`f(M) < 0`

,`y = y`

- if
`f(M) > 0`

,`y = y - 1`

To avoid having to calculate `f(M)`

all the time, we introduce the notion of a decision variable.

The ‘decision’ variable, `D`

, keeps track of the current value of `f(M)`

.
Its initial value can be calculated as the difference between the first midpoint, `M`

, and the starting coordinate in our circle, `(0, R)`

.

```
D = f(M) - f(0, R)
= f(0 + 1, R - 0.5) - f(0, R)
= f(1, R - 0.5) - f(0, R)
= square(1) + square(R - 0.5) - square(R) - [square(0) + square(R) - square(R)]
= square(1) + square(R - 0.5) - square(R)
= 1 + square(R - 0.5) - square(R)
= 1 + square(R) - 0.5R - 0.5R + 0.25 - square(R)
= 1 + square(R) - 0.5R - 0.5R + 0.25 - square(R)
= 5/4 - R
```

`D`

can then be used to determine which candidate point to select next, using the same logic as earlier:

- if
`D > 0`

, select`(xp + 1, yp)`

- if
`D < 0`

, select`(xp + 1, yp - 1)`

As we calcuate points on the line, we need to update the value of `D`

to correspond to the next midpoint.
The way in which the value changes depends on which candidate point was chosen (i.e., if `y`

was changed or not).

We can define the midpoint at step `k`

as being:

```
midpoint(k) = (x(k) + 1, y(k) - 0.5)
```

It follows that the midpoint at step `k + 1`

is then:

```
midpoint(k + 1) = (x(k + 1) + 1, y(k + 1) - 0.5)
```

Because we know that `x`

will *always* be incremented, we know that `x(k + 1) = x(k) + 1`

.
We can use this knowledge to simplify the equation for `(midpoint(k + 1))`

as follows:

```
midpoint(k + 1) = (x(k) + 1 + 1, y(k + 1) - 0.5)
```

To calculate the general increment to apply to the decision variable `D`

, `dInc`

, we need to calculate the difference between `f(midpoint(k + 1))`

and `f(midpoint(k))`

.

```
dInc = f(midpoint(k + 1)) - f(mipdoint(k))
= square(x(k) + 1 + 1) + square(y(k + 1) - 0.5) - square(R) - [square(x(k) + 1) + square(y(k) - 0.5) - square(R)]
= square(x(k) + 2) + square(y(k + 1) - 0.5) - square(R) - square(x(k) + 1) - square(y(k) - 0.5) + square(R)
= square(x(k) + 2) + square(y(k + 1) - 0.5) - square(x(k) + 1) - square(y(k) - 0.5)
```

We then need to substitute each possible value of `y(k + 1)`

to find the two potential increments to `D`

.

So, if `y`

**was not incremented**:

```
y(k + 1) = y(k)
dInc = square(x(k) + 2) + square(y(k) - 0.5) - square(x(k) + 1) - square(y(k) - 0.5)
= square(x(k) + 2) - square(x(k) + 1)
= square(x(k)) + 2x(k) + 2x(k) + 4 - (square(x(k)) + x(k) + x(k) + square(1))
= square(x(k)) + 4x(k) + 4 - (square(x(k)) + 2x(k) + 1)
= square(x(k)) + 4x(k) + 4 - square(x(k) - 2x(k) - 1)
= 4x(k) + 4 - 2x(k) - 1)
= 2x(k) + 3
```

If `y`

**was incremented**:

```
y(k + 1) = y(k) - 1
dInc = square(x(k) + 2) + square(y(k) - 1 - 0.5) - square(x(k) + 1) - square(y(k) - 0.5)
= square(x(k) + 2) + square(y(k) - 1.5) - square(x(k) + 1) - square(y(k) - 0.5)
= square(x(k)) + 2x(k) + 2x(k) + 4 + square(y(k)) - 1.5y(k) - 1.5y(k) + 2.25 - (square(x(k)) + x(k) + x(k) + 1) - (square(y(k)) - 0.5y(k) - 0.5y(k) + 0.25)
= square(x(k)) + 2x(k) + 2x(k) + 4 + square(y(k)) - 1.5y(k) - 1.5y(k) + 2.25 - square(x(k)) - x(k) - x(k) - 1 - square(y(k)) + 0.5y(k) + 0.5y(k) - 0.25
= square(x(k)) + 4x(k) + 4 + square(y(k)) - 3y(k) + 2 - square(x(k)) - x(k) - x(k) - 1 - square(y(k)) + y(k)
= square(x(k)) + 4x(k) + 5 + square(y(k)) - 3y(k) - square(x(k)) - x(k) - x(k) - square(y(k)) + y(k)
= 4x(k) + 5 - 3y(k) - x(k) - x(k) + y(k)
= 2x(k) + 5 - 2y(k)
= 2(x(k) - y(k)) + 5
```

So, during each iteration of the algorithm, based on whether `y`

was decremented or not, we increment `D`

by either `2x(k) + 3`

or `2(x(k) - y(k)) + 5`

.

## Algorithm

Assuming the existence of a method `setPixel(x, y)`

, which colours a pixel at the location `(x, y)`

, the following algorithm represents the midpoint circle drawing algorithm for the first octant, given a radius `R`

, and a centre point `(midX, midY)`

.

```
d = (5 / 4) - R
y = R
for (x = 0; x < y; ++x):
setPixel(x + midX, y + midY) # offset the pixel according to the circle centre
if (d < 0):
d += (2 * x) + 3
else:
d += 2 * (x - y) + 5
y -= 1
```

However, there are still some floating point calculations in the algorithm, specifically in the initialisation of `d`

.
To avoid this, we can multiply all values of `d`

by `4`

, including the initialisation of `d`

and the increments to `d`

.

We are also only drawing the pixels for the first octant.
This can be fixed by translating the `x`

and `y`

coordinates to cover all octants.

Applying these two changes results in the final optimised algorithm:

```
d = 5 - (4 * R)
y = R
for (x = 0; x < y; ++x):
setPixel(x + midX, y + midY) # offset the pixel according to the circle centre
# colour the pixels in the other 7 octants
setPixel(x + midX, -y + midY) # offset the pixel according to the circle centre
setPixel(-x + midX, y + midY) # offset the pixel according to the circle centre
setPixel(-x + midX, -y + midY) # offset the pixel according to the circle centre
setPixel(y + midX, x + midY) # offset the pixel according to the circle centre
setPixel(y + midX, -x + midY) # offset the pixel according to the circle centre
setPixel(-y + midX, x + midY) # offset the pixel according to the circle centre
setPixel(-y + midX, -x + midY) # offset the pixel according to the circle centre
if (d < 0):
d += 4 * ((2 * x) + 3)
else:
d += 4 * (2 * (x - y) + 5)
y -= 1
```