Skip to content
AfluidityAlgorithm Atlas
RenderingAll categories
CoreConcept & Pseudocode EntryAI Reviewed (ai-reviewed)

Midpoint Circle Algorithm

Rasterizes a circle of integer radius R onto a 2D pixel grid using 8-way octant symmetry and integer-only midpoint decision arithmetic without square roots or trigonometry.

Explore relationshipsOpen 3D GraphBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Rendering
Difficulty
Beginner
Family
Rasterization & Scan Conversion
Tier
Core
Status
Reviewed
Review
AI Reviewed
Sources
1
Formulas
1
Relationships
1
Code example
Not ready
Visualization
Ready
Aliases
Bresenham's Circle Algorithm, Integer Circle Rasterization

Overview

The Midpoint Circle Algorithm (Bresenham's circle algorithm) steps x from 0 to y along a single 45-degree octant of a circle of radius R, maintaining an integer decision variable d = 1 - R that tests whether the midpoint between candidate pixels (x+1, y) and (x+1, y-1) lies inside or outside x^2 + y^2 = R^2. Each computed (x, y) is mirrored across all 8 octants.

Core Concepts

8-way octant symmetryimplicit circle function x^2 + y^2 - R^2integer midpoint decision variableincremental second differences

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(R)

Average

O(R)

Worst

O(R)

Space

O(1) auxiliary

Interactive Runtime & Memory Budget Calculator

Estimate wall-clock latency, operation count, and working memory for Midpoint Circle Algorithm across input scales.

Input Scale N:
JIT-compiled JS/TS (~350M primitive ops/sec)
Est. Average TimeO(R)

428.6 µs

60 FPS Frame-Safe (<16ms)~150.0k ops
Est. Worst-Case TimeO(R)

428.6 µs

60 FPS Frame-Safe (<16ms)~150.0k ops
Est. Working MemoryO(1) auxiliary

128 B

L2/L3 Cache FriendlyN=100,000

When to Use

  • Use the Midpoint Circle Algorithm when you need fast, exact, integer-only rasterization of a circle on a pixel grid or tilemap without trig functions or square roots.
  • Use it alongside Bresenham's Line Algorithm for software 2D shape rasterization.

When Not to Use

  • Avoid when smooth anti-aliased subpixel circle edges are required; use Xiaolin Wu's circle algorithm or signed distance field (SDF) fragment shading instead.

What It Does

  • Plots all discrete grid pixels of a circle of radius R centered at (cx, cy) using only integer additions and shifts
  • Exploits 8-way octant symmetry so only one 45-degree arc (0 <= x <= y) is computed

Use Cases

  • Drawing circles, rings, and circular brushes in 2D bitmap editors and software rasterizers
  • Computing discrete circular field-of-view and AoE radii on 2D game tilemaps
  • Embedded microcontroller display graphics without floating-point hardware

Inputs

  • Integer center coordinates (cx, cy) and integer radius R >= 0

Outputs

  • Set of rasterized integer pixel coordinates (x, y) forming the circle perimeter

Key Formulas (1)

Midpoint Decision Update

d_{next} = d + 2x + 1 (if d < 0); d_{next} = d + 2(x − y) + 1 (if d ≥ 0)
d_{next} = d + 2x + 1 (if d < 0); d_{next} = d + 2(x - y) + 1 (if d >= 0)

Incremental integer update of f(x + 1, y - 0.5) = (x + 1)^2 + (y - 0.5)^2 - R^2.

Pseudocode

  1. 1.Initialize x = 0, y = R, decision parameter d = 1 - R
  2. 2.While x <= y:
  3. 3. Plot the 8 symmetric points (cx +/- x, cy +/- y) and (cx +/- y, cy +/- x)
  4. 4. Increment x += 1
  5. 5. If d < 0: set d += 2 * x + 1
  6. 6. Else: decrement y -= 1 and set d += 2 * (x - y) + 1

Algorithmic Specification & Pseudocode

Concept & Pseudocode Entry

This entry is part of the 1,000-algorithm concept catalog and provides high-level pseudocode, complexity bounds, and relationship links rather than a standalone in-browser benchmark engine.

⚡ Explore 63 Live Benchmarked Implementations →

Structured Execution Steps

  1. Initialize x = 0, y = R, decision parameter d = 1 - R
  2. While x <= y:
  3. Plot the 8 symmetric points (cx +/- x, cy +/- y) and (cx +/- y, cy +/- x)
  4. Increment x += 1
  5. If d < 0: set d += 2 * x + 1
  6. Else: decrement y -= 1 and set d += 2 * (x - y) + 1

Canonical Example

Input
Center = (0, 0), Radius R = 5
Output
First octant points: (0, 5), (1, 5), (2, 5), (3, 4), (4, 3), mirrored to 8 octants
Explanation
Starting at (0, 5) with d = -4, the integer decision variable steps along x and decrements y at x = 3.

Implementation Notes

  • Initialize x = 0, y = R, d = 1 - R; at each step increment x and update d += 2*x + 1 (if d < 0) or d += 2*(x - y) + 1 after decrementing y.

Common Pitfalls

  • Emitting duplicate pixels at the cardinal (x = 0) and diagonal (x = y) octant boundaries when plotting 8 symmetric points.
  • Using floating-point sqrt(R^2 - x^2) per column, which leaves gaps where the circle slope exceeds 1.

Interactive Mechanism Walkthrough & State Debugger

Spatial Primitive & Sweep-Line Canvas
Midpoint Circle Algorithm mechanism walkthrough step 1 of 6
sweep-line Xx = 60px
active hull vertices2
orientation testccw(p, q, r) > 0
invariantUpper/Lower Envelope
Step 1 of 6: Initialize x = 0, y = R, decision parameter d = 1 - R

Sources (1)

What each reference supports for this entry.

Bresenham (1977) — A Linear Algorithm for Incremental Digital Display of Circular Arcs

Paper

CACM paper deriving integer incremental rasterization of circular arcs.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
Conceptual neighborBresenham's Line Algorithm

Rendering · Foundation

Applies Bresenham's integer midpoint error accumulation to second-degree circular curves with 8-way symmetry.

Compare with this

Relationships

View full relationship page
Conceptual neighborBresenham's Line Algorithm

Applies Bresenham's integer midpoint error accumulation to second-degree circular curves with 8-way symmetry.

Related Algorithms

Bresenham's Line AlgorithmRasterizationZ-Buffering

Tags

RasterizationRenderingGeometryInteger Only