Bresenham's Line Algorithm

Every line on a computer screen is a lie. A mathematical line is a continuous, infinitely thin ribbon of points. A screen is a grid of square pixels. Drawing a line means deciding which pixels to light up — and making that choice so quickly that the result looks smooth.

In 1962, IBM engineer Jack Bresenham was working with a pen plotter at IBM's San José Research Laboratory. Floating-point arithmetic was expensive — or simply unavailable — on the hardware of the day. He needed to trace a straight path across a grid using only the cheapest operation a digital circuit can do: integer addition.

The insight he found is almost embarrassing in its simplicity: instead of computing the exact y-coordinate for every x-step (which requires division), track the accumulated error between the true line and the chosen pixel row. Each step you just add a constant, then check whether the error has crossed a threshold. If it has, step up a row and subtract the threshold. No division, no floating point — just addition and a sign check.

The result is an algorithm that is $O(n)$ in the number of pixels and provably optimal: it touches exactly the pixels that best approximate the line, and nothing else.

Drag the endpoints on the pixel grid below. The algorithm updates instantly, lighting only the pixels Bresenham's integer-addition loop chooses.

<p class="hint">{{hint}}</p>
<div class="layout">
  <canvas id="grid" width="280" height="280"></canvas>
  <div class="panel">
    <div class="info-row"><span class="dot start-dot"></span> {{start_label}} <span id="p0"></span></div>
    <div class="info-row"><span class="dot end-dot"></span> {{end_label}} <span id="p1"></span></div>
    <div class="info-row">{{pixels_lit}} <span id="count"></span></div>
    <div class="divider"></div>
    <div class="label">{{step_log_label}}</div>
    <div id="log" class="log"></div>
    <div class="divider"></div>
    <button id="toggle" type="button">{{show_naive}}</button>
  </div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.layout { display: flex; gap: 1rem; align-items: flex-start; flex-wrap: wrap; }
canvas { border: 1px solid #cdd9e3; border-radius: 6px; cursor: crosshair; touch-action: none; }
.panel { flex: 1; min-width: 160px; font-size: .82rem; }
.info-row { display: flex; align-items: center; gap: .35rem; margin-bottom: .35rem; }
.dot { display: inline-block; width: 10px; height: 10px; border-radius: 50%; }
.start-dot { background: #2e9e4f; }
.end-dot { background: #c92f3c; }
.divider { border-top: 1px solid #dde3ea; margin: .5rem 0; }
.label { font-weight: 600; font-size: .78rem; color: #555; margin-bottom: .25rem; }
.log { font-family: ui-monospace, monospace; font-size: .72rem; color: #333; line-height: 1.6; }
button { font: 600 13px system-ui; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 6px; cursor: pointer; margin-top: .4rem; }
button.active { background: #fff; color: #1d3557; }

// Code not found

Watch how the algorithm never revisits a column: it advances exactly one step in x each iteration, updating y only when the accumulated error demands it. The error variable is the heart of the trick — it accumulates the slope and discharges in whole-pixel steps, keeping everything in the integer domain. Compare the Bresenham and naive float columns on the side panel: they agree on which pixels to light, but one does it with a single integer add per step.

How fast can you possibly draw a line on a pixel grid?

• Lower bound: you must visit at least Δx pixels (one per column, for a line with horizontal extent Δx). Any correct algorithm is Ω(n).
• Bresenham: exactly Δx iterations, each doing two integer additions and one comparison. Total work: $O(n)$. It matches the lower bound.
• Status: solved — the algorithm is provably optimal in the number of arithmetic operations needed to rasterize a line segment under the standard pixel-grid model (Bresenham, 1965).

The deeper insight is what made it fast. The naive approach computes y = round(x * dy/dx) at every step — requiring a multiplication and a division. Bresenham noticed that consecutive y-values differ by at most 1. So he replaced the exact computation with an incremental error accumulator:

error = 2*dy - dx
for each x from x0 to x1:
    plot(x, y)
    if error > 0:
        y += 1
        error -= 2*dx
    error += 2*dy

Every variable stays an integer. The multiplications by 2 are just left-shifts. On 1960s hardware — and on modern CPUs where integer ops are faster than floating-point — this is as lean as it gets.

Bresenham later generalized the same idea to circles and ellipses (the midpoint circle algorithm), and the error-accumulator pattern appears throughout computational geometry whenever you need to walk a curve on a grid efficiently. See also sorting lower bounds for another example of proving an algorithm optimal by matching a lower bound.

"Convert a continuous line into discrete steps with no fractions" is a problem that appears everywhere coordinates meet a grid:

• GPU rasterization pipelines: every triangle that reaches your screen is broken into horizontal spans using a variant of Bresenham's incremental method. The scan-line fill algorithm is a direct descendant.
• Font rendering: TrueType and PostScript outlines are curved, but they are drawn onto a pixel grid. Rasterizers use Bresenham-style stepping along Bézier curves to decide which pixels fall inside a glyph.
• CNC machining and 3-D printing: a CNC mill moves a cutter from point A to point B in discrete motor steps. The stepper-motor controller runs a Bresenham variant to distribute horizontal and vertical steps evenly along the path — exactly the same problem, just with motors instead of pixels.
• Robotics path planning: differential-drive robots that step left/right motors independently use Bresenham to approximate a straight trajectory on a discrete step grid.
• Medical imaging: drawing lines on CT or MRI voxel grids to measure distances, segment regions, or trace vessel centerlines relies on 3-D generalizations of the algorithm.

The unifying idea is incremental integer arithmetic: whenever you need to walk a geometric path across a discrete grid without accumulating floating-point error, you reach for the pattern Bresenham identified in 1962.

Bresenham's algorithm is a small masterpiece of algorithmic thinking: it took a problem that felt like it needed floating-point arithmetic, found the right invariant (the accumulated error), and reduced the whole computation to a single integer addition per pixel.

It is $O(n)$ and provably optimal — you cannot rasterize a line in fewer operations. It was fast on the hardware of 1962, and it is still the foundation of rasterization pipelines inside every GPU shipping today.

The lesson is not that integer arithmetic is always better. It is that the right abstraction — tracking error instead of recomputing exact position — can eliminate an entire class of expensive operations. See closest pair of points for another case where the right geometric insight collapses the apparent complexity.