Motivation
A circle is an equation in continuous coordinates; an image is a collection of samples on a lattice. Substituting integer horizontal coordinates into a square-root formula is one possible way to connect them, but it leaves several questions unanswered. Which arc should be sampled? How should its samples be reflected? What happens on an axis or the diagonal, where two reflections coincide? And does selecting a nearby center say anything about the fraction of its pixel square covered by a stroke?
The integer line note answered similar questions for a linear implicit function. A circle has a quadratic implicit function. Its successive differences are still simple enough to update by integer addition. We will derive those additions from a particular midpoint, rather than borrow a line recurrence or silently replace a fractional expression by a familiar approximation.
This note specifies one binary boundary-selection procedure. Pixel centers are the points of , the vertical coordinate increases upward, the center is integral, and the radius is a nonnegative integer. All arithmetic in the proof uses mathematical integers. These assumptions make the initial axis point and all eight symmetries compatible with the lattice. Fractional centers, finite-width strokes, antialiasing and native graphics-API conventions require further specifications.
Definitions
Definition 2.3.1
(Implicit circle and its fundamental octant)
Work first in offsets from the center and define
Negative values are inside the circle and positive values are outside. The fundamental octant used here is . Start at the exact axis point . At a state with , the two next candidates are the east point and the southeast point .
Both candidates advance one horizontal coordinate. The second additionally lowers the vertical coordinate. Their midpoint is . The letters name directions in our upward-increasing coordinate system; a framebuffer with downward-increasing row numbers must map coordinates consistently.
Definition 2.3.2
(Exact midpoint decision and closed-octant policy)
Store the scaled midpoint value
Emit the current state when . If , stop this octant immediately. Otherwise choose when , and choose when . After the move, emit the new state only if it still has ; a crossed state is not an additional octant sample.
The weak inequality states a complete equality policy: a hypothetical zero would choose the lower candidate. In fact, an odd square is one modulo four, so . Zero cannot occur for this model. This is a statement about exact midpoint equality, not a claim that every other notion of equal distance has been excluded.
Why does the sign have this direction? Before any nonterminal decision, , hence and the upper circular arc has a real height
Also . Thus means , so is vertically nearer to than is. When , and the lower candidate is vertically nearer. This establishes the comparison between the two declared candidates. A global nearest-pixel or nearest-radial-distance theorem is not being asserted.
The recurrence and its proof
At the initial state the decision is
Suppose the old coordinates are . After an east move, the next tested midpoint changes from to . Therefore
After a southeast move, it changes to , giving
These formulas use the coordinates before the move. Using the already incremented horizontal coordinate in the same expressions would evaluate a different polynomial.
Theorem 2.3.3
(Exact decision invariant and finite termination)
For integer , initialize , , . At every nonterminal emitted state apply exactly one of the following simultaneous updates:
At every state reached, and . Every emitted state satisfies . The procedure terminates after at most moves. Successive emitted states differ by or . For , the result is just the center; an early return is convenient but not necessary.
Proof
(Induction through both branches)
The initial identity was computed above. If it holds at an old state, the two polynomial differences give exactly the identity at the corresponding new state. Induction proves it through either branch, including a final crossed state whose decision will never be used. The congruence follows from the displayed polynomial, or from the initial congruence and the fact that both increments are divisible by four.
Initially . At a nonterminal emitted state, , so . The new horizontal coordinate is nonnegative, and either update leaves . If the new state remains in the octant, all emitted-state inequalities hold again; otherwise it is discarded and the loop stops. In particular, no negative vertical coordinate is emitted.
For termination, let . It starts at . Each east move reduces it by one, and each southeast move reduces it by two. A move is allowed only while . Consequently after at most moves we have either reached , which is emitted and stops immediately, or crossed to , which is not emitted. The possible displacements give the adjacency statement. When , the initial state is already diagonal. Its eight orbit entries all equal , so local deduplication returns one center and the general loop stops before making any move. The early return merely makes this case explicit. This proves every claim.
Proof X-ray
What the invariant proves, and what it does not
The invariant identifies a stored integer with the implicit function at the next candidates' midpoint. It does not identify with the error at the center already emitted: that center has implicit value , a different quantity at a different location. The sign comparison proves the nearer choice among two vertical candidates. Neither that comparison nor finite termination by itself proves global radial optimality, all-touched-square coverage, a Hausdorff bound or an antialiasing formula. Those would require separate statements and proofs.
Why the last octant sample needs no extra endpoint
If the last emitted state is diagonal, it is already its own reflection across . If the loop instead exits by crossing the diagonal, its last emitted state has . To see this, a crossing from a positive integer gap is possible only when a southeast move subtracts two from gap one. An east move from gap one reaches zero and is emitted. Thus a crossing ends with a pair ; the missing-looking neighbor will be supplied by reflection. Emitting the crossed state as another octant sample would duplicate that neighbor's orbit.
Eight-way symmetry without duplicate writes
For an offset , form the following ordered candidate list:
Add to each offset, retaining only its first occurrence within that list. A set of eight destinations is not always eight distinct pixels. For with there are four axis pixels. For with there are four diagonal pixels. When , there are eight distinct pixels. The zero-radius case has only one.
Theorem 2.3.4
(Unique orbit ownership and an eight-connected boundary)
The emitted representatives have disjoint symmetry orbits. For , if there are representatives and when the last representative is diagonal, otherwise , the number of distinct selected centers is
Their union is eight-connected: between any two selected centers there is a path of selected centers whose successive coordinate differences have absolute value at most one in each coordinate.
Proof
(Unique orbits and connectivity)
Any point in an orbit determines its unique nonnegative ordered absolute coordinates . These recover its fundamental-octant representative. No representative repeats, because strictly increases, so no two different representatives have a common orbit. The initial representative is the only one on an axis. There can be at most one diagonal representative, since it stops the loop. Counting four points for the axis, four for a possible diagonal and eight for the others gives the formula. The restriction to matters: at radius zero the axis and diagonal representative coincide, and the formula would give zero instead of the correct one center.
Within the fundamental octant, consecutive representatives are eight-neighbors. Reflections preserve that relation. At the diagonal, either the two reflected paths share their diagonal endpoint, or their endpoints are and , which are eight-neighbors by the stopping argument. At an axis, adjacent reflected paths share the same axis endpoint. For a clockwise walk starting at the upper axis, use the transformed paths , reversing the traversal of every second path. Their junctions alternate between diagonal and axis. Joining these paths connects all the selected centers. This is a connectivity result for the selected pixel graph; it does not equate that graph with a continuous circle or a filtered stroke.
The order of first occurrences in the eight-entry list specifies deterministic output, but is not angular boundary traversal. Applications needing a clockwise polyline must assemble the octant paths in angular order. Applications doing counting or alpha blending must remove duplicates even if repeated opaque writes happen to look harmless.
Worked examples
Worked example 2.3.5
(Radius three: every state, every orbit)
Take and . The first decision is . The decision stored at a diagonal state is shown for checking the invariant, but is not used.
| Current | Action after emission | Update using old coordinates | ||
|---|---|---|---|---|
| east | ||||
| southeast | ||||
| stop on diagonal | no next decision |
The midpoint in the second row is , whose implicit value is ; multiplying by four gives the stored . Therefore the algorithm lowers the next vertical coordinate. The output contains both interior and exterior centers relative to the exact circle: binary boundary selection is not the same as insisting on .
After local duplicate removal, the three orbits are
Thus , and . Translating the center to translates each of these sixteen centers by , with exactly the same offset calculations and decisions.
Worked example 2.3.6
(Radius five: crossing is a stopping event)
For , the emitted states and stored decisions are
The first two moves are east. The next is southeast, with increment , taking from to . The final move is southeast again and reaches , outside the fundamental octant. It is not emitted as a new representative: it already belongs to the orbit of . There are four representatives, no diagonal representative and distinct output centers.
Worked example 2.3.7
(The smallest radii)
For we have . The axis representative is emitted; since the move is southeast and reaches , which is crossed and not emitted. Is the rightmost point missing? No: already belongs to the orbit of . With and the count is , namely . For the initial state is diagonal, so the loop stops before any move and the eight orbit entries collapse to the single center ; the early return gives the same result.
Complete integer procedure
The code below keeps updates in the same order as the proof: calculate the new decision with the old , then change the coordinates. unique_in_order retains the first occurrence of each entry in a list of at most eight pairs.
function raster_circle(C, r):
require C.x and C.y are integers; require integer r >= 0
if r == 0: return [C]
x = 0
y = r
D = 5 - 4*r
output = []
while x <= y:
orbit = [(x,y), (y,x), (-x,y), (-y,x),
(-x,-y), (-y,-x), (x,-y), (y,-x)]
for (u,v) in unique_in_order(orbit):
append (C.x + u, C.y + v) to output
if x == y: break
if D < 0:
D = D + 8*x + 12
x = x + 1
else:
D = D + 8*x - 8*y + 20
x = x + 1
y = y - 1
return output
No whole-output hash set is needed: unique orbit ownership was proved, and the local eight-entry list can be deduplicated in constant space. Under a constant-cost arithmetic model, time is and auxiliary space is when results are streamed. Storing the output needs space. Mathematical integers conceal a bit cost; fixed-width implementations must accommodate center translation, the initial products and intermediate updates without overflow. This note supplies no machine-integer range certification.
Misconceptions and counterexamples
Counterexample mode
A fractional center does not preserve this lattice construction
For radius one at the origin, the algorithm emits the four axis centers . Translating these offsets by produces half-integer horizontal coordinates, not integer pixel centers. Those locations cannot be used directly as integer centers. Snapping the circle center to a lattice point changes the circle: at the integer pixel center , the implicit value for the true translated circle is , while for a circle snapped to the origin it is .
Eight-way symmetry is also not automatically a symmetry of the integer lattice about a fractional center. Swapping the two offsets of about gives , which is not an integer center. Some special fractional centers retain some lattice symmetries, but that does not validate the present axis seed and recurrence for arbitrary centers. A new model and derivation are needed.
Counterexample mode
A selected boundary pixel is not a full-coverage pixel
To define a genuine finite-width outline, take the annulus and a unit box filter. The pixel square centered at contains an open neighborhood of its center inside the annulus, but also a subset of positive area near its corner outside the annulus, since and the distance function is continuous. Its covered area is strictly between zero and one. The binary radius-one algorithm selects that center and writes a full binary value; it does not calculate this fractional area.
A zero-width ideal circumference has area zero, so integrating its ordinary area indicator would give zero in every pixel. A visible antialiased outline therefore needs a width or another reconstruction model as well as a filter. Eight-way symmetry and an exact integer recurrence do not supply those missing definitions.
Common mistake
(Mixing initializations and recurrences from different presentations)
A common arithmetic shortcut initializes a different stored value, for example , and then uses a recurrence taken from another presentation. That value is not our exact at the first midpoint. It might define an equivalent algorithm under a separately proved transformation, or a different algorithm, but equivalence cannot be inferred by mixing initializations and updates. Keep the defining invariant attached to the stored quantity.
Common mistake
(Testing the emitted center instead of the next midpoint)
Testing only at the current emitted center asks whether that center is inside or outside the circle. It does not compare the next two candidates. For radius three, gives no sign to act on, while the decision is and the correct move is east. Replacing one sign by the other confuses two distinct tests.
Exercises
Quick check
(Trace radius four. List every emitted representative and decision, the move after each nonterminal state, and the distinct output count.)
Start from and apply the update table.
Solution · Guided solution
The representatives are , with decisions . From the first state take east: . From take southeast: . From take east: . Stop at without using its decision. With and , the output count is .
Quick check
(At an emitted state with , , , compute directly, select the next state and compute its decision in two ways. Explain which old coordinates the recurrence needs.)
Substitute into the defining polynomial first, then compare with the update.
Solution · Guided solution
Direct substitution gives . Choose southeast, reaching . The old-coordinate update is . Direct substitution at the new state gives , agreeing exactly. Using inside the old-coordinate increment would instead add , producing , and would break the invariant.
Quick check
(Prove that exact midpoint equality cannot occur for integer radius and integer states. If a program changes D < 0 to D <= 0, does its exact-arithmetic output change under this specification?)
Look at and modulo four.
Solution · Guided solution
The two terms and are divisible by four, while is one modulo four. Hence and cannot be zero. The two branch predicates therefore select the same states in exact arithmetic for these inputs. This conclusion does not permit treating zero arbitrarily after changing the input domain or the stored expression; overflow can also invalidate the exact-arithmetic argument.
Quick check
(For radius two, enumerate the representatives and their distinct orbits. Then translate the result to . How many writes result if an implementation naively emits all eight entries for each representative, and how many distinct centers are actually intended?)
Trace the recurrence; each representative owns an orbit of at most eight points.
Solution · Guided solution
The representatives are with and with . The next state is crossed and omitted. The first orbit is . The second is . Add to each pair to obtain the intended translated centers: and . Naive eight-entry emission makes sixteen writes; the specified set contains twelve distinct centers.
Quick check
(Prove that there is at most one diagonal representative, and that the last representative has gap either zero or one. Explain why appending the first crossed state duplicates an already owned orbit.)
Track the gap move by move.
Solution · Guided solution
A diagonal representative immediately terminates the loop, so another cannot follow it. If the loop exits through a crossed state, its previous gap was a positive integer and the update subtracted either one or two. A negative result is possible only by subtracting two from one. Thus the last emitted state is and the crossed state is ; they have the same ordered absolute coordinates and hence the same orbit. If the loop stops on the diagonal the last gap is zero. These are the only stopping cases by the termination proof.
Quick check
(A translucent source is blended twice over transparent black using premultiplied source-over, with source alpha . Compute the resulting alpha and explain why duplicate elimination matters even when the final integer coordinate is unchanged.)
Apply repeatedly.
Solution · Guided solution
Source-over updates alpha by . The first write gives ; the second gives . More generally, repeated writes give by induction. Repeatedly emitting one axis or diagonal center can therefore darken or strengthen a translucent outline. Removing duplicates is part of output ownership, rather than merely a storage optimization.