Midpoint Line Drawing Simulator

How Midpoint Line Drawing Simulator works

The midpoint algorithm — Bresenham's line algorithm in its implicit-function form — replaces DDA's floating-point accumulator with a single integer that answers one question per pixel: having just plotted (x, y), is the ideal line above or below the midpoint between the two candidate next pixels? Write the line as F(x, y) = dy·x − dx·y + c, which is zero on the line, negative above it and positive below. Evaluating F at the midpoint (x+1, y+½) gives the decision parameter d. If d is negative the midpoint lies above the line, so the line passes below it and the east pixel (x+1, y) wins; otherwise the north-east pixel (x+1, y+1) does. The clever part is that d can be updated incrementally: choosing east adds 2·dy, choosing north-east adds 2·(dy − dx). Every quantity is an integer, so there is no rounding and no drift. To keep one set of rules, lines from other octants are first mapped into zone 0 (0 ≤ slope ≤ 1, moving right), plotted, then mapped back.

Pseudocode

midpointLine(x1, y1, x2, y2):        // assumes zone 0: dx >= dy >= 0
    dx = x2 - x1
    dy = y2 - y1

    d = 2*dy - dx                     // F at the first midpoint, doubled
    incE  = 2*dy                      // chose East
    incNE = 2*(dy - dx)               // chose North-East

    x = x1
    y = y1
    plot(x, y)

    while x < x2:
        if d < 0:                     // midpoint above line -> East
            d = d + incE
        else:                         // midpoint below/on line -> North-East
            d = d + incNE
            y = y + 1
        x = x + 1
        plot(x, y)

// Other zones: swap and/or negate x,y to reach zone 0, run the above,
// then apply the inverse mapping to every plotted pixel.

Time and space complexity

Time

O(max(|dx|, |dy|)) — one iteration per pixel

Space

O(1)

Same pixel count as DDA, but each step is one integer comparison and one integer addition, with no multiplication or rounding inside the loop.

Worked example

Draw from (2, 3) to (10, 6) — zone 0 already. dx = 8, dy = 3. Initial d = 2·3 − 8 = −2. incE = 6, incNE = 2(3−8) = −10.

1. Startplot (2, 3), d = −2.
2. d = −2 < 0East. d += 6 → 4. plot (3, 3).
3. d = 4 ≥ 0North-East. d += −10 → −6. plot (4, 4).
4. d = −6 < 0East. d += 6 → 0. plot (5, 4).
5. d = 0 ≥ 0North-East. d += −10 → −10. plot (6, 5).
6. d = −10 < 0East. d += 6 → −4. plot (7, 5).
7. d = −4 < 0East. d += 6 → 2. plot (8, 5).
8. d = 2 ≥ 0North-East. d += −10 → −8. plot (9, 6).
9. d = −8 < 0East. d += 6 → −2. plot (10, 6). x = x2, stop.

Nine pixels from (2,3) to (10,6), every decision made with integer arithmetic only. d never needed a division and never left the integers.

Common exam mistakes

• Using d = dy − dx/2 and keeping the halves. Multiplying the whole decision function by 2 is what makes it integer — do it from the start.
• Applying zone-0 rules to a steep or leftward line without transforming it first. Slopes above 1 need x and y swapped, or y will fall behind.
• Getting the tie case wrong. When d = 0 the midpoint is exactly on the line; pick one convention (this version takes North-East) and use it consistently.
• Updating x inside only one branch. x advances every iteration in zone 0; only y is conditional.
• Forgetting to invert the zone transformation before plotting. The algorithm runs in zone 0 but the pixels must be written back in the original zone.

Frequently asked questions

Related simulators