Polygons and the Separating Axis

What You’ll Learn

If you can find one direction along which two shapes do not overlap, they miss.

That is the entire algorithm, and you have used it twice already without it having a name. Section 5.1’s box test is exactly this with the directions fixed to $x$ and $y$ : a gap on either axis proves a miss. What changes here is only which directions are worth trying.

For convex polygons the answer is short — the directions perpendicular to their edges — and that is where 2D earns its place in this Module. In three dimensions the candidate axes are the face normals of both shapes plus the cross product of every pair of edges: fifteen axes for two boxes, and the reason SAT has a reputation for being fiddly. In 2D there are no cross-product axes at all. Two triangles need six, and every one of them is an edge turned ninety degrees.

Shadows

Project a polygon onto a direction and you get a shadow: the lowest and highest it reaches along that direction. Dot every corner against the axis, keep the smallest and largest.

\text{shadow} = \left[\min_i (P_i \cdot \hat{n}),\ \max_i (P_i \cdot \hat{n})\right]

Only the corners need testing, and that is convexity paying for itself: every point of a convex polygon is a blend of its corners, so no interior point can reach further along any direction than the furthest corner already does. The build checks that by projecting a grid of interior points and confirming none escapes the corners’ shadow.

Then compare the two shadows with a range check — the same rangesOverlap from Section 5.1, doing its fourth job in three Sections: two boxes, two collinear segments, and now two polygon shadows.

Two polygons, every candidate axis, and the one that settles it

Drag and turn the triangle, then tick the box to see all eight axes at once.

The code that draws it src/lib/gamedev/demos/2d/separate.scene.ts

/** Two convex polygons, every candidate axis, and the shadows on the one that proves a miss. */
import {
  makeCanvas2D,
  addDragTargets,
  arrow,
  dot as fillDot,
  label,
  line,
} from "../canvas2d.ts";
// From `controls.ts`, not `ui.ts`: the latter imports Three.js and this track must not.
import { addCheckbox, addReadout, addSlider } from "../controls.ts";
import { candidateAxes } from "../../../gamedev2d/sat2d.ts";
import {
  BOUNDS,
  SPIN_RANGE,
  START,
  VIEW,
  fixedAt,
  movingAt,
  satReport,
  screenOf,
  shadowSegment,
  worldOf,
} from "./separate-shared.ts";
import type { MountFn } from "../runner.ts";

const FIXED_COLOUR = "#7d8590";
const MOVING_COLOUR = "#58a6ff";
const TOUCHING = "#f0883e";
const PROOF = "#7ee787";
const OTHER_AXIS = "#3b4552";
const PUSH = "#d2a8ff";
const DIM = "#636c76";

const mount: MountFn = (el) => {
  const { ctx, canvas, clear } = makeCanvas2D(el, VIEW.height);

  const show = addReadout(el);
  const note = addReadout(el);
  const px = addSlider(el, "x", -BOUNDS.x, BOUNDS.x, START.x, draw, "", 0.05);
  const py = addSlider(el, "y", -BOUNDS.y, BOUNDS.y, START.y, draw, "", 0.05);
  const spin = addSlider(
    el,
    "turn the triangle",
    SPIN_RANGE.min,
    SPIN_RANGE.max,
    0,
    draw,
    "\u00B0",
    1,
  );
  const spinFixed = addSlider(
    el,
    "turn the pentagon",
    SPIN_RANGE.min,
    SPIN_RANGE.max,
    0,
    draw,
    "\u00B0",
    1,
  );
  const showAll = addCheckbox(el, "show every candidate axis", false, draw);

  // Dragging is the natural way in; the sliders are the keyboard path to the same configuration.
  const stopDragging = addDragTargets(
    canvas,
    () => [screenOf({ x: px(), y: py() })],
    (_index, sx, sy) => {
      const world = worldOf(sx, sy);
      px.set(Math.min(Math.max(world.x, -BOUNDS.x), BOUNDS.x));
      py.set(Math.min(Math.max(world.y, -BOUNDS.y), BOUNDS.y));
      draw();
    },
  );

  function strokePolygon(
    poly: readonly { x: number; y: number }[],
    colour: string,
    width = 2.2,
  ) {
    ctx.save();
    ctx.strokeStyle = colour;
    ctx.lineWidth = width;
    ctx.beginPath();
    poly.forEach((p, i) => {
      const q = screenOf(p);
      if (i === 0) ctx.moveTo(q.x, q.y);
      else ctx.lineTo(q.x, q.y);
    });
    ctx.closePath();
    ctx.stroke();
    ctx.restore();
    for (const p of poly) {
      const q = screenOf(p);
      fillDot(ctx, q.x, q.y, 2.6, colour);
    }
  }

  function draw() {
    clear();
    const a = fixedAt(spinFixed());
    const b = movingAt({ x: px(), y: py() }, spin());
    const r = satReport(a, b);
    const origin = screenOf({ x: 0, y: 0 });

    /* Every candidate axis as a spoke through the origin, so "the axes are the edges turned ninety
       degrees" is something a reader can count rather than take on faith. */
    if (showAll()) {
      for (const axis of candidateAxes(a, b)) {
        line(
          ctx,
          { x: origin.x - axis.x * 200, y: origin.y + axis.y * 200 },
          { x: origin.x + axis.x * 200, y: origin.y - axis.y * 200 },
          OTHER_AXIS,
          { width: 1 },
        );
      }
    }

    /* The axis that settles it, with both shadows drawn along it. When they miss there is a visible gap
       between the two shadows, and that gap **is** the proof. */
    if (r.proof) {
      const axis = r.proof;
      line(
        ctx,
        { x: origin.x - axis.x * 220, y: origin.y + axis.y * 220 },
        { x: origin.x + axis.x * 220, y: origin.y - axis.y * 220 },
        PROOF,
        { width: 1.2, dashed: true },
      );
      for (const [poly, colour] of [
        [a, FIXED_COLOUR],
        [b, MOVING_COLOUR],
      ] as const) {
        const shadow = shadowSegment(poly, axis);
        // Offset the two shadows slightly apart so they can both be seen where they nearly meet.
        const across = { x: -axis.y, y: axis.x };
        const nudge = colour === FIXED_COLOUR ? 7 : -7;
        const from = screenOf(shadow.from);
        const to = screenOf(shadow.to);
        line(
          ctx,
          { x: from.x + across.x * nudge, y: from.y - across.y * nudge },
          { x: to.x + across.x * nudge, y: to.y - across.y * nudge },
          colour,
          { width: 4 },
        );
        // A tick at each end of the shape's own projection lines, joining shape to shadow.
        for (const end of [shadow.from, shadow.to]) {
          const q = screenOf(end);
          fillDot(
            ctx,
            q.x + across.x * nudge,
            q.y - across.y * nudge,
            3,
            colour,
          );
        }
      }
      label(
        ctx,
        "this axis separates them",
        origin.x + 10,
        origin.y - 10,
        PROOF,
      );
    }

    strokePolygon(a, FIXED_COLOUR);
    strokePolygon(b, r.hit ? TOUCHING : MOVING_COLOUR, 2.6);

    /* When they do overlap there is no proof to draw, so the shallowest axis is drawn instead - the
       direction Section 5.4 will push along. */
    if (r.hit && r.push) {
      const from = screenOf({ x: 0, y: 0 });
      arrow(
        ctx,
        from,
        {
          x: from.x + r.push.axis.x * r.push.depth * 42,
          y: from.y - r.push.axis.y * r.push.depth * 42,
        },
        PUSH,
        2.4,
      );
      label(ctx, "shallowest overlap", from.x + 12, from.y + 18, PUSH);
    }

    label(
      ctx,
      "drag the triangle \u00b7 every axis is one shape's edge, turned ninety degrees",
      12,
      VIEW.height - 10,
      DIM,
    );

    const offered = candidateAxes(a, b).length;
    show(
      `${offered} candidate axes, ${r.distinct} of them distinct \u00b7 ` +
        (r.hit
          ? `no axis separates them, so they overlap \u00b7 shallowest by ${r.push?.depth.toFixed(3)}`
          : `axis ${r.tried} of ${offered} already proved a miss`),
    );
    note(
      r.hit
        ? r.pushDisagrees
          ? "note the shallowest axis: with unnormalized axes the code would have chosen a different one here"
          : "every axis had to be checked before this could be said \u2014 overlapping is the expensive case"
        : "one axis with a gap is the whole proof, which is why the loop stops as soon as it finds one",
    );
  }

  draw();

  return stopDragging;
};

export default mount;

Watch the readout as you drag. When the shapes are apart, the first axis tried is often enough and the loop stops — at the opening position it is settled by axis 1 of 8. When they overlap, all eight have to be checked before you can say so. Overlapping is the expensive case, which is the opposite of what most people guess.

Why The Edges Are Enough

The claim deserves a reason rather than a rule. If two convex shapes are apart, there is a straight line you can draw between them. Slide that line toward one of the shapes until it cannot move any further and it ends up lying flush against an edge. So the direction perpendicular to that edge separates them — which means some edge normal always works, and testing the edges is testing everything.

Two practical notes fall out of that:

Opposite edges are redundant. A rectangle’s four normals point in only two directions, and a shadow does not care which way up its axis is. Two rectangles offer eight axes and two distinct directions. Skipping the duplicates is the first optimisation anyone makes, and it is worth knowing before you make it that the duplicates are harmless, only wasteful.

Winding decides which way the normals face. For a counter-clockwise polygon the interior lies to the left of each edge, so the right perpendicular points outward. The hit-or-miss answer does not care — an axis and its opposite cast identical shadows — but the push-out direction in Section 5.4 does, and a polygon loaded from a file can be wound either way. Normalizing the winding once is cheaper than reasoning about signs everywhere afterwards.

Where the axes come from, and why they are normalized

The code src/lib/gamedev/demos/2d/normals.ts

/** The candidate axes, where they come from, and why they are normalized. */
import {
  candidateAxes,
  distinctAxisCount,
  edgeNormals,
  edgeNormalsRaw,
  overlapOnAxis,
  project,
  regularPolygon,
  smallestOverlap,
  smallestOverlapRaw,
  suitableForSat,
} from "../../../gamedev2d/sat2d.ts";
import { CHEVRON } from "./separate-shared.ts";
import type { Demo } from "../runner.ts";

const SQUARE = [
  { x: -1, y: -1 },
  { x: 1, y: -1 },
  { x: 1, y: 1 },
  { x: -1, y: 1 },
];
const TRIANGLE = regularPolygon(3, 1.5, { x: 0.8, y: 0.4 }, 0.3);

const demo: Demo = (log) => {
  // One axis per edge, and nothing else. That is the part 3D does not get.
  log(
    "edgeNormals(square)",
    edgeNormals(SQUARE)
      .map((n) => `(${n.x}, ${n.y})`)
      .join(" "),
    "one per edge, each the edge turned ninety degrees and scaled to length 1",
  );
  log(
    "candidateAxes(square, triangle).length",
    candidateAxes(SQUARE, TRIANGLE).length,
    `4 + 3, and ${distinctAxisCount(SQUARE, TRIANGLE)} of them point in different directions`,
  );
  log(
    "distinctAxisCount(square, square shifted)",
    distinctAxisCount(
      SQUARE,
      SQUARE.map((p) => ({ x: p.x + 3, y: p.y })),
    ),
    "8 axes offered, 2 directions - a rectangle's opposite edges test identically",
  );

  // A projection is a shadow: the lowest and highest the shape reaches along a direction.
  const axis = { x: 1, y: 0 };
  log(
    "project(triangle, (1, 0))",
    `${project(TRIANGLE, axis).min.toFixed(4)} to ${project(TRIANGLE, axis).max.toFixed(4)}`,
    "only the corners need testing, because a convex shape reaches no further than they do",
  );
  log(
    "overlapOnAxis(square, triangle, (1, 0))",
    overlapOnAxis(SQUARE, TRIANGLE, axis).toFixed(4),
    "positive is an overlap on this axis; negative would be a gap, and one gap ends the test",
  );

  /* Normalizing does not change the verdict - scaling an axis scales both shadows - but it does change
     which axis wins the "shallowest" comparison, because depth comes out in units of the axis's length. */
  const good = smallestOverlap(SQUARE, TRIANGLE)!;
  const raw = smallestOverlapRaw(SQUARE, TRIANGLE)!;
  const squareEdge = edgeNormalsRaw(SQUARE)[0];
  const triangleEdge = edgeNormalsRaw(TRIANGLE)[0];
  log(
    "smallestOverlap vs smallestOverlapRaw",
    `depth ${good.depth.toFixed(4)} along (${good.axis.x.toFixed(3)}, ${good.axis.y.toFixed(3)}) vs ${raw.depth.toFixed(4)} along (${raw.axis.x.toFixed(3)}, ${raw.axis.y.toFixed(3)})`,
    `unnormalized, the square's axes are ${Math.hypot(squareEdge.x, squareEdge.y).toFixed(3)} long and the triangle's ${Math.hypot(triangleEdge.x, triangleEdge.y).toFixed(3)}, so the depths are in different units`,
  );

  // And the precondition, which is not a formality.
  log(
    "suitableForSat(square) and suitableForSat(chevron)",
    `${suitableForSat(SQUARE)} and ${suitableForSat(CHEVRON)}`,
    "a concave shape gives no error and no warning, only overlaps that are not there",
  );
};

export default demo;

edgeNormals(square) → (0, -1) (1, 0) (0, 1) (-1, 0) // one per edge, each the edge turned ninety degrees and scaled to length 1

candidateAxes(square, triangle).length → 7 // 4 + 3, and 5 of them point in different directions

distinctAxisCount(square, square shifted) → 2 // 8 axes offered, 2 directions - a rectangle's opposite edges test identically

project(triangle, (1, 0)) → -0.3004 to 2.2330 // only the corners need testing, because a convex shape reaches no further than they do

overlapOnAxis(square, triangle, (1, 0)) → 1.3004 // positive is an overlap on this axis; negative would be a gap, and one gap ends the test

smallestOverlap vs smallestOverlapRaw → depth 1.1184 along (-0.955, -0.296) vs 2.6008 along (2.000, 0.000) // unnormalized, the square's axes are 2.000 long and the triangle's 2.598, so the depths are in different units

suitableForSat(square) and suitableForSat(chevron) → true and false // a concave shape gives no error and no warning, only overlaps that are not there

Whether the shapes overlap does not depend on an axis’s length. Scaling a direction scales both shadows by the same factor, so the sign of the overlap cannot change. Unnormalized axes give a perfectly correct hit test, always — the build asserts that across forty thousand configurations, and it is why this bug survives every test anyone writes for it.

What breaks is the depth. Overlap along an axis comes out in units of that axis’s length, so comparing depths across axes of different lengths compares different units — and “the shallowest overlap” then picks the wrong axis. With the demo’s pentagon and triangle that happens at 47.56% of overlapping configurations, and the chosen direction is out by as much as 81.41°.

So: a correct collision test, and a character shoved sideways out of a wall it should have been pushed off the front of. That is Section 5.4’s problem arriving early.

The Minimum Translation Vector

When no axis separates them, the axis with the smallest overlap is the shortest way to push them apart. Every axis measures a distance you could move one shape to end the overlap along that direction, and the smallest of those is the least disruptive.

That is the minimum translation vector, and Section 5.4 is about what to do with it. Here it is only a measurement — drawn as the purple arrow when the shapes touch.

SAT Needs Convex Shapes, And Will Not Tell You Otherwise

The same test on a concave shape, reporting hits that are not there

The square starts in the notch, touching nothing, and the test says otherwise.

The code that draws it src/lib/gamedev/demos/2d/concave.scene.ts

/** A concave shape, and the region where the separating axis test reports a hit that is not there. */
import {
  makeCanvas2D,
  addDragTargets,
  dot as fillDot,
  label,
} from "../canvas2d.ts";
// From `controls.ts`, not `ui.ts`: the latter imports Three.js and this track must not.
import { addCheckbox, addReadout, addSlider } from "../controls.ts";
import { polygonsOverlap } from "../../../gamedev2d/sat2d.ts";
import {
  BOUNDS,
  CHEVRON,
  CHEVRON_HULL,
  PROBE_START,
  UNIT,
  VIEW,
  concaveFalseArea,
  falseRegionCells,
  probeAt,
  satIsWrongAt,
  screenOf,
  worldOf,
} from "./separate-shared.ts";
import type { MountFn } from "../runner.ts";

const SHAPE = "#7d8590";
const HULL = "#3b4552";
const HONEST = "#7ee787";
const LYING = "#ff7b72";
const APART = "#58a6ff";
const DIM = "#636c76";

const mount: MountFn = (el) => {
  const { ctx, canvas, clear } = makeCanvas2D(el, VIEW.height);

  // Both are fixed for the life of the scene, so neither is recomputed on a drag.
  const cells = falseRegionCells();
  const measured = concaveFalseArea(300);
  const hull = CHEVRON_HULL;

  const show = addReadout(el);
  const note = addReadout(el);
  const px = addSlider(
    el,
    "x",
    -BOUNDS.x,
    BOUNDS.x,
    PROBE_START.x,
    draw,
    "",
    0.05,
  );
  const py = addSlider(
    el,
    "y",
    -BOUNDS.y,
    BOUNDS.y,
    PROBE_START.y,
    draw,
    "",
    0.05,
  );
  const showRegion = addCheckbox(
    el,
    "shade every place the test is wrong",
    true,
    draw,
  );

  const stopDragging = addDragTargets(
    canvas,
    () => [screenOf({ x: px(), y: py() })],
    (_index, sx, sy) => {
      const world = worldOf(sx, sy);
      px.set(Math.min(Math.max(world.x, -BOUNDS.x), BOUNDS.x));
      py.set(Math.min(Math.max(world.y, -BOUNDS.y), BOUNDS.y));
      draw();
    },
  );

  function strokePolygon(
    poly: readonly { x: number; y: number }[],
    colour: string,
    width = 2.2,
    dashed = false,
  ) {
    ctx.save();
    ctx.strokeStyle = colour;
    ctx.lineWidth = width;
    if (dashed) ctx.setLineDash([5, 4]);
    ctx.beginPath();
    poly.forEach((p, i) => {
      const q = screenOf(p);
      if (i === 0) ctx.moveTo(q.x, q.y);
      else ctx.lineTo(q.x, q.y);
    });
    ctx.closePath();
    ctx.stroke();
    ctx.restore();
  }

  function draw() {
    clear();
    const p = { x: px(), y: py() };
    const probe = probeAt(p);
    const sat = polygonsOverlap(CHEVRON, probe);
    const lying = satIsWrongAt(p);

    // The measured false region, cell by cell. Precomputed, so this is only drawing.
    if (showRegion()) {
      ctx.save();
      ctx.fillStyle = "rgba(255, 123, 114, 0.22)";
      for (const cell of cells) {
        const q = screenOf({ x: cell.x, y: cell.y });
        const side = cell.size * UNIT;
        ctx.fillRect(q.x - side / 2, q.y - side / 2, side + 0.5, side + 0.5);
      }
      ctx.restore();
    }

    /* The convex hull, which is roughly the shape a convex test can describe. Dashed, and labelled as an
       approximation rather than as the answer: a concave polygon's reflex edges contribute normals of
       their own, so the hull bounds the error without being equal to it. */
    strokePolygon(hull, HULL, 1.4, true);
    strokePolygon(CHEVRON, SHAPE, 2.4);
    for (const corner of CHEVRON) {
      const q = screenOf(corner);
      fillDot(ctx, q.x, q.y, 2.6, SHAPE);
    }

    strokePolygon(probe, lying ? LYING : sat ? HONEST : APART, 2.4);
    const centre = screenOf(p);
    fillDot(ctx, centre.x, centre.y, 3.5, lying ? LYING : sat ? HONEST : APART);

    label(ctx, "the shape", 12, 18, SHAPE);
    label(
      ctx,
      "its convex hull, roughly what a convex test sees",
      12,
      32,
      HULL,
    );
    label(
      ctx,
      "drag the square into the notch \u00b7 shaded means the test is lying",
      12,
      VIEW.height - 10,
      DIM,
    );

    show(
      `the test says ${sat ? "overlap" : "apart"} \u00b7 ` +
        `${lying ? "and nothing is actually touching" : sat ? "and it is right" : "and it is right"} \u00b7 ` +
        `${(measured.fraction * 100).toFixed(2)}% of the area around this shape is a false positive`,
    );
    note(
      lying
        ? "no corner of either shape is inside the other and no edges cross \u2014 the test simply cannot describe a notch"
        : sat
          ? "a real overlap, reported correctly \u2014 SAT is not broken, it is being asked about the wrong kind of shape"
          : "outside the shape and outside its hull too, so every axis agrees and the answer is right",
    );
  }

  draw();

  return stopDragging;
};

export default mount;

The square starts inside the notch. No corner of either shape is inside the other, no edges cross, and nothing whatsoever is touching. The test reports an overlap.

That is not a bug in the code. isConvex comes from Section 2.1, and here it is a precondition — a test built on shadows can only ever describe a convex region, so handed a concave polygon it answers about something closer to the shape’s convex hull. The dashed outline shows that hull, and the shaded cells are every probe position where the answer is measurably wrong: 1.307 square units, 3.19% of the area sampled around the shape.

The fix is not to patch SAT. It is to decompose the shape into convex pieces — a chevron is two quadrilaterals — and test each. Every engine does this, and it is why a physics editor makes you draw convex collision shapes rather than tracing your sprite.

source Shadows, edge normals, the separating axis, and the unnormalized version kept for pricing src/lib/gamedev2d/sat2d.ts 320 lines

/**
 * The separating axis test: **if you can find one direction along which two shapes do not overlap, they miss.**
 *
 * That sentence is the whole algorithm, and you have already used it twice. Section 5.1's box test is
 * this with the two axes fixed to $x$ and $y$. What changes here is only *which* directions are worth
 * trying - and the answer for convex polygons is short: the directions perpendicular to their edges.
 *
 * **This is the Section where 2D genuinely earns its place.** In three dimensions the candidate axes are
 * the face normals of both shapes *plus* the cross product of every pair of edges - fifteen axes for two
 * boxes, and the reason SAT has a reputation for being fiddly. In 2D there are no cross-product axes at
 * all. Two triangles need six axes and every one of them is just an edge turned ninety degrees.
 */
import { cross, isConvex, windingOf } from "./cross2d.ts";
import { rangesOverlap } from "./collide2d.ts";
import { dot } from "./dot2d.ts";
import { length, normalize } from "./length2d.ts";
import {
  displacement,
  movedBy,
  scaled,
  type Point,
  type Vector,
} from "./vectors2d.ts";

/** A polygon is its corners, in order. Convexity is a separate question, and SAT insists on it. */
export type Polygon = readonly Point[];

/** What a polygon casts onto an axis: the lowest and highest it reaches along that direction. */
export type Interval = { min: number; max: number };

/**
 * The shadow a polygon casts on an axis.
 *
 * Dot every corner against the direction and keep the smallest and largest. That is Section 1.4's
 * projection applied to a whole shape, and the reason only the **corners** need checking is convexity:
 * every point of a convex polygon is a blend of its corners, so no interior point can reach further
 * along any direction than the furthest corner does.
 */
export function project(poly: Polygon, axis: Vector): Interval {
  let min = Infinity;
  let max = -Infinity;
  for (const corner of poly) {
    const along = dot(corner, axis);
    min = Math.min(min, along);
    max = Math.max(max, along);
  }
  return { min, max };
}

/**
 * Put a polygon into counter-clockwise order, so its edge normals reliably point **outward**.
 *
 * The hit-or-miss answer does not care - an axis and its opposite give the same shadows, so a flipped
 * normal changes nothing. The **push-out direction** cares a great deal, and that is what Section 5.4
 * needs. A polygon loaded from a file or built by dragging can be wound either way, so normalizing the
 * winding once is cheaper than reasoning about signs everywhere afterwards.
 */
export function counterClockwise(poly: Polygon): Polygon {
  return windingOf(poly) === "clockwise" ? [...poly].reverse() : poly;
}

/**
 * The candidate axes for one polygon: each edge turned ninety degrees, at unit length.
 *
 * **Normalized deliberately, and it matters for exactly one reason.** Whether the shapes overlap is
 * unaffected by an axis's length, because scaling a direction scales both shadows equally and the
 * comparison is unchanged. But the *depth* of overlap comes out in units of the axis's length, so
 * comparing depths across axes of different lengths compares different units - and the "smallest
 * overlap" then picks the wrong axis. The build prices that.
 */
export function edgeNormals(poly: Polygon): Vector[] {
  const wound = counterClockwise(poly);
  const normals: Vector[] = [];
  for (let i = 0; i < wound.length; i += 1) {
    const edge = displacement(wound[i], wound[(i + 1) % wound.length]);
    // For counter-clockwise winding the interior lies to the left, so the right perpendicular is outward.
    const outward = normalize({ x: edge.y, y: -edge.x });
    // A repeated corner gives a zero-length edge and no usable normal. Skipping it is correct: it
    // contributes no direction, and dividing by its length would produce NaN axes that separate nothing.
    if (outward !== null) normals.push(outward);
  }
  return normals;
}

/** The same, left unnormalized. Here only so the build can show what that costs. */
export function edgeNormalsRaw(poly: Polygon): Vector[] {
  const wound = counterClockwise(poly);
  const normals: Vector[] = [];
  for (let i = 0; i < wound.length; i += 1) {
    const edge = displacement(wound[i], wound[(i + 1) % wound.length]);
    if (length(edge) > 1e-12) normals.push({ x: edge.y, y: -edge.x });
  }
  return normals;
}

/**
 * Every axis worth testing for a pair: the edge normals of both.
 *
 * And in 2D that is genuinely all of them. The reason is worth stating because it is what makes this
 * Section tractable: if two convex shapes are apart, there is a line between them, and that line can
 * always be slid until it lies flush against an edge of one of them. So some edge's normal separates
 * them, and testing the edges is testing everything.
 */
export function candidateAxes(a: Polygon, b: Polygon): Vector[] {
  return [...edgeNormals(a), ...edgeNormals(b)];
}

/**
 * How much the two shadows overlap on an axis. **Negative means a gap**, and a gap means a miss.
 *
 * The range comparison is Section 5.1's, doing its fourth job in three Sections: two boxes, two
 * collinear segments, and now two polygon shadows.
 */
export function overlapOnAxis(a: Polygon, b: Polygon, axis: Vector): number {
  const shadowA = project(a, axis);
  const shadowB = project(b, axis);
  return (
    Math.min(shadowA.max, shadowB.max) - Math.max(shadowA.min, shadowB.min)
  );
}

/** The same question as a boolean, so the range check is visibly the same one. */
export function shadowsOverlap(a: Polygon, b: Polygon, axis: Vector): boolean {
  const shadowA = project(a, axis);
  const shadowB = project(b, axis);
  return rangesOverlap(shadowA.min, shadowA.max, shadowB.min, shadowB.max);
}

/**
 * An axis that proves the two shapes miss, or `null` if there is none.
 *
 * **One is enough.** That is what makes SAT cheap in the common case: shapes that are far apart are
 * usually separated by the first axis tried, and the loop stops. Shapes that overlap are the expensive
 * case, because every axis has to be checked before you can say so.
 */
export function separatingAxis(a: Polygon, b: Polygon): Vector | null {
  for (const axis of candidateAxes(a, b)) {
    if (!shadowsOverlap(a, b, axis)) return axis;
  }
  return null;
}

/** Do two **convex** polygons overlap? No separating axis means yes. */
export function polygonsOverlap(a: Polygon, b: Polygon): boolean {
  return separatingAxis(a, b) === null;
}

/** The axis with the least overlap, and by how much. What Section 5.4 pushes along. */
export type Push = { axis: Vector; depth: number };

/**
 * The shallowest overlap across all candidate axes: the **minimum translation vector**.
 *
 * The shortest way to separate two overlapping shapes, because every axis measures a distance you could
 * move one of them to end the overlap on that axis, and the smallest of those is the least disruptive.
 * Section 5.4 is about what to do with it; here it is only the measurement.
 *
 * Returns `null` when they are not overlapping at all, which is a different thing from a zero-depth
 * push and worth keeping distinct.
 */
export function smallestOverlap(a: Polygon, b: Polygon): Push | null {
  let best: Push | null = null;
  for (const axis of candidateAxes(a, b)) {
    const depth = overlapOnAxis(a, b, axis);
    if (depth <= 0) return null;
    if (best === null || depth < best.depth) best = { axis, depth };
  }
  return best;
}

/**
 * The same, with unnormalized axes. Correct about hit or miss, wrong about which way to push.
 *
 * Kept so the build can measure the difference rather than the page claiming there is one.
 */
export function smallestOverlapRaw(a: Polygon, b: Polygon): Push | null {
  let best: Push | null = null;
  for (const axis of [...edgeNormalsRaw(a), ...edgeNormalsRaw(b)]) {
    const depth = overlapOnAxis(a, b, axis);
    if (depth <= 0) return null;
    if (best === null || depth < best.depth) best = { axis, depth };
  }
  return best;
}

/**
 * How many of the candidate axes point in genuinely different directions.
 *
 * Worth knowing because a rectangle's opposite edges have opposite normals, which test identically - so
 * two rectangles offer eight axes and only two distinct directions between them. Testing the duplicates
 * is harmless and wasteful, and skipping them is the first optimisation anyone makes.
 */
export function distinctAxisCount(a: Polygon, b: Polygon): number {
  const seen: Vector[] = [];
  for (const axis of candidateAxes(a, b)) {
    // Parallel counts as the same, in either direction, since a shadow does not care which way up it is.
    if (seen.some((other) => Math.abs(cross(axis, other)) < 1e-9)) continue;
    seen.push(axis);
  }
  return seen.length;
}

// ---- The convexity requirement ----------------------------------------------------------------

/**
 * Is this polygon something SAT can be trusted on? Convex, and with enough corners to be a shape.
 *
 * `isConvex` comes from Section 2.1, where it was a fact about cross products changing sign. Here it is
 * a **precondition**, and one worth checking rather than assuming: SAT on a concave polygon does not
 * crash, does not warn, and reports overlaps that are not there. The build measures how much area that
 * costs.
 */
export function suitableForSat(poly: Polygon): boolean {
  return poly.length >= 3 && isConvex(poly);
}

/**
 * Is a point inside a polygon? Ray casting, which works for concave shapes too.
 *
 * Needed as the honest reference the concave case is measured against. It counts how many times a ray
 * from the point crosses the boundary: an odd count means inside. Nothing about it assumes convexity,
 * which is exactly why it can be used to catch SAT out.
 */
export function containsPoint(poly: Polygon, p: Point): boolean {
  let inside = false;
  for (let i = 0, j = poly.length - 1; i < poly.length; j = i, i += 1) {
    const a = poly[i];
    const b = poly[j];
    // Does the edge straddle the point's height, and if so is the crossing to the right?
    if (a.y > p.y !== b.y > p.y) {
      const crossesAt = a.x + ((p.y - a.y) / (b.y - a.y)) * (b.x - a.x);
      if (crossesAt > p.x) inside = !inside;
    }
  }
  return inside;
}

// ---- Building and moving polygons -------------------------------------------------------------

/** A regular polygon, which is the easiest convex shape to reason about and to draw. */
export function regularPolygon(
  sides: number,
  radius: number,
  centre: Point = { x: 0, y: 0 },
  rotation = 0,
): Point[] {
  return Array.from({ length: sides }, (_, i) => {
    const angle = rotation + (i / sides) * Math.PI * 2;
    return {
      x: centre.x + Math.cos(angle) * radius,
      y: centre.y + Math.sin(angle) * radius,
    };
  });
}

/** Every corner moved by the same displacement. */
export function translatePolygon(poly: Polygon, by: Vector): Point[] {
  return poly.map((p) => movedBy(p, by));
}

/** Every corner turned about a pivot, which is Section 2.3's rotation applied to a list. */
export function rotatePolygon(
  poly: Polygon,
  radians: number,
  about: Point = { x: 0, y: 0 },
): Point[] {
  const cos = Math.cos(radians);
  const sin = Math.sin(radians);
  return poly.map((p) => {
    const local = displacement(about, p);
    return movedBy(about, {
      x: local.x * cos - local.y * sin,
      y: local.x * sin + local.y * cos,
    });
  });
}

/**
 * The convex hull: the smallest convex polygon containing every corner. Andrew's monotone chain.
 *
 * Here because it names what a concave shape's problem **is**. SAT can only ever describe a convex
 * region, so handed a concave polygon it answers about something closer to this - and the difference
 * between the two is where it invents collisions.
 *
 * Not exactly the hull, though, and the page is careful about that: a concave polygon offers normals from
 * its reflex edges too, which are not hull edges, and those extra axes occasionally do separate. So the
 * hull bounds the lie rather than being it, which is why the false region is measured as well as drawn.
 */
export function convexHull(poly: Polygon): Point[] {
  if (poly.length < 3) return [...poly];
  const sorted = [...poly].sort((p, q) => p.x - q.x || p.y - q.y);
  const half = (points: Point[]): Point[] => {
    const chain: Point[] = [];
    for (const p of points) {
      while (
        chain.length >= 2 &&
        cross(
          displacement(chain[chain.length - 2], chain[chain.length - 1]),
          displacement(chain[chain.length - 2], p),
        ) <= 0
      ) {
        chain.pop();
      }
      chain.push(p);
    }
    return chain;
  };
  const lower = half(sorted);
  const upper = half([...sorted].reverse());
  return [...lower.slice(0, -1), ...upper.slice(0, -1)];
}

/** The average of the corners. Not the centre of area, and adequate for placing a label. */
export function cornerCentre(poly: Polygon): Point {
  const total = poly.reduce((sum, p) => ({ x: sum.x + p.x, y: sum.y + p.y }), {
    x: 0,
    y: 0,
  });
  return scaled(total, 1 / poly.length);
}

Godot: ConvexPolygonShape2D is the shape SAT applies to, and the name is a warning rather than a description. CollisionPolygon2D has a build_mode of Solids or Segments, and a concave outline becomes multiple convex pieces internally. Geometry2D.decompose_polygon_in_convex() does that decomposition explicitly if you need it yourself, and Geometry2D.convex_hull() is the hull above.

Unity 2D: PolygonCollider2D accepts concave outlines and splits them into convex paths behind the scenes; the points you set and the pathCount you get back are not the same thing, which is this Section’s constraint showing through the API. PhysicsShapeGroup2D exposes the pieces.

Both engines cap the number of vertices on a convex shape — the axis count grows with it, and so does the cost of the overlapping case. If you are hitting that cap, the answer is usually fewer, simpler shapes rather than one detailed one.

Where This Shows Up

Section 5.4, which takes the minimum translation vector and turns it into a push and a slide.
Section 5.1’s box test, which is this algorithm with the axes fixed to $x$ and $y$ .
Section 5.1’s range check, still doing the comparison.
Section 1.4’s dot product, doing every projection.
Section 2.1’s cross product, deciding convexity and spotting parallel axes.
Rotated hitboxes generally — the moment a collision shape can turn, this is the test you need.

One direction with a gap in it proves two convex shapes miss, and for polygons the directions worth trying are just the edge normals — no cross-product axes, which is why 2D is where this idea is learnable. Project by dotting the corners, compare the shadows with a range check, and stop at the first gap: missing is cheap, overlapping is what costs you every axis. Normalize the axes, not because the verdict needs it but because the depth does — unnormalized, the hit test stays perfectly correct while the shallowest-overlap direction goes wrong by up to $81.41°$ . And check convexity, because SAT on a concave shape reports overlaps that are not there, silently, over $3.19\%$ of the area around it. Decompose into convex pieces instead of patching the test.