Chapter 8: Find the Big Box Before Inspecting the Edge

Start with a game a five-year-old can understand

The one truth in this chapter: Hit Testing is a geometry query system, not a handful of if statements.

Put twenty toys into four shoeboxes. Now close your eyes and use a cotton swab to find “the thin blue string on top.” You have two options: take out and touch every toy, or first see which shoebox the swab landed in, inspect only the toys inside that box, and finally measure how far the swab is from the string.

Predict what happens first. The blue string is as thin as a hair. After a child enlarges the toy city ten times, how close must the swab be to count as a hit? If the tolerance also grows ten times, does clicking become easier or stay the same? If a rectangle is rotated 45°, can touching only its large, unrotated box prove that you really touched the rectangle?

This is a two-phase query. The first phase may keep a few extra candidates, but it must never omit the real target. Only the second phase checks fill, stroke, handles, connectors, and the true transformed geometry. The result is more than true/false: it tells the tool who was hit, which part was hit, how far away it was, and where the world and local points are.

Translate the toys into Canvas

The analogy has limits. A real shoebox has volume, while a 2D AABB is only an axis-aligned range. AABB intersection is necessary but not sufficient. Negative Scale reverses local orientation, but width and height must not become negative distances. A mathematically zero-width line has no area, yet a UI can make it clickable with screen tolerance. Floating-point numbers are not infinitely precise rulers either, so boundary decisions require an epsilon.

Kill the wrong instincts first

• “x <= px <= x + width is enough.” Rotation, parent transforms, negative Scale, line segments, and Bézier curves break it immediately.
• “Calling ctx.isPointInPath() directly is most accurate.” That welds hit rules to the Renderer, Context State, and browser environment. Node tests, spatial indexes, and SVG/GPU Renderers cannot reuse them.
• “An AABB hit is a real hit.” A rotated rectangle leaves large empty regions near the corners of its AABB.
• “Use a fixed 5 world units to click a line.” At Zoom 0.1, that is 0.5 px and almost impossible to hit; at Zoom 10, it is 50 px and hits from far away.
• “Return the first candidate.” A Spatial Index does not promise Z-Order; compare candidates according to the page’s stacking rules.
• “Cache Bounds forever.” When the Shape, a parent Transform, Stroke, or Geometry changes, a stale box makes targets disappear or creates ghost hits.

Production backpack

Prerequisite contract

Chapter 4 supplies invertible worldToScreen/screenToWorld transforms and a finite, positive Camera Scale. Chapter 5 gives Shapes stable IDs, parent-child relationships, Z-Order, Local Transform, and a Geometry Provider. Chapter 7 passes in only a normalized World Point. GeometryKernel imports no Canvas API, React, or DOM.

Formal knowledge

A two-dimensional vector is v=(x,y). The Dot Product a·b=ax·bx+ay·by supports projection and angle tests. The sign of the scalar two-dimensional Cross Product a×b=ax·by-ay·bx tells you left or right turn, line-segment intersection, and polygon winding. Distance is the length of the difference vector. Point-to-segment distance is not point-to-infinite-line distance: first compute t=clamp(((p-a)·(b-a))/|b-a|²,0,1), then use a+t(b-a). When segment length approaches zero, treat it as a point.

Line-segment intersection must handle ordinary crossings, collinear overlap, and endpoint contact. The product must also decide whether these cases return one point, an interval, or only a boolean. Polygon Contains can use the even-odd rule or nonzero Winding; holes and self-intersecting polygons require an explicit fill rule. A quadratic or cubic Bézier Narrow Phase can use an analytic nearest point, recursive subdivision, or flattening with an error bound. Do not approximate every curve with a fixed ten segments and pretend the precision is uniform.

An AABB is {minX,minY,maxX,maxY} and works well for indexing and broad filtering. An OBB has a center, two unit axes, and half-extents; it fits rotated targets more tightly but costs more to intersect. A common implementation transforms the corners of local geometry through the World Matrix, then takes their minima and maxima to produce a conservative transformed AABB. Nested Groups must compose matrices in the established multiplication order. Reorder min/max after negative Scale. A non-invertible matrix can only produce a diagnosable miss, never spreading NaN values.

A Fill hit uses an inside-area rule. A Stroke hit expands the centerline by “the true transformed half-stroke width for this Shape + toleranceWorld” and also considers line cap, join, and miter. Never add a local-space strokeWidth or local distance directly to world tolerance. With a uniform Camera, toleranceWorld = toleranceScreen / abs(cameraScale). With a nonuniform View Transform, transform the screen-tolerance vector through the inverse matrix or compare exactly in Screen Space. Resize and Rotate Handles usually remain 8–12 CSS px on screen; they must not scale with the world.

The Broad Phase interface promises only “every object that could intersect.” Its implementation can begin as a linear scan and later become an R-tree, quadtree, or BVH. Each Shape’s Geometry Provider answers Narrow Phase queries for containsPoint, distanceToPoint, intersectsRectangle, nearestPoint, outline, and snapPoints. Sort query results deterministically by overlay handle, selected-object rules, Z-Order, distance, and stable ID. Replay then remains stable even if index return order changes.

Evidence and compatibility (verified 2026-08-29)

GeometryKernel uses plain numeric structures and runs in Node. MDN DOMMatrix and DOMMatrixReadOnly.inverse() are useful references for the browser adapter. MDN states that components may become NaN when an inverse is unavailable, so the boundary must validate finiteness. Canvas isPointInPath() and isPointInStroke() are useful for differential testing, but they are not domain truth. Kernel tests should pass unchanged after replacing the Renderer.

The engineering increment for this chapter

Starting point: The Select Tool scans every Shape and uses an unrotated-rectangle if. Finish line: An independent GeometryKernel supplies stable queries. The linear Broad Phase can be replaced by a spatial index without changing the Narrow Phase or result semantics.

Add these files and interfaces:

• src/engine/geometry/vector.ts: vectors, dot, cross, and epsilon;
• src/engine/geometry/bounds.ts: AABB, transforms, and intersection;
• src/engine/geometry/providers.ts: Geometry Provider registry;
• src/engine/geometry/GeometryKernel.ts: Broad/Narrow queries and deterministic sorting;
• src/engine/geometry/__tests__/properties.test.ts: rotation, negative Scale, degenerate shapes, and tolerance properties;
• tests/browser/hit-tolerance.spec.ts: the same screen distance at different Zoom levels.

This complete TypeScript kernel implements rectangle and polyline queries. Ellipse and Bézier support add Providers later without changing the Tool. First make explicit a contract that code can easily hide: in this teaching kernel, strokeWidthWorld is a world-space width that does not scale with the Shape Transform, and Entry.bounds is the transformed world AABB including half the stroke. If the product chooses “scaling a Shape also scales its Stroke,” the Provider must first calculate the true transformed outline rather than adding world tolerance to local distance. The example Camera has only rotation, translation, and uniform Zoom; use Screen-Space comparison for a nonuniform View Transform.

export type Vec = Readonly<{ x: number; y: number }>;
export type Aabb = Readonly<{ minX: number; minY: number; maxX: number; maxY: number }>;
export type Mat = Readonly<{ a: number; b: number; c: number; d: number; e: number; f: number }>;
export type Geometry =
  | Readonly<{
      kind: 'rect';
      width: number;
      height: number;
      filled: boolean;
      strokeWidthWorld: number;
    }>
  | Readonly<{
      kind: 'polyline';
      points: readonly Vec[];
      closed: boolean;
      strokeWidthWorld: number;
    }>;
export type Entry = Readonly<{
  id: string;
  z: number;
  world: Mat;
  bounds: Aabb;
  geometry: Geometry;
}>;
export type HitResult = Readonly<{
  id: string;
  part: 'fill' | 'stroke';
  distanceWorld: number;
  worldPoint: Vec;
  localPoint: Vec;
  z: number;
}>;

const EPS = 1e-9;
const dot = (a: Vec, b: Vec) => a.x * b.x + a.y * b.y;
const sub = (a: Vec, b: Vec): Vec => ({ x: a.x - b.x, y: a.y - b.y });
const add = (a: Vec, b: Vec): Vec => ({ x: a.x + b.x, y: a.y + b.y });
const mul = (a: Vec, n: number): Vec => ({ x: a.x * n, y: a.y * n });
const length = (v: Vec) => Math.hypot(v.x, v.y);
export const cross = (a: Vec, b: Vec) => a.x * b.y - a.y * b.x;

export function nearestOnSegment(p: Vec, a: Vec, b: Vec): Vec {
  const ab = sub(b, a);
  const denominator = dot(ab, ab);
  if (denominator <= EPS) return a;
  const t = Math.max(0, Math.min(1, dot(sub(p, a), ab) / denominator));
  return add(a, mul(ab, t));
}

export function invert(m: Mat): Mat | null {
  const det = m.a * m.d - m.b * m.c;
  if (!Number.isFinite(det) || Math.abs(det) <= EPS) return null;
  return {
    a: m.d / det,
    b: -m.b / det,
    c: -m.c / det,
    d: m.a / det,
    e: (m.c * m.f - m.d * m.e) / det,
    f: (m.b * m.e - m.a * m.f) / det,
  };
}

export const transform = (m: Mat, p: Vec): Vec => ({
  x: m.a * p.x + m.c * p.y + m.e,
  y: m.b * p.x + m.d * p.y + m.f,
});

export const expand = (b: Aabb, by: number): Aabb => ({
  minX: b.minX - by,
  minY: b.minY - by,
  maxX: b.maxX + by,
  maxY: b.maxY + by,
});
export const containsAabb = (b: Aabb, p: Vec) =>
  p.x >= b.minX && p.x <= b.maxX && p.y >= b.minY && p.y <= b.maxY;

function pointInPolygon(point: Vec, points: readonly Vec[]): boolean {
  let winding = 0;
  for (let i = 0; i < points.length; i++) {
    const a = points[i],
      b = points[(i + 1) % points.length];
    const side = cross(sub(b, a), sub(point, a));
    if (a.y <= point.y && b.y > point.y && side > EPS) winding++;
    if (a.y > point.y && b.y <= point.y && side < -EPS) winding--;
  }
  return winding !== 0;
}

function narrow(entry: Entry, worldPoint: Vec, toleranceWorld: number): HitResult | null {
  const inverse = invert(entry.world);
  if (!inverse) return null;
  const p = transform(inverse, worldPoint);
  const g = entry.geometry;
  const points: readonly Vec[] =
    g.kind === 'rect'
      ? [
          { x: 0, y: 0 },
          { x: g.width, y: 0 },
          { x: g.width, y: g.height },
          { x: 0, y: g.height },
        ]
      : g.points;
  const worldPoints = points.map((point) => transform(entry.world, point));

  let minimumWorld = Number.POSITIVE_INFINITY;
  const edgeCount = g.kind === 'rect' || g.closed ? points.length : Math.max(0, points.length - 1);
  for (let i = 0; i < edgeCount; i++) {
    const nearest = nearestOnSegment(
      worldPoint,
      worldPoints[i],
      worldPoints[(i + 1) % worldPoints.length],
    );
    minimumWorld = Math.min(minimumWorld, length(sub(worldPoint, nearest)));
  }
  const filled = g.kind === 'rect' ? g.filled : g.closed;
  const inFill = filled && points.length >= 3 && pointInPolygon(p, points);
  const strokeHit = minimumWorld <= g.strokeWidthWorld / 2 + toleranceWorld;
  if (!inFill && !strokeHit) return null;
  return {
    id: entry.id,
    part: inFill ? 'fill' : 'stroke',
    distanceWorld: inFill ? 0 : minimumWorld,
    worldPoint,
    localPoint: p,
    z: entry.z,
  };
}

export interface SpatialQuery {
  atPoint(point: Vec, radiusWorld: number): readonly Entry[];
}

export class GeometryKernel {
  constructor(private readonly index: SpatialQuery) {}

  hitTest(worldPoint: Vec, toleranceScreen: number, cameraScale: number): HitResult | null {
    if (!(cameraScale > EPS) || !Number.isFinite(cameraScale)) return null;
    const toleranceWorld = toleranceScreen / cameraScale;
    const candidates = this.index
      .atPoint(worldPoint, toleranceWorld)
      .filter((entry) => containsAabb(expand(entry.bounds, toleranceWorld), worldPoint))
      .sort((a, b) => b.z - a.z || a.id.localeCompare(b.id));
    for (const entry of candidates) {
      const result = narrow(entry, worldPoint, toleranceWorld);
      if (result) return result;
    }
    return null;
  }
}

The complete public contract for a Provider also includes the following capabilities. Selection, Snapping, and the Spatial Index depend on it instead of the Renderer:

export interface ShapeGeometryProvider<S> {
  bounds(shape: S): Aabb;
  containsPoint(shape: S, localPoint: Vec): boolean;
  distanceToPoint(shape: S, localPoint: Vec): number;
  intersectsRectangle(shape: S, localRectangle: Aabb): boolean;
  transformedBounds(shape: S, world: Mat): Aabb;
  nearestPoint(shape: S, localPoint: Vec): Vec;
  selectionOutline(shape: S): readonly Vec[];
  snapPoints(shape: S): readonly Vec[];
}

Property tests focus on invariants rather than testing only three attractive coordinates:

import { describe, expect, it } from 'vitest';
import fc from 'fast-check';
import { GeometryKernel, nearestOnSegment } from '../GeometryKernel';

describe('GeometryKernel', () => {
  it('the nearest point on a segment always remains within the segment parameter range', () => {
    fc.assert(
      fc.property(
        fc.double({ min: -1e4, max: 1e4, noNaN: true }),
        fc.double({ min: -1e4, max: 1e4, noNaN: true }),
        (x, y) => {
          const q = nearestOnSegment({ x, y }, { x: 0, y: 0 }, { x: 10, y: 0 });
          expect(q.x).toBeGreaterThanOrEqual(0);
          expect(q.x).toBeLessThanOrEqual(10);
          expect(q.y).toBe(0);
        },
      ),
    );
  });

  it('screen tolerance stays the same at different zoom levels', () => {
    const line = {
      id: 'line',
      z: 1,
      world: { a: 1, b: 0, c: 0, d: 1, e: 0, f: 0 },
      bounds: { minX: 0, minY: 0, maxX: 100, maxY: 0 },
      geometry: {
        kind: 'polyline' as const,
        points: [
          { x: 0, y: 0 },
          { x: 100, y: 0 },
        ],
        closed: false,
        strokeWidthWorld: 0,
      },
    };
    const kernel = new GeometryKernel({ atPoint: () => [line] });
    expect(kernel.hitTest({ x: 20, y: 4 }, 5, 1)?.id).toBe('line');
    expect(kernel.hitTest({ x: 20, y: 0.4 }, 5, 10)?.id).toBe('line');
    expect(kernel.hitTest({ x: 20, y: 0.6 }, 5, 10)).toBeNull();
  });

  it('Shape scale does not turn world tolerance into local tolerance', () => {
    const scaledLine = {
      id: 'scaled',
      z: 1,
      world: { a: 10, b: 0, c: 0, d: 10, e: 0, f: 0 },
      bounds: { minX: 0, minY: 0, maxX: 100, maxY: 0 },
      geometry: {
        kind: 'polyline' as const,
        points: [
          { x: 0, y: 0 },
          { x: 10, y: 0 },
        ],
        closed: false,
        strokeWidthWorld: 0,
      },
    };
    const kernel = new GeometryKernel({ atPoint: () => [scaledLine] });
    expect(kernel.hitTest({ x: 50, y: 4 }, 5, 1)?.distanceWorld).toBe(4);
    expect(kernel.hitTest({ x: 50, y: 6 }, 5, 1)).toBeNull();
  });
});

Run pnpm vitest run src/engine/geometry. Every property run should pass without a DOM environment. Run pnpm playwright test tests/browser/hit-tolerance.spec.ts. At 25%, 100%, and 400% Zoom, a point 4 px from the line should hit and one 6 px away should miss. Record candidate counts so Chapter 15 can use the same assertion when replacing the spatial index.

Return to the shoeboxes. The index says only “the swab may have landed in these boxes.” A Provider touches the real toy edge, and Z-Order decides which topmost toy comes out first. If the paintbrush becomes a GPU Renderer, the boxes, ruler, and result note stay unchanged.

Break it on purpose

Pass with evidence

• Vector, dot, cross, point-to-segment distance, line intersection, Polygon/Winding, and the Bézier strategy each have an independent definition.
• AABB is used only for the Broad Phase; OBB or true geometry supports the Narrow Phase where needed.
• Transformed Bounds supports rotation, nesting, negative Scale, and floating-point epsilon.
• Fill, Stroke Expansion, and Handle Geometry use explicit, distinct rules.
• HitResult contains ID, part, distance, local/world points, and Z information.
• Bounds/Contains/Distance/Intersects/Nearest/Outline/SnapPoints does not depend on Canvas Context.
• Every Geometry test still runs after deleting the Renderer.

Explain it to a five-year-old

Answer without saying “vector,” “AABB,” “hit test,” or “spatial index”:

1. Why do we find the shoebox first but refuse to announce that we found the toy as soon as we find the box?
2. After enlarging the toy city, why should the cotton-swab tip still look equally thick to our eyes?
3. When two toys overlap, how do we ensure that we pick the same one every time?
4. New question: if a string shrinks into one tiny point, how should the ruler measure it without producing “not a number”?