第 8 章：检查边缘之前，先找到大盒子

从一个五岁孩子也能理解的游戏开始

本章唯一的真相：命中测试是一个几何查询系统，而不是几条 if 语句。

把二十件玩具放进四个鞋盒。现在闭上眼睛，用一根棉签寻找“最上面那根蓝色细绳”。你有两种选择：取出并触碰每件玩具；或者先判断棉签落进了哪个鞋盒，只检查那个盒子里的玩具，最后测量棉签离细绳有多远。

先预测会发生什么。蓝色细绳像头发一样细。孩子把玩具城市放大十倍后，棉签必须靠多近才算命中？如果容差也扩大十倍，点击会变得更容易，还是难度保持不变？如果一个矩形旋转了 45°，仅仅触碰它那个较大的、未旋转的包围盒，能否证明你真的触碰到了矩形？

这是一个两阶段查询。第一阶段可以保留少量额外的候选对象，但绝不能漏掉真正的目标。只有第二阶段才会检查填充、描边、控制柄、连接线以及经过变换后的真实几何形状。结果不只是 true/false：它还会告诉工具命中了谁、命中了哪个部位、距离有多远，以及世界坐标点和局部坐标点分别在哪里。

将玩具对应到 Canvas

这个类比有其局限。真实的鞋盒具有体积，而二维 AABB 只是与坐标轴对齐的范围。与 AABB 相交是必要条件，但不是充分条件。负缩放会翻转局部方向，但宽度和高度不能因此变成负距离。数学上宽度为零的线没有面积，但 UI 可以通过屏幕容差让它可点击。浮点数也不是具有无限精度的尺子，因此边界判定需要 epsilon。

先破除错误直觉

• “x <= px <= x + width 就够了。” 旋转、父级变换、负缩放、线段和贝塞尔曲线会立刻让它失效。
• “直接调用 ctx.isPointInPath() 最准确。” 这会把命中规则与渲染器、上下文状态和浏览器环境焊死在一起。Node 测试、空间索引以及 SVG/GPU 渲染器都无法复用这些规则。
• “命中 AABB 就是真正命中。” 旋转后的矩形会在其 AABB 的四角附近留下大片空白区域。
• “用固定的 5 个世界单位来点击一条线。” 在缩放比例为 0.1 时，这相当于 0.5 px，几乎不可能命中；在缩放比例为 10 时，这相当于 50 px，从很远的地方也会命中。
• “返回第一个候选对象。” 空间索引不保证 Z 轴顺序；应按照页面的堆叠规则比较候选对象。
• “永久缓存边界。” 当形状、父级变换、描边或几何发生变化时，过期的包围盒会使目标消失或产生幽灵命中。

生产级工具包

前置契约

第 4 章提供可逆的 worldToScreen/screenToWorld 变换以及有限且为正的相机缩放比例。第 5 章为形状提供稳定 ID、父子关系、Z 轴顺序、局部变换和几何提供器。第 7 章只传入一个标准化的世界坐标点。GeometryKernel 不导入任何 Canvas API、React 或 DOM。

形式化知识

二维向量是 v=(x,y)。点积 a·b=ax·bx+ay·by 支持投影和角度测试。二维标量叉积 a×b=ax·by-ay·bx 的符号可以判断向左转还是向右转、线段是否相交以及多边形的环绕方向。距离是差向量的长度。点到线段的距离并不是点到无限延伸直线的距离：先计算 t=clamp(((p-a)·(b-a))/|b-a|²,0,1)，再使用 a+t(b-a)。当线段长度趋近于零时，将其视为一个点。

线段相交必须处理普通交叉、共线重叠和端点接触。产品还必须决定这些情况返回一个点、一个区间，还是仅返回布尔值。多边形包含判断可以使用奇偶规则或非零环绕规则；带孔洞或自相交的多边形需要明确指定填充规则。二次或三次贝塞尔曲线的窄阶段可以使用解析法求最近点、递归细分，或在给定误差界限下进行扁平化。不要把每条曲线都近似为固定的十条线段，然后假装精度处处一致。

AABB 是 {minX,minY,maxX,maxY}，非常适合用于索引和宽阶段筛选。OBB 具有一个中心、两条单位轴和半范围；它能更紧密地包裹旋转后的目标，但相交计算成本更高。一种常见实现是用世界矩阵变换局部几何的各个角点，然后取各坐标的最小值和最大值，生成一个保守的变换后 AABB。嵌套组必须按照既定的乘法顺序组合矩阵。应用负缩放后，要重新排列最小值和最大值。不可逆矩阵只能产生一个可诊断的未命中结果，绝不能扩散 NaN 值。

填充命中使用区域内部判定规则。描边命中会将中心线向外扩展“此形状经过真实变换后的描边半宽 + toleranceWorld”，同时还要考虑线帽、线连接和斜接。绝不能把局部空间中的 strokeWidth 或局部距离直接加到世界容差上。对于均匀相机，toleranceWorld = toleranceScreen / abs(cameraScale)。对于非均匀视图变换，应使用逆矩阵变换屏幕容差向量，或直接在屏幕空间中进行精确比较。调整大小和旋转控制柄通常在屏幕上保持 8–12 CSS px；它们绝不能随世界空间一起缩放。

宽阶段接口只承诺返回“所有可能相交的对象”。其实现可以从线性扫描开始，之后再改为 R 树、四叉树或 BVH。每个形状的几何提供器负责回答 containsPoint、distanceToPoint、intersectsRectangle、nearestPoint、outline 和 snapPoints 的窄阶段查询。应依次按照浮层控制柄、选中对象规则、Z 轴顺序、距离和稳定 ID，对查询结果进行确定性排序。这样，即使索引的返回顺序发生变化，重放结果也能保持稳定。

证据与兼容性（已于 2026-08-29 验证）

GeometryKernel 使用普通数值结构，并可在 Node 中运行。MDN DOMMatrix 和 DOMMatrixReadOnly.inverse() 是浏览器适配器的实用参考资料。MDN 指出，当逆矩阵不可用时，分量可能会变为 NaN，因此边界处必须验证数值是否有限。Canvas 的 isPointInPath() 和 isPointInStroke() 可用于差分测试，但不能作为领域真值。替换 Renderer 后，内核测试应当无需修改仍能通过。

本章的工程增量

起点： Select Tool 扫描每一个 Shape，并使用未旋转矩形的 if。终点： 一个独立的 GeometryKernel 提供稳定的查询。线性 Broad Phase 可以替换为空间索引，而无需更改 Narrow Phase 或结果语义。

添加以下文件和接口：

• src/engine/geometry/vector.ts：向量、点积、叉积和 epsilon；
• src/engine/geometry/bounds.ts：AABB、变换和相交；
• src/engine/geometry/providers.ts：Geometry Provider 注册表；
• src/engine/geometry/GeometryKernel.ts：Broad/Narrow 查询和确定性排序；
• src/engine/geometry/__tests__/properties.test.ts：旋转、负 Scale、退化 Shape 和容差属性；
• tests/browser/hit-tolerance.spec.ts：不同 Zoom 级别下相同的屏幕距离。

这个完整的 TypeScript 内核实现了矩形和折线查询。之后可以通过添加 Provider 来支持椭圆和贝塞尔曲线，而无需更改 Tool。首先明确一个很容易被代码掩盖的约定：在这个教学内核中，strokeWidthWorld 是一种不会随 Shape Transform 缩放的世界空间宽度，而 Entry.bounds 是包含半个描边宽度的变换后世界 AABB。如果产品选择“缩放 Shape 时也缩放其 Stroke”，Provider 就必须先计算真实的变换后轮廓，而不能把世界空间容差加到局部距离上。示例 Camera 仅包含旋转、平移和均匀 Zoom；对于非均匀 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;
  }
}

Provider 的完整公共约定还包含以下能力。Selection、Snapping 和 Spatial Index 依赖这些能力，而非 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[];
}

属性测试关注不变量，而不是只测试三个看起来不错的坐标：

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();
  });
});

运行 pnpm vitest run src/engine/geometry。每次属性测试都应在没有 DOM 环境的情况下通过。运行 pnpm playwright test tests/browser/hit-tolerance.spec.ts。在 25%、100% 和 400% Zoom 下，距离线条 4 px 的点应命中，而距离 6 px 的点应未命中。记录候选项数量，以便第 15 章替换空间索引时复用同一断言。

回到鞋盒的比喻。索引只会说：“棉签可能落在了这些盒子里。”Provider 会触碰玩具的真实边缘，而 Z-Order 决定最上层的哪个玩具最先被取出。即使画笔变成 GPU Renderer，盒子、尺子和结果记录也保持不变。

故意破坏它

用证据证明通过

• 向量、点积、叉积、点到线段距离、直线相交、Polygon/Winding 和贝塞尔策略各自都有独立定义。
• AABB 仅用于 Broad Phase；需要时由 OBB 或真实几何体支持 Narrow Phase。
• 变换后的 Bounds 支持旋转、嵌套、负 Scale 和浮点 epsilon。
• Fill、Stroke Expansion 和 Handle Geometry 使用明确且彼此不同的规则。
• HitResult 包含 ID、部位、距离、局部/世界点以及 Z 信息。
• Bounds/Contains/Distance/Intersects/Nearest/Outline/SnapPoints 不依赖 Canvas Context。
• 删除 Renderer 后，每个 Geometry 测试仍然可以运行。

给五岁小朋友讲明白

回答时不要说“向量”“AABB”“命中测试”或“空间索引”：

1. 为什么我们先找到鞋盒，却不肯在找到盒子的那一刻就宣布找到了玩具？
2. 放大玩具城市后，为什么棉签尖在我们眼中仍应保持同样的粗细？
3. 当两个玩具重叠时，怎样确保我们每次都拿到同一个？
4. 新问题：如果一根绳子缩成一个小点，尺子应该怎样测量它，才不会产生“非数字”？