My contour tracer ran fine. The polygons it produced closed properly, had a sensible number of points, and drew as recognisable shapes. The only problem was area — it reported regions twenty times larger than they actually were.
The bug was in the termination condition, and it was an ordering mistake that only surfaces on particular shapes.
What the tracer is actually doing
The input is a binary mask: some pixels belong to the target region, the rest are background. Turning that into vector graphics means extracting each connected region’s boundary as an ordered list of points and joining them into a polygon.
Moore-neighbourhood tracing works the way you solve a maze by hand: keep one hand on the wall and you will come back to where you started. On a pixel grid that means:
Scan to find the topmost-leftmost pixel of the region as the start — chosen because it is guaranteed to be on the boundary, with background above and to its left. Then every step does the same thing: stand on the current boundary pixel, begin at the position just past the direction you arrived from, and check the eight neighbours clockwise; the first one belonging to the region is your next step.
Starting the scan from the arrival direction is the crucial part. Scanning from a fixed direction (due east, say) makes the tracer go wrong at concave corners — it needs to know where it came from in order to keep hugging the wall instead of turning into the region’s interior.
7 0 1 neighbour indices (clockwise)
6 · 2 · is the current pixel
5 4 3So the state at each step is a pair: position and direction. That direction is simultaneously the result of the last step and the starting point for the next scan. That is exactly where this went wrong.
The termination condition in Moore-neighbourhood tracing
To walk the boundary of a connected region, the standard approach is Moore-neighbourhood tracing: stand on the current boundary pixel, start from the direction you entered by, scan clockwise around the eight neighbours until you find another pixel of the region, step onto it, repeat.
The question is when to stop. The naive answer is “when you return to the start”, which is not enough — some shapes pass through the start pixel mid-walk. A dumbbell with a thin neck does it, so does a one-pixel-wide spur that the tracer walks out along and back. Stopping there yields half a contour.
The correct condition is Jacob’s stopping criterion: you must return to the start pixel and enter it travelling in the same direction you first left it in. Position and direction must both match before the loop is genuinely complete.
My implementation had both conditions. In the wrong order.
The mistake
The loop body looked roughly like this:
while (true) {
// check whether we are back at the start with a matching direction
if (x === startX && y === startY && dir === startDir) break;
next = findNextBoundaryPixel(x, y, dir);
x = next.x; y = next.y;
dir = next.dir; // direction updated only after the check
points.push([x, y]);
}The check runs before the move, using the dir left over from the previous iteration. So at the moment the tracer stands on the start pixel, the direction it holds describes how it arrived, not how it is about to leave.
Those two directions usually differ. The condition therefore almost never fires, and the tracer does not stop at the end of the first loop — it goes round a second time, and a third, until it hits the iteration cap.
Why the area inflates twentyfold
Here is the counter-intuitive part: walking extra laps should only add points. It should not change the area.
What matters is where it stops. The tracer is ultimately killed by the point cap, which leaves it at an arbitrary position on the contour rather than at the start. The resulting point list is therefore not closed — a stretch of real boundary sits between its last point and its first.
Downstream, the area calculation (the shoelace formula) joins first to last and treats that as closure. That artificial edge can cut straight across the region, enclosing a large area that was never part of it. The thinner and longer the shape, and the wider the gap, the worse the inflation.
The twentyfold case was a long thin arm: the tracer stopped near the wrist, and the closing edge ran clean across the torso.
It also explained a second symptom I had not connected — some regions were traced along their top edge only. That is the case where the leftover direction happens to equal the start direction: the tracer has just finished running along the top, the condition fires immediately, and a single edge is all you get.
The fix
Move the check after the direction update:
while (true) {
next = findNextBoundaryPixel(x, y, dir);
x = next.x; y = next.y;
dir = next.dir; // update direction first
// then check: position and *departure* direction must both match
if (x === startX && y === startY && dir === startDir) break;
points.push([x, y]);
}Three lines reordered. Afterwards every region’s traced bounding box matched the region’s own bounding box, off by the single pixel that outer-edge tracing normally introduces.
Why the shoelace formula is fooled
Area comes from the shoelace formula: pair up consecutive vertices, sum the cross products, halve the result.
let area = 0;
for (let i = 0; i < pts.length; i++) {
const [x1, y1] = pts[i];
const [x2, y2] = pts[(i + 1) % pts.length]; // last point wraps to first
area += x1 * y2 - x2 * y1;
}
area = Math.abs(area) / 2;Note the % pts.length: it joins the last point back to the first unconditionally. That is correct when the polygon is genuinely closed — first and last coincide, the edge has zero length, and it contributes nothing.
When the point list is not closed, that edge is a real and possibly long segment. The shoelace formula makes no demands about whether a polygon is sensible; it mechanically computes an algebraic sum for whatever shape you hand it.
Worse, if that artificial edge makes the polygon self-intersecting, the formula returns signed areas that partly cancel. The result can be too large, too small, or close enough to correct to hide the problem entirely. Twentyfold is simply the number I happened to get; there is no rule to it.
Why the unit tests missed it
I had unit tests for the tracer, using rectangles and circles. Neither shape can trigger this bug.
They are too “fat”: the tracer never walks into a one-pixel-wide dead end, and after an extra lap the arrival and departure directions at the start pixel tend to coincide anyway, so the condition fires more or less by accident. All green.
What actually triggers it are long thin shapes with branches — a character’s arm, strands of hair, folds in clothing. Those have many one-pixel protrusions that the tracer must walk into and back out of, producing a far more complicated direction sequence.
The lesson is that geometry tests must include pathological shapes: one-pixel lines, thin-necked dumbbells, regions with holes, single-pixel regions. Green lights from rectangles and circles only tell you it works in the easiest possible case.
Holes: the shoelace formula’s sign does the work for you
Everything above concerns outer contours. Real character layers frequently have holes — gaps in a sleeve, cut-outs for eyes, the inner ring of a letter O. Moore-neighbourhood tracing finds only the outer contour, so holes need separate handling or the computed area includes them.
Conveniently, the shoelace formula solves this itself: it produces a signed area whose sign follows the winding direction. If an outer contour traced clockwise yields a positive value, tracing holes counter-clockwise yields negative values, and simply summing gives the correct net area.
area = shoelace(outer) # clockwise, positive
for hole in holes:
area += shoelace(hole) # counter-clockwise, negative -- add, don't subtractNo “if this is a hole, subtract” branch is needed. Letting the winding direction carry that information is less error-prone than tracking it in a boolean flag — direction falls out of the tracing process naturally, whereas a flag has to be maintained by hand.
SVG path uses the same convention: write the outer contour and its holes into one d attribute and pair it with fill-rule="evenodd" or nonzero, and the renderer punches the holes out. The former counts crossing parity, the latter the signed sum of winding directions — so if your hole directions are reversed, evenodd still looks right while nonzero fills the holes in. That makes a good self-check: if the two rules render differently, a direction is wrong.
Pick complementary connectivity; do not use 8 on both sides
One choice has to be settled before tracing begins: whether pixel adjacency means 4-connectivity (edges only) or 8-connectivity (including diagonals).
It is not an arbitrary pick. The classic connectivity paradox: in a 2×2 checkerboard pattern, two foreground pixels touch only diagonally and so do the two background pixels. If both foreground and background use 8-connectivity, the foreground is connected and so is the background — a closed curve has failed to separate the plane into inside and outside, which is topologically contradictory.
The fix is to make them complementary: 8-connectivity for foreground and 4 for background, or the reverse. Diagonally touching foreground counts as connected while diagonally touching background does not, and the contradiction disappears.
The practical consequence is immediate. With 8-connectivity on the foreground, two regions meeting at a corner are treated as one and the tracer runs around both; with 4-connectivity they yield two separate contours. For line art and thin strokes, 8-connectivity is close to mandatory — a one-pixel diagonal line reads as a string of isolated points under 4-connectivity.
So the configuration should expose one switch with the other derived from it, rather than two independent parameters — the latter lets a user configure exactly the contradictory combination above, and the symptom (contours occasionally merging or breaking for no apparent reason) is very hard to diagnose.
How to catch this sooner
The bug survived my initial checks because its output looks correct: closed polygons, plausible point counts, coherent rendered shapes. Eyeballing the contour drawing reveals nothing.
There is exactly one check that catches it, and it is cheap: compare the bounding box of the traced contour against the bounding box of the region it is supposed to describe.
Those two numbers come from independent paths — the region box from connected-component labelling, the contour box from the point list. A correct contour forces them to agree; a runaway or truncated trace shows up immediately.
Stated more generally: validate geometric output against an invariant computed by a different route, rather than by looking at it. Area, bounding box, point-count bounds, closure — all of these can be checked automatically, and “it looks right” proves nothing.
The other thing worth recording is that top-edge symptom. I had filed it as a separate minor defect to look at later. It was in fact the same bug seen from another angle — the same termination condition firing early instead of late, depending on the shape. Triaging two anomalies separately is a good way to miss the cause they share.
A shattered mask is precisely the input that breaks contour tracing. To watch one come apart, open the soft mask threshold lab and push the noise past 0.12 while watching connectivity.