On the Construction of Circular Arcs by Means of Incremental Error Computation

This document explains in full detail the midpoint circle method, with particular attention to the origin of the decision variable and the manner in which its change is obtained at each step.

1. Introduction

When a circle is to be drawn on a rectangular grid of discrete points, direct use of the equation

x² + y² = r²

is inefficient, since it requires repeated squaring and comparison. Early computing devices and plotting machines were not suited to such operations. A method was therefore sought which would permit the tracing of a circular arc by means of addition alone.

The midpoint circle method fulfills this requirement by maintaining a running error value which measures the deviation of the plotted points from the true curve.

2. Equation of the Circle

Let a circle of radius r be centered at the origin. Its equation may be written as:

f(x, y) = x² + y² − r²

For any point (x, y):

If f(x, y) < 0, the point lies inside the circle.

If f(x, y) = 0, the point lies on the circle.

If f(x, y) > 0, the point lies outside the circle.

Only the sign of f is required for decision making.

3. Use of Symmetry

Because the circle is symmetric in eight directions, it is sufficient to compute points only in the region:

0 ≤ x ≤ y

All remaining points are obtained by reflection.

4. Starting Point

The tracing begins at the top of the circle:

x = 0
y = r

This point lies exactly on the circumference.

5. Permissible Steps

From a point (x, y), only two forward steps are permitted:

East: (x + 1, y)
South-East: (x + 1, y − 1)

At each step, one of these two must be chosen.

6. Midpoint Test

Between the East and South-East candidates lies the midpoint:

M = (x + 1, y − 1/2)

If this midpoint lies inside the circle, then the East point is closer to the true curve. If it lies outside, the South-East point is closer.

We therefore evaluate:

f(M) = (x + 1)² + (y − 1/2)² − r²

7. Expansion of the Midpoint Function

(x + 1)² = x² + 2x + 1
(y − 1/2)² = y² − y + 1/4

f(M) = (x² + y² − r²) + 2x − y + 5/4

Let:

d = f(M)

Multiply by 4:

D = 4(x² + y² − r²) + 8x − 4y + 5

8. Initial Value of D

x = 0
y = r

D₀ = 5 − 4r
d₀ = 1 − r

9. Incremental Updating

The value of D is updated incrementally instead of being recomputed.

10. East Step Update

x₁ = x + 1
y₁ = y

D₁ = D + 8x + 12
ΔD = 8x + 12

11. South-East Step Update

x₁ = x + 1
y₁ = y − 1

D₁ = D + 8x − 8y + 20
ΔD = 8x − 8y + 20

12. Interpretation of the Error Term

The variable D represents the signed distance between the true circle and the midpoint.

If D < 0, choose East.

If D ≥ 0, choose South-East.

13. Complete Procedure

Initialize:

x = 0
y = r
D = 5 − 4r

While x ≤ y:

Plot symmetric points.

If D < 0:
D = D + 8x + 12

Else:
D = D + 8x − 8y + 20
y = y − 1

x = x + 1

14. Conclusion

The midpoint circle method transforms the continuous equation of a circle into a discrete stepwise construction by maintaining a single error variable. The change in this variable is obtained directly from algebraic expansion. This permits accurate plotting using only integer arithmetic and is well suited to early computational machinery.