A contour line looks continuous after it is drawn.

The data underneath is usually not continuous. It is a grid of samples:

f[i, j]

Marching squares is the little algorithm that stands between those two facts. It walks cell by cell, asks which corners are above an isovalue, and emits short line segments where the contour crosses cell edges.

Most cells are boring. Two are not.

The 16-Case Contract

Take one grid cell with four scalar values:

tl ---- tr
|      |
|      |
bl ---- br

For an isovalue \(\alpha\), each corner becomes a bit:

corner >= alpha  ->  inside
corner <  alpha  ->  outside

Four bits create 16 cases. If one corner is inside, the contour enters through one incident edge and leaves through the other. If two adjacent corners are inside, the contour crosses the two opposite edges. If all or no corners are inside, there is no segment inside the cell.

The edge crossing is placed by linear interpolation. On an edge with endpoint values \(a\) and \(b\), the fraction from \(a\) to \(b\) is

\[t = {\alpha-a \over b-a}.\]

This is the same local recipe that made marching cubes famous in 3D. Lorensen and Cline’s 1987 paper framed the method as a case-table algorithm: classify cube vertices against a constant density, look up intersected edges, and place surface vertices with linear interpolation.1 Marching squares is the 2D version of that idea.

But a case table only knows corner signs.

The Ambiguous Cases

The trouble cases are the diagonals:

case 5:   in  out       case 10:  out in
          out in                  in  out

Both have four edge crossings. Both can be connected in two ways:

connect like /        or        connect like \

The corner signs alone do not tell you which connection matches the continuous field inside the cell. A hard-coded diagonal is a topology decision disguised as a lookup-table entry.

One common repair is to look at the bilinear patch implied by the four samples:

\[f(x,y)=a+bx+cy+dxy.\]

That patch agrees with linear interpolation on each cell edge, but it has an interior shape. The asymptotic-decider idea of Nielson and Hamann was introduced for marching cubes ambiguity, using the interpolant’s asymptotic behavior to choose a consistent topology.2 In two dimensions, the same principle becomes very visible: inspect the bilinear saddle or center behavior instead of pretending that a four-bit case number is enough.

Lab: One Cell Gets A Vote

The lab below implements marching squares on a deterministic scalar field. It does four things:

  • samples a scalar field on an \(n \times n\) cell grid;
  • classifies every cell into one of 16 cases;
  • places contour endpoints by edge interpolation;
  • resolves cases 5 and 10 with either an asymptotic decider, a fixed diagonal, or a simple center-value rule.

The default field is the bilinear saddle

\[f(x,y)=32(x-0.5)(y-0.5)\]

with a 17-by-17 cell grid and isovalue 0.01. That intentionally places the saddle inside one cell rather than exactly on a grid line. The central cell is case 5:

Corner Value
bottom-left 0.0276816609
bottom-right -0.0276816609
top-right 0.0276816609
top-left -0.0276816609

The bilinear saddle value is 0, below the isovalue, so the decider chooses the low-center branch.

Ordinary contour segment Ambiguous-cell segment Case 5 or 10 Above isovalue Below isovalue

Bilinear saddle at iso 0.01 using asymptotic decider. Cases 5 and 10 are the cells where one bit table needs an extra diagonal rule.

What The Counts Hide

The default audit row is:

Field Rule Cells Active cells Segments Ambiguous Decider high/low Max endpoint residual
bilinear saddle asymptotic decider 289 33 34 1 0 / 1 6.4e-17

If you switch from Asymptotic decider to Always / or Always \, the segment count does not change. That is the trap. The table still emits two segments for case 5, but it connects a different pair of edges. The metric that changed is topology, not count.

The broader audit grid checks several fields and rules:

Field Rule Resolution Cells Active Segments Ambiguous
bilinear saddle asymptotic decider 17 289 33 34 1
bilinear saddle always / 17 289 33 34 1
bilinear saddle always \ 17 289 33 34 1
two hills asymptotic decider 24 576 48 48 0
soft ring asymptotic decider 26 676 136 140 4
ripple field cell-center sign 22 484 142 142 0

The exported audit verifies grid dimensions, case histogram accounting, ambiguous-cell counting, finite segment endpoints, unit-square endpoint bounds, and that every interpolated endpoint evaluates back to the isovalue within floating-point tolerance.

To reproduce the deterministic audit grid from the repository root:

node - <<'NODE'
const lab = require("./assets/js/marching-squares-lab.js");
const EXPECTED_CASE_SHAPE = [
  "1:saddle:decider:0.01:17:0:19:289/33/34/1:0/1:6.418e-17:9",
  "2:saddle:slash:0.01:17:0:19:289/33/34/1:0/1:6.418e-17:8",
  "3:saddle:backslash:0.01:17:0:19:289/33/34/1:0/1:6.418e-17:8",
  "4:hills:decider:0:24:0.08:33:576/48/48/0:0/0:1.388e-17:7",
  "5:ring:decider:0:26:0:41:676/136/140/4:0/4:6.939e-18:8",
  "6:waves:center:0.1:22:0.12:57:484/142/142/0:0/0:2.776e-17:7"
];
const EXPECTED_CASE_ROWS = [
  "1:saddle:decider:iso=0.01:grid=17:cells=289/33/34/1:decisions=0/1:residual=6.418e-17:checks=9/9:failed=none:passed=true",
  "2:saddle:slash:iso=0.01:grid=17:cells=289/33/34/1:decisions=0/1:residual=6.418e-17:checks=8/8:failed=none:passed=true",
  "3:saddle:backslash:iso=0.01:grid=17:cells=289/33/34/1:decisions=0/1:residual=6.418e-17:checks=8/8:failed=none:passed=true",
  "4:hills:decider:iso=0:grid=24:cells=576/48/48/0:decisions=0/0:residual=1.388e-17:checks=7/7:failed=none:passed=true",
  "5:ring:decider:iso=0:grid=26:cells=676/136/140/4:decisions=0/4:residual=6.939e-18:checks=8/8:failed=none:passed=true",
  "6:waves:center:iso=0.1:grid=22:cells=484/142/142/0:decisions=0/0:residual=2.776e-17:checks=7/7:failed=none:passed=true"
];
const EXPECTED_FIELD_SHAPE = [
  "hills:1 cases/7 checks:576/48/48/0:1.388e-17",
  "ring:1 cases/8 checks:676/136/140/4:6.939e-18",
  "saddle:3 cases/25 checks:867/99/102/3:6.418e-17",
  "waves:1 cases/7 checks:484/142/142/0:2.776e-17"
];
const EXPECTED_RULE_SHAPE = [
  "backslash:1 cases/8 checks:289/33/34/1:6.418e-17",
  "center:1 cases/7 checks:484/142/142/0:2.776e-17",
  "decider:3 cases/24 checks:1541/217/222/5:6.418e-17",
  "slash:1 cases/8 checks:289/33/34/1:6.418e-17"
];
const EXPECTED_CRITICAL_SHAPE = [
  "ambiguous count agrees:6/6",
  "cell count:6/6",
  "decider records all ambiguous votes:2/2",
  "grid dimensions:6/6",
  "histogram count:6/6",
  "residual finite:6/6",
  "saddle field has ambiguous cells:3/3",
  "segment endpoints stay in unit square:6/6",
  "segments finite:6/6"
];
const EXPECTED_CASES = EXPECTED_CASE_SHAPE.length;
const EXPECTED_CHECKS = EXPECTED_CASE_SHAPE.reduce((sum, row) => {
  const parts = row.split(":");
  return sum + Number(parts[parts.length - 1]);
}, 0);

function sameList(actual, expected) {
  return actual.length === expected.length &&
    actual.every((value, index) => value === expected[index]);
}

function caseShape(row) {
  return `${row.caseId}:${row.field}:${row.ambiguity}:${row.iso}:` +
    `${row.resolution}:${row.noise}:${row.seed}:` +
    `${row.cells}/${row.activeCells}/${row.segments}/${row.ambiguous}:` +
    `${row.highDecisions}/${row.lowDecisions}:` +
    `${row.maxResidual.toExponential(3)}:${row.totalChecks}`;
}

function caseRow(row) {
  return `${row.caseId}:${row.field}:${row.ambiguity}:iso=${row.iso}:` +
    `grid=${row.resolution}:` +
    `cells=${row.cells}/${row.activeCells}/${row.segments}/${row.ambiguous}:` +
    `decisions=${row.highDecisions}/${row.lowDecisions}:` +
    `residual=${row.maxResidual.toExponential(3)}:` +
    `checks=${row.passedChecks}/${row.totalChecks}:` +
    `failed=${row.failedChecks.length ? row.failedChecks.join("|") : "none"}:` +
    `passed=${row.passed}`;
}

function rowDrifts(actual, expected) {
  return {
    missing: expected.filter((row) => !actual.includes(row)),
    extra: actual.filter((row) => !expected.includes(row))
  };
}

function hasRowDrift(drift) {
  return drift.missing.length > 0 || drift.extra.length > 0;
}

function aggregateShape(row, key) {
  return `${row[key]}:${row.cases} cases/${row.totalChecks} checks:` +
    `${row.cells}/${row.activeCells}/${row.segments}/${row.ambiguous}:` +
    row.maxResidual.toExponential(3);
}

function criticalShape(row) {
  return `${row.check}:${row.passed}/${row.total}`;
}

const audit = lab.auditGrid();
const failed = audit.cases.filter(
  (row) => !row.passed || row.passedChecks !== row.totalChecks
);
const shape = {
  cases: audit.cases.map(caseShape),
  caseRows: audit.cases.map(caseRow),
  byField: audit.byField.map((row) => aggregateShape(row, "field")),
  byRule: audit.byRule.map((row) => aggregateShape(row, "ambiguity")),
  criticalChecks: audit.criticalChecks.map(criticalShape)
};
const caseRowDrifts = rowDrifts(shape.caseRows, EXPECTED_CASE_ROWS);
const shapeErrors = [
  ["cases", shape.cases, EXPECTED_CASE_SHAPE],
  ["caseRows", hasRowDrift(caseRowDrifts) ? shape.caseRows : EXPECTED_CASE_ROWS, EXPECTED_CASE_ROWS],
  ["byField", shape.byField, EXPECTED_FIELD_SHAPE],
  ["byRule", shape.byRule, EXPECTED_RULE_SHAPE],
  ["criticalChecks", shape.criticalChecks, EXPECTED_CRITICAL_SHAPE]
].filter((row) => !sameList(row[1], row[2]))
  .map(([name, actual, expected]) => ({ name, actual, expected }));

console.table(audit.cases.map((row) => ({
  field: row.field,
  rule: row.ambiguity,
  resolution: row.resolution,
  cells: row.cells,
  active: row.activeCells,
  segments: row.segments,
  ambiguous: row.ambiguous,
  decisions: `${row.highDecisions}/${row.lowDecisions}`,
  residual: row.maxResidual.toExponential(1),
  passed: row.passed
})));
console.table(audit.byField);
console.table(audit.byRule);
console.table(audit.criticalChecks);
const summary =
  `${audit.passed}/${audit.total} cases and ${audit.passedChecks}/${audit.totalChecks} checks passed`;
if (
  shapeErrors.length ||
  failed.length ||
  !audit.ok ||
  audit.checked !== EXPECTED_CHECKS ||
  audit.total !== EXPECTED_CASES ||
  audit.totalChecks !== EXPECTED_CHECKS ||
  audit.passed !== audit.total ||
  audit.passedChecks !== audit.totalChecks
) {
  throw new Error(JSON.stringify({
    summary,
    shapeErrors,
    caseRowDrifts,
    shape,
    failed,
    errors: audit.errors,
    totals: {
      checked: audit.checked,
      total: audit.total,
      passed: audit.passed,
      passedChecks: audit.passedChecks,
      totalChecks: audit.totalChecks
    }
  }, null, 2));
}
console.log(summary);
NODE

The Diagonal Is Not A Styling Choice

The ambiguous cases are sometimes explained as a drawing nuisance. That makes them sound cosmetic. They are not.

A contour is often used as data:

  • a coastline in a map tile;
  • a medical boundary on a slice;
  • an isobar in a weather field;
  • a collision shape;
  • a thresholded probability region;
  • a mesh cross-section.

In those settings, the diagonal decides connectivity. Two regions may become one region. One hole may become two holes. A later simplifier or polygonizer will inherit that decision as if the samples had proved it.

The honest statement is:

the corners identify edge crossings;
the interpolation model chooses the interior topology

If the interpolation model is bilinear, the asymptotic decider is a principled local rule. If the data is categorical, aliased, quantized, or semantically piecewise-constant, a bilinear rule may be the wrong story. The cell still needs an extra promise; it is just not always the same promise.

Sampling Is Not A Shape

Marching squares is local. It does not know whether the real field had a thin loop entirely inside a cell, a sharp corner between samples, or two features that crossed between grid lines. No diagonal rule can recover information that was never sampled.

That limitation is not a failure of the algorithm. It is the sampling contract coming due. The method can be exact for the piecewise interpolation model you chose; it cannot certify the unsampled world behind the grid.

When I see a contouring system in production, I want four answers:

  • What interpolation model is the contour claiming?
  • How are cases 5 and 10 resolved?
  • Are equality cases handled deterministically?
  • Are topology-sensitive downstream steps tested under grid shifts and isovalue perturbations?

A contour line is not just ink. It is a sequence of local topology decisions. Most cells have one obvious crossing. Some cells have two diagonals, and the code has to admit which one it chose.

Sources

  1. William E. Lorensen and Harvey E. Cline, “Marching Cubes: A High Resolution 3D Surface Construction Algorithm”, Computer Graphics 21(4), SIGGRAPH 1987. The paper presents a case-table method for constant-density surfaces, scan-line processing, and linear interpolation of edge intersections. ↩

  2. Gregory M. Nielson and Bernd Hamann, “The Asymptotic Decider: Resolving the Ambiguity in Marching Cubes”, IEEE Visualization 1991. The method addresses ambiguous marching-cubes topology by using the interpolation behavior inside the cell rather than only the vertex sign pattern. ↩