碰撞检测与边界判断

概述

碰撞检测（Collision Detection）是判断两个几何图形是否重叠或相交的算法。边界判断（Boundary Detection）则是判断一个图形是否在另一个区域范围内。它们是 Canvas 图形编辑器、游戏引擎和数据可视化交互的核心基础。

实际应用场景

场景	碰撞检测的用途
图形编辑器（Figma、Photoshop）	点击选中图形、框选多个图形、拖拽吸附对齐、裁切边界限制
游戏开发	子弹命中判定、角色与障碍物碰撞、拾取物品
数据可视化	鼠标悬停高亮图表元素、Tooltip 定位、Brush 框选数据点
拖拽交互	拖拽排序、放置区域判定、拖拽边界限制
地图应用	点击选中区域、判断标注是否在视口内

碰撞检测的两个阶段

在实际系统中，碰撞检测通常分为两个阶段：

宽相位（Broad Phase）：用简单快速的算法（如 AABB）排除掉大部分不可能碰撞的图形对，时间复杂度低
窄相位（Narrow Phase）：对宽相位筛选出的少量候选对，使用精确但更耗时的算法（如 SAT）做最终判定

平面向量基础

向量运算是所有碰撞检测算法的数学基础。如果你对向量已经很熟悉，可以跳过这一节。

向量基本运算

vector2d.ts
/** 二维向量 */
interface Vector2D {
  x: number;
  y: number;
}

/** 向量加法：两个向量首尾相连 */
function add(a: Vector2D, b: Vector2D): Vector2D {
  return { x: a.x + b.x, y: a.y + b.y };
}

/**
 * 向量减法：从 a 到 b 的方向向量
 * 几何意义：b - a = 从 a 指向 b 的箭头
 */
function subtract(a: Vector2D, b: Vector2D): Vector2D {
  return { x: b.x - a.x, y: b.y - a.y };
}

/** 向量数乘：拉伸或缩短向量 */
function scale(v: Vector2D, s: number): Vector2D {
  return { x: v.x * s, y: v.y * s };
}

/** 向量的长度（模），即向量箭头的长度 */
function length(v: Vector2D): number {
  return Math.sqrt(v.x * v.x + v.y * v.y);
}

/**
 * 单位向量（归一化）
 * 保持方向不变，将长度缩放到 1
 * 用途：只关心方向不关心大小时
 */
function normalize(v: Vector2D): Vector2D {
  const len = length(v);
  if (len === 0) return { x: 0, y: 0 };
  return { x: v.x / len, y: v.y / len };
}

/** 法向量（垂直向量）：将向量逆时针旋转 90° */
function perpendicular(v: Vector2D): Vector2D {
  return { x: -v.y, y: v.x };
}

点积（Dot Product）

点积是碰撞检测中最常用的运算，它的核心作用是计算投影。

\vec{a} \cdot \vec{b} = a_x \cdot b_x + a_y \cdot b_y = |\vec{a}||\vec{b}|\cos\theta

dot-product.ts
/** 点积：a · b = ax*bx + ay*by */
function dot(a: Vector2D, b: Vector2D): number {
  return a.x * b.x + a.y * b.y;
}

直觉理解：影子类比

想象太阳从正上方照射，一根棍子 $\vec{a}$ 在地面（ $\vec{b}$ 方向）上投下一个影子。点积就是衡量这个"影子"有多长：

         ↗ a（棍子）
        /
       / θ
      /____·________→ b（地面方向）
      |← 投影 →|

投影长度 = |a| × cos(θ)

当 $\vec{b}$ 是单位向量时， $\vec{a} \cdot \vec{b}$ 就是 $\vec{a}$ 在 $\vec{b}$ 方向上的投影长度（带正负号的标量）

点积的正负号含义：

条件	含义	$\theta$ 范围
$\vec{a} \cdot \vec{b} > 0$	$\vec{a}$ 和 $\vec{b}$ 大致同方向	$0° < \theta < 90°$
$\vec{a} \cdot \vec{b} = 0$	$\vec{a}$ 和 $\vec{b}$ 垂直	$\theta = 90°$
$\vec{a} \cdot \vec{b} < 0$	$\vec{a}$ 和 $\vec{b}$ 大致反方向	$90° < \theta < 180°$

在碰撞检测中的用途：SAT 算法需要将多边形的顶点投影到分离轴上，投影就是用点积算的。

投影公式

向量 $\vec{v}$ 在轴 $\vec{axis}$ 上的投影长度（标量）：

\text{proj} = \vec{v} \cdot \hat{axis} = \frac{\vec{v} \cdot \vec{axis}}{|\vec{axis}|}

其中 $\hat{axis}$ 是 $\vec{axis}$ 的单位向量。如果 $\vec{axis}$ 已经是单位向量，直接做点积即可。

projection.ts
/** 向量 v 在轴 axis 上的投影长度（标量值） */
function projectOntoAxis(v: Vector2D, axis: Vector2D): number {
  // 先将轴归一化为单位向量，再做点积
  const normalizedAxis = normalize(axis);
  return dot(v, normalizedAxis);
}

叉积（Cross Product，2D）

在 2D 中，叉积返回一个标量（不是向量），它的核心作用是判断方向关系。

\vec{a} \times \vec{b} = a_x \cdot b_y - a_y \cdot b_x = |\vec{a}||\vec{b}|\sin\theta

cross-product.ts
/**
 * 2D 叉积（返回标量）
 * 正值：b 在 a 的逆时针方向（左侧）
 * 负值：b 在 a 的顺时针方向（右侧）
 * 零：a 和 b 共线（平行）
 */
function cross(a: Vector2D, b: Vector2D): number {
  return a.x * b.y - a.y * b.x;
}

直觉理解：左右手判断

在 2D 平面中（屏幕坐标系，y 轴向下），叉积告诉你 $\vec{b}$ 在 $\vec{a}$ 的哪一侧：

叉积 > 0（b 在 a 的逆时针方向）   叉积 < 0（b 在 a 的顺时针方向）

      b ↗                                    ↗ a
      /                                     /
     / ）                                （ /
    /____→ a                          b ←__/

叉积的绝对值 = 平行四边形面积

$|\vec{a} \times \vec{b}|$ 等于以 $\vec{a}$ 和 $\vec{b}$ 为两边的平行四边形面积。三角形面积就是它的一半。

叉积在碰撞检测中的用途：

用途	说明
判断点在线段的哪一侧	射线法（点在多边形内）需要用到
判断线段是否相交	两条线段的端点分别在对方的两侧
判断点是否在凸多边形内	点与每条边做叉积，符号全部一致则在内部

碰撞检测算法

1. AABB 碰撞检测（未旋转矩形）

AABB（Axis-Aligned Bounding Box，轴对齐包围盒）是最简单、最高效的碰撞检测方法，只适用于没有旋转的矩形。

核心思想：两个矩形碰撞 = 在 X 轴上重叠且在 Y 轴上重叠。反过来说，只要有任何一个方向上不重叠，就不碰撞。

用一个具体的例子来理解，假设有两个矩形 A 和 B：

矩形 A: x=10, y=10, width=80, height=60
矩形 B: x=50, y=40, width=80, height=60

                  X 轴方向
     10      90
  A:  |======|          A 的范围：10 ~ 90
          50      130
  B:       |======|     B 的范围：50 ~ 130
          |==|          重叠部分：50 ~ 90 ✓

                  Y 轴方向
     10      70
  A:  |======|          A 的范围：10 ~ 70
          40      100
  B:       |======|     B 的范围：40 ~ 100
          |==|          重叠部分：40 ~ 70 ✓

两个轴都重叠 → 碰撞！

不碰撞的四种情况（满足任意一种就不碰撞）：

A 在 B 左边：  A.right < B.left      即 A.x + A.width < B.x
A 在 B 右边：  B.right < A.left      即 B.x + B.width < A.x
A 在 B 上边：  A.bottom < B.top      即 A.y + A.height < B.y
A 在 B 下边：  B.bottom < A.top      即 B.y + B.height < A.y

aabb-collision.ts
interface AABB {
  x: number;      // 左上角 x
  y: number;      // 左上角 y
  width: number;
  height: number;
}

/**
 * AABB 碰撞检测
 * 思路：判断是否 NOT 不碰撞（双重否定 = 碰撞）
 * 时间复杂度：O(1)，只做 4 次比较
 */
function isAABBCollision(a: AABB, b: AABB): boolean {
  return !(
    a.x + a.width < b.x ||   // A 完全在 B 的左边
    b.x + b.width < a.x ||   // A 完全在 B 的右边
    a.y + a.height < b.y ||  // A 完全在 B 的上边
    b.y + b.height < a.y     // A 完全在 B 的下边
  );
}

AABB 的价值

虽然 AABB 只能处理未旋转矩形，但它的核心价值在于宽相位预检测：给任何形状套一个 AABB 包围盒，先用 $O(1)$ 快速排除不可能碰撞的对。只有 AABB 碰撞的才进入精确检测。

2. 圆与圆碰撞

核心思想：两个圆碰撞，当且仅当圆心距离 ≤ 两个半径之和。

 碰撞：d ≤ r1 + r2                不碰撞：d > r1 + r2

    .-"""-.   .-"""-.              .-"""-.       .-"""-.
   /   ·   \ /   ·   \           /   ·   \     /   ·   \
  |   r1  d  r2   |              |   r1   |   |   r2   |
   \       / \       /            \       /     \       /
    '-...-'   '-...-'              '-...-'       '-...-'
      |←  d  →|                      |←    d      →|

  d = 圆心之间的距离
  r1, r2 = 两个圆的半径

circle-collision.ts
interface Circle {
  cx: number;     // 圆心 x
  cy: number;     // 圆心 y
  radius: number; // 半径
}

/**
 * 圆与圆碰撞检测
 * 优化技巧：比较距离的平方，避免 Math.sqrt() 开方运算
 */
function isCircleCollision(a: Circle, b: Circle): boolean {
  const dx = a.cx - b.cx;
  const dy = a.cy - b.cy;
  const distSquared = dx * dx + dy * dy;         // 距离的平方
  const radiusSum = a.radius + b.radius;
  return distSquared <= radiusSum * radiusSum;    // 比较平方，避免开方
}

为什么比较平方而不直接比较距离？

Math.sqrt() 是相对昂贵的运算。因为 $d \leq r_1 + r_2$ 等价于 $d^2 \leq (r_1 + r_2)^2$ （两边都是非负数），所以比较平方在数学上完全等价，但性能更好。在大量碰撞检测时这个优化很重要。

3. 圆与矩形碰撞

核心思想：找到矩形上离圆心最近的点，如果这个最近点到圆心的距离 ≤ 半径，就碰撞。

找最近点的方法：将圆心坐标 clamp（钳制）到矩形范围内。

场景 1：圆心在矩形外                场景 2：圆心在矩形内

  ┌─────────┐                      ┌─────────┐
  │         │    ·← 圆心           │    ·    │ ← 圆心在里面
  │         ·← 最近点              │  圆心   │   最近点就是圆心本身
  │         │   /                  │         │
  └─────────┘  / ← 距离           └─────────┘

circle-rect-collision.ts
/**
 * 圆与未旋转矩形的碰撞检测
 * Math.max/Math.min 的嵌套实现了 clamp 操作
 */
function isCircleRectCollision(circle: Circle, rect: AABB): boolean {
  // 把圆心坐标"钳制"到矩形范围内，得到矩形上离圆心最近的点
  const closestX = Math.max(rect.x, Math.min(circle.cx, rect.x + rect.width));
  const closestY = Math.max(rect.y, Math.min(circle.cy, rect.y + rect.height));

  // 计算最近点到圆心的距离（的平方）
  const dx = circle.cx - closestX;
  const dy = circle.cy - closestY;
  return dx * dx + dy * dy <= circle.radius * circle.radius;
}

4. 点与旋转矩形碰撞

当矩形有旋转时，直接用 AABB 的方式就不行了。核心技巧是：把点转换到矩形的局部坐标系，在局部坐标系中矩形是未旋转的。

具体例子：矩形中心在 (100, 100)，宽 80，高 60，旋转 45°。点 P 在 (130, 110)。

步骤 1：平移 → P' = (130-100, 110-100) = (30, 10)
步骤 2：反向旋转 -45° →
  localX = 30 × cos(-45°) - 10 × sin(-45°) ≈ 28.28
  localY = 30 × sin(-45°) + 10 × cos(-45°) ≈ -14.14
步骤 3：判断 |28.28| ≤ 40 且 |-14.14| ≤ 30 → true → 点在矩形内

point-in-rotated-rect.ts
interface RotatedRect {
  cx: number;       // 中心点 x
  cy: number;       // 中心点 y
  width: number;
  height: number;
  angle: number;    // 旋转角度（弧度）
}

/**
 * 判断点是否在旋转矩形内
 * 核心思路：反向旋转，转化为未旋转的 AABB 判断
 */
function isPointInRotatedRect(
  px: number,
  py: number,
  rect: RotatedRect
): boolean {
  // 1. 将点平移到以矩形中心为原点
  const dx = px - rect.cx;
  const dy = py - rect.cy;

  // 2. 反向旋转（-angle），让矩形"回正"
  const cos = Math.cos(-rect.angle);
  const sin = Math.sin(-rect.angle);
  const localX = dx * cos - dy * sin;
  const localY = dx * sin + dy * cos;

  // 3. 在局部坐标系中做简单的范围判断
  const halfW = rect.width / 2;
  const halfH = rect.height / 2;
  return Math.abs(localX) <= halfW && Math.abs(localY) <= halfH;
}

这个技巧非常通用

"转换到局部坐标系"是处理旋转图形碰撞的通用策略。不管是点击选中、裁切边界还是拖拽限制，只要涉及旋转，首先想到反向旋转到局部坐标系。

5. 分离轴定理（SAT）

SAT（Separating Axis Theorem）是处理任意凸多边形碰撞的通用算法。它是碰撞检测中最重要的算法之一，面试高频考点。

核心思想

分离轴定理

如果两个凸多边形不碰撞，那么一定存在一条直线（称为分离轴），使得两个多边形在这条线上的投影不重叠。反之，如果在所有候选轴上投影都重叠，则两个多边形碰撞。

用一个生活化的比喻来理解：想象你手里拿着一个手电筒，从不同角度照射两个物体到墙上。如果你能找到一个角度，让两个影子完全分开（不重叠），那这两个物体就没有碰撞。

为什么选边的法向量作为候选轴？

这是 SAT 中最不好理解的部分。直觉上，你可能会问：轴的方向有无穷多个，为什么只检查边的法向量？

原因：如果两个凸多边形能被一条线分开，那么这条分离线一定可以旋转到与某条边平行（想象把分离线贴到两个形状最近的边上）。分离轴垂直于分离线，所以分离轴一定与某条边的法向量平行。

两个矩形被分离线分开的例子：

  ┌────┐
  │ A  │         ┌────┐
  └────┘         │ B  │
   分离线→ - - - └────┘
         ↑
    分离轴（垂直于分离线）
    = 某条边的法向量方向

因此，只需检查两个多边形所有边的法向量即可。对于两个矩形（各 4 条边），平行边的法向量相同，所以实际只有 2+2=4 个候选轴。

完整的步骤演示（带数字）

用一个具体例子来走一遍完整的 SAT 流程。

题目：矩形 A 的四个顶点是 (0,0), (4,0), (4,3), (0,3)。矩形 B 的四个顶点是 (3,1), (7,1), (7,4), (3,4)。判断它们是否碰撞。

Y
·─────────·
·─────·───·──·
│  │  A  │  │  │
│     ·──│──·
·─────·  │ B │
1  2  3  4  5  6  7   X

第 1 步：获取候选轴

矩形 A 的边：(0,0)→(4,0) 方向 (4,0)，法向量 (0,4)→归一化 (0,1)。另一条边 (4,0)→(4,3) 方向 (0,3)，法向量 (-3,0)→归一化 (-1,0)，即 (1,0)。

矩形 B 没有旋转，法向量同 A。所以候选轴只有 2 个：(1,0) 和 (0,1)。

第 2 步：在轴 (1,0) 上投影（即 X 轴方向）

A 的顶点投影到 X 轴：0, 4, 4, 0 → 区间 [0, 4]
B 的顶点投影到 X 轴：3, 7, 7, 3 → 区间 [3, 7]
重叠？[0,4] 和 [3,7] → 4 ≥ 3 且 7 ≥ 0 → 重叠 ✓（重叠部分 [3,4]）

第 3 步：在轴 (0,1) 上投影（即 Y 轴方向）

A 的顶点投影到 Y 轴：0, 0, 3, 3 → 区间 [0, 3]
B 的顶点投影到 Y 轴：1, 1, 4, 4 → 区间 [1, 4]
重叠？[0,3] 和 [1,4] → 3 ≥ 1 且 4 ≥ 0 → 重叠 ✓（重叠部分 [1,3]）

结论：所有候选轴上投影都重叠 → 碰撞 ✓

如果不碰撞会是什么样？点击展开

把 B 移到 (5,1), (9,1), (9,4), (5,4)：

在轴 (1,0) 上：
  A 的投影：[0, 4]
  B 的投影：[5, 9]
  4 < 5 → 不重叠！

只要找到一个轴上不重叠就可以立即返回 不碰撞，无需继续检查其他轴。这就是 SAT 的"短路"特性，让不碰撞的情况检测得更快。

完整代码实现

sat-collision.ts
/**
 * 获取旋转矩形的四个顶点（世界坐标）
 * 先在局部坐标系算出四个角，再旋转+平移到世界坐标
 */
function getRotatedRectVertices(rect: RotatedRect): Vector2D[] {
  const { cx, cy, width, height, angle } = rect;
  const hw = width / 2;
  const hh = height / 2;
  const cos = Math.cos(angle);
  const sin = Math.sin(angle);

  // 四个角在局部坐标系中的位置：左上、右上、右下、左下
  const localCorners: [number, number][] = [
    [-hw, -hh], [hw, -hh], [hw, hh], [-hw, hh],
  ];

  // 旋转并平移到世界坐标
  return localCorners.map(([lx, ly]) => ({
    x: cx + lx * cos - ly * sin,
    y: cy + lx * sin + ly * cos,
  }));
}

/**
 * 获取凸多边形所有边的法向量（即 SAT 的候选分离轴）
 * 对每条边计算垂直方向并归一化
 */
function getAxes(vertices: Vector2D[]): Vector2D[] {
  const axes: Vector2D[] = [];
  for (let i = 0; i < vertices.length; i++) {
    const current = vertices[i];
    const next = vertices[(i + 1) % vertices.length];

    // 边向量：从 current 指向 next
    const edge: Vector2D = { x: next.x - current.x, y: next.y - current.y };

    // 边的法向量（垂直方向）就是候选分离轴
    const normal = perpendicular(edge);
    axes.push(normalize(normal));
  }
  return axes;
}

/**
 * 将多边形所有顶点投影到指定轴上
 * 返回投影的最小值和最大值，构成一个区间 [min, max]
 */
function projectPolygon(
  vertices: Vector2D[],
  axis: Vector2D
): [number, number] {
  // 投影 = 顶点向量与轴的点积
  let min = dot(vertices[0], axis);
  let max = min;

  for (let i = 1; i < vertices.length; i++) {
    const projection = dot(vertices[i], axis);
    if (projection < min) min = projection;
    if (projection > max) max = projection;
  }

  return [min, max];
}

/** 判断两个一维区间 [a0, a1] 和 [b0, b1] 是否重叠 */
function isOverlap(a: [number, number], b: [number, number]): boolean {
  return a[0] <= b[1] && b[0] <= a[1];
}

/**
 * SAT 碰撞检测：适用于任意两个凸多边形
 * 时间复杂度：O(n × m)，n 和 m 是两个多边形的顶点数
 */
function isSATCollision(
  verticesA: Vector2D[],
  verticesB: Vector2D[]
): boolean {
  // 收集所有候选分离轴
  const axesA = getAxes(verticesA);
  const axesB = getAxes(verticesB);
  const allAxes = [...axesA, ...axesB];

  for (const axis of allAxes) {
    const projA = projectPolygon(verticesA, axis);
    const projB = projectPolygon(verticesB, axis);

    // 只要有一个轴上投影不重叠 → 找到了分离轴 → 不碰撞
    if (!isOverlap(projA, projB)) {
      return false; // 短路返回，性能好
    }
  }

  // 所有轴上投影都重叠 → 碰撞
  return true;
}

旋转矩形碰撞（基于 SAT）

rotated-rect-collision.ts
/** 两个旋转矩形的碰撞检测，直接用 SAT */
function isRotatedRectCollision(
  a: RotatedRect,
  b: RotatedRect
): boolean {
  const verticesA = getRotatedRectVertices(a);
  const verticesB = getRotatedRectVertices(b);
  return isSATCollision(verticesA, verticesB);
}

SAT 性能优化

AABB 预检测：先用 AABB 包围盒做宽相位，不碰撞的直接排除
平行边去重：两个矩形各 4 条边，但平行边的法向量相同，所以实际只有 2+2=4 个候选轴
短路返回：找到第一个不重叠的轴就立即返回 false

SAT 的局限性

只适用于凸多边形。对于凹多边形，需要先做凸分解（Convex Decomposition）
不直接适用于曲线形状（如椭圆）。圆可以特殊处理：候选轴加上"圆心到多边形最近顶点"的方向
对于复杂形状，可以考虑使用 GJK 算法（基于闵可夫斯基差）

6. 射线法判断点在多边形内

射线法（Ray Casting）可以判断一个点是否在任意多边形（凸或凹）的内部。这在可视化中的 Tooltip 命中检测、地图区域点击等场景中非常实用。

核心思想

从点 P 向任意方向（通常选水平向右）发出一条射线，数射线与多边形边界的交叉次数：

奇数次 → 点在多边形内
偶数次 → 点在多边形外

偶数交叉（外部）：              奇数交叉（内部）：

  ┌─────┐                      ┌─────┐
  │     │                      │     │
P ·─────┼──────→              │  P ·─┼────→
  │     │  2次交叉            │     │  1次交叉
  └─────┘                      └─────┘
  → 外部                       → 内部

point-in-polygon.ts
/**
 * 射线法（Ray Casting）判断点是否在多边形内
 * 适用于任意多边形（凸或凹）
 * 从点 P 水平向右发射线，统计与多边形边的交叉次数
 */
function isPointInPolygon(
  point: Vector2D,
  polygon: Vector2D[]
): boolean {
  let inside = false;
  const n = polygon.length;

  for (let i = 0, j = n - 1; i < n; j = i++) {
    const xi = polygon[i].x, yi = polygon[i].y;
    const xj = polygon[j].x, yj = polygon[j].y;

    // 条件 1：边的 y 范围跨越了点的 y 坐标
    // 条件 2：射线与边的交点在点的右边
    const intersect =
      (yi > point.y) !== (yj > point.y) &&
      point.x < ((xj - xi) * (point.y - yi)) / (yj - yi) + xi;

    if (intersect) {
      inside = !inside; // 每次交叉翻转状态
    }
  }

  return inside;
}

射线法详细推导过程

对于多边形的每条边（从顶点 i 到顶点 j），我们需要判断从点 P 水平向右的射线是否穿过这条边。

条件 1：(yi > point.y) !== (yj > point.y)

这确保边的两个端点在射线的上下两侧（即边的 y 范围包含了点的 y 坐标）。如果两个端点都在射线上方或下方，射线不可能穿过这条边。

条件 2：point.x < 交点x

边与 y = point.y 的交点 x 坐标：通过线性插值 $x_{交点} = x_i + \frac{(x_j - x_i)(y_P - y_i)}{y_j - y_i}$ 。如果交点在点的右边，说明射线穿过了这条边。

边界情况

射线法对于点恰好在多边形边上的情况处理可能不一致。如果需要精确处理边界，可以单独检查点是否在任何一条边上（用点到线段的距离判断）。

7. 线段相交检测

判断两条线段是否相交在碰撞检测中经常用到，比如判断射线与多边形边的交叉、判断两个多边形的边是否穿插等。

核心思想：用叉积判断方向

两条线段 AB 和 CD 相交的充要条件是：

A 和 B 在线段 CD 的两侧（C→D 的叉积方向不同）
C 和 D 在线段 AB 的两侧（A→B 的叉积方向不同）

A 和 B 在 CD 两侧（叉积异号）：

       A
        \      C
         \    /
          ×  /   ← 交点
         / \/
        /   B
       D

  CD→CA 的叉积 > 0（A 在 CD 的左边）
  CD→CB 的叉积 < 0（B 在 CD 的右边）
  → A 和 B 在 CD 两侧 ✓

segment-intersection.ts
/**
 * 判断两条线段 AB 和 CD 是否相交
 * 原理：用叉积判断两个端点是否分别在对方线段的两侧
 */
function doSegmentsIntersect(
  a: Vector2D,
  b: Vector2D,
  c: Vector2D,
  d: Vector2D
): boolean {
  /**
   * 辅助函数：计算三点的方向
   * 返回叉积 (q-p) × (r-p) 的正负号
   * > 0: 逆时针  < 0: 顺时针  = 0: 共线
   */
  const crossSign = (p: Vector2D, q: Vector2D, r: Vector2D): number => {
    return (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x);
  };

  const d1 = crossSign(c, d, a); // A 在 CD 的哪一侧
  const d2 = crossSign(c, d, b); // B 在 CD 的哪一侧
  const d3 = crossSign(a, b, c); // C 在 AB 的哪一侧
  const d4 = crossSign(a, b, d); // D 在 AB 的哪一侧

  // 如果 A 和 B 在 CD 两侧，且 C 和 D 在 AB 两侧 → 相交
  if (d1 * d2 < 0 && d3 * d4 < 0) {
    return true;
  }

  // 特殊情况：某个端点恰好在另一条线段上（共线且在范围内）
  const onSegment = (p: Vector2D, q: Vector2D, r: Vector2D): boolean => {
    return (
      Math.min(p.x, r.x) <= q.x &&
      q.x <= Math.max(p.x, r.x) &&
      Math.min(p.y, r.y) <= q.y &&
      q.y <= Math.max(p.y, r.y)
    );
  };

  if (d1 === 0 && onSegment(c, a, d)) return true;
  if (d2 === 0 && onSegment(c, b, d)) return true;
  if (d3 === 0 && onSegment(a, c, b)) return true;
  if (d4 === 0 && onSegment(a, d, b)) return true;

  return false;
}

8. Canvas 内置命中检测

在浏览器中使用 Canvas 时，不一定要手动实现碰撞检测。Canvas 2D API 提供了内置的命中检测方法。

canvas-hit-test.ts
/**
 * 使用 Canvas 内置 API 进行命中检测
 * isPointInPath：判断点是否在填充区域内
 * isPointInStroke：判断点是否在描边线上
 */
function canvasHitTest(
  ctx: CanvasRenderingContext2D,
  mouseX: number,
  mouseY: number
): void {
  // 1. 先构建路径（不需要实际绘制）
  ctx.beginPath();
  ctx.rect(50, 50, 100, 80);

  // 2. 用 isPointInPath 判断点是否在路径填充区域内
  if (ctx.isPointInPath(mouseX, mouseY)) {
    console.log('鼠标在矩形内');
  }

  // 3. 用 isPointInStroke 判断点是否在路径描边线上
  ctx.lineWidth = 10; // 描边宽度影响命中区域
  if (ctx.isPointInStroke(mouseX, mouseY)) {
    console.log('鼠标在矩形边线上');
  }
}

/**
 * 实际使用示例：在 Canvas 编辑器中实现点击选中
 * 为每个图形创建路径并检测
 */
interface Shape {
  type: 'rect' | 'circle' | 'path';
  // ... 各种属性
}

function findShapeAtPoint(
  ctx: CanvasRenderingContext2D,
  shapes: Shape[],
  x: number,
  y: number
): Shape | null {
  // 从后往前遍历（后绘制的在上层，优先选中）
  for (let i = shapes.length - 1; i >= 0; i--) {
    const shape = shapes[i];
    ctx.beginPath();

    // 根据图形类型构建路径
    if (shape.type === 'rect') {
      // 如果有旋转，需要先 save/translate/rotate
      ctx.rect(/* ... */0, 0, 0, 0);
    } else if (shape.type === 'circle') {
      ctx.arc(/* ... */0, 0, 0, 0, Math.PI * 2);
    }

    if (ctx.isPointInPath(x, y)) {
      return shape; // 找到了！
    }
  }
  return null; // 没有命中任何图形
}

isPointInPath 的优势和局限

优势：

支持任意复杂路径（贝塞尔曲线、圆弧等），不需要自己实现碰撞算法
浏览器内部用 C++ 实现，性能不错

局限：

需要重新构建路径（beginPath + 绑路径），如果图形多可能有性能问题
不支持 Canvas 变换（translate/rotate/scale）后的坐标自动转换，需要手动处理或使用 DOMMatrix 做坐标变换
对于大量图形，空间索引 + 手动碰撞检测可能更高效

空间索引优化

当场景中有大量图形（数百到数万个）时，逐个做碰撞检测的性能无法接受（ $O(n^2)$ ）。空间索引通过将空间划分为区域，只检测同区域内的图形，大幅减少检测次数。

网格法（Grid）

最简单的空间索引。将画布划分为固定大小的网格，每个图形注册到所在的网格单元中。检测碰撞时，只检查同一个网格单元（及相邻单元）内的图形。

grid-spatial-index.ts
/**
 * 网格空间索引
 * 将画布划分为固定大小的格子，每个格子维护一个图形列表
 */
class SpatialGrid {
  private cellSize: number;
  private grid: Map<string, Set<number>>; // key: "col,row" → value: 图形 id 集合

  constructor(cellSize: number) {
    this.cellSize = cellSize;
    this.grid = new Map();
  }

  /** 生成网格单元的 key */
  private getKey(col: number, row: number): string {
    return `${col},${row}`;
  }

  /** 将一个 AABB 注册到它所覆盖的所有网格单元中 */
  insert(id: number, aabb: AABB): void {
    // 计算 AABB 覆盖哪些网格单元
    const startCol = Math.floor(aabb.x / this.cellSize);
    const endCol = Math.floor((aabb.x + aabb.width) / this.cellSize);
    const startRow = Math.floor(aabb.y / this.cellSize);
    const endRow = Math.floor((aabb.y + aabb.height) / this.cellSize);

    for (let col = startCol; col <= endCol; col++) {
      for (let row = startRow; row <= endRow; row++) {
        const key = this.getKey(col, row);
        if (!this.grid.has(key)) {
          this.grid.set(key, new Set());
        }
        this.grid.get(key)!.add(id);
      }
    }
  }

  /** 查询某个 AABB 范围内可能碰撞的图形 id */
  query(aabb: AABB): Set<number> {
    const result = new Set<number>();
    const startCol = Math.floor(aabb.x / this.cellSize);
    const endCol = Math.floor((aabb.x + aabb.width) / this.cellSize);
    const startRow = Math.floor(aabb.y / this.cellSize);
    const endRow = Math.floor((aabb.y + aabb.height) / this.cellSize);

    for (let col = startCol; col <= endCol; col++) {
      for (let row = startRow; row <= endRow; row++) {
        const key = this.getKey(col, row);
        const cell = this.grid.get(key);
        if (cell) {
          cell.forEach((id) => result.add(id));
        }
      }
    }
    return result;
  }

  /** 清空网格（每帧需要重建） */
  clear(): void {
    this.grid.clear();
  }
}

四叉树（Quadtree）

四叉树是一种自适应的空间索引，它递归地将空间四等分。与固定网格不同，四叉树能根据图形的分布密度自动调整划分粒度：图形密集的区域划分更细，稀疏区域不再细分。

quadtree.ts
/**
 * 四叉树节点
 * 当一个节点中的图形数量超过阈值时，自动分裂为 4 个子节点
 */
class QuadTree {
  private bounds: AABB;              // 当前节点覆盖的区域
  private maxObjects: number;         // 分裂阈值（超过这个数量就分裂）
  private maxDepth: number;           // 最大深度（防止无限递归）
  private depth: number;              // 当前深度
  private objects: { id: number; aabb: AABB }[]; // 存储的图形
  private children: QuadTree[] | null; // 四个子节点（未分裂时为 null）

  constructor(
    bounds: AABB,
    maxObjects = 10,
    maxDepth = 5,
    depth = 0
  ) {
    this.bounds = bounds;
    this.maxObjects = maxObjects;
    this.maxDepth = maxDepth;
    this.depth = depth;
    this.objects = [];
    this.children = null;
  }

  /** 将当前节点分裂为 4 个子节点 */
  private split(): void {
    const { x, y, width, height } = this.bounds;
    const hw = width / 2;
    const hh = height / 2;
    const nextDepth = this.depth + 1;

    this.children = [
      new QuadTree({ x, y, width: hw, height: hh }, this.maxObjects, this.maxDepth, nextDepth),           // NW 左上
      new QuadTree({ x: x + hw, y, width: hw, height: hh }, this.maxObjects, this.maxDepth, nextDepth),   // NE 右上
      new QuadTree({ x, y: y + hh, width: hw, height: hh }, this.maxObjects, this.maxDepth, nextDepth),   // SW 左下
      new QuadTree({ x: x + hw, y: y + hh, width: hw, height: hh }, this.maxObjects, this.maxDepth, nextDepth), // SE 右下
    ];

    // 把当前节点的图形重新分配到子节点
    for (const obj of this.objects) {
      this.insertIntoChildren(obj);
    }
    this.objects = [];
  }

  /** 将图形插入到合适的子节点中 */
  private insertIntoChildren(obj: { id: number; aabb: AABB }): void {
    if (!this.children) return;
    for (const child of this.children) {
      if (isAABBCollision(obj.aabb, child.bounds)) {
        child.insert(obj.id, obj.aabb);
      }
    }
  }

  /** 插入一个图形 */
  insert(id: number, aabb: AABB): void {
    // 如果已经分裂，直接插入子节点
    if (this.children) {
      this.insertIntoChildren({ id, aabb });
      return;
    }

    this.objects.push({ id, aabb });

    // 超过阈值且未达到最大深度 → 分裂
    if (this.objects.length > this.maxObjects && this.depth < this.maxDepth) {
      this.split();
    }
  }

  /** 查询与指定区域可能碰撞的所有图形 id */
  query(range: AABB): Set<number> {
    const result = new Set<number>();

    // 当前节点区域与查询区域不重叠，直接跳过
    if (!isAABBCollision(this.bounds, range)) {
      return result;
    }

    // 添加当前节点的图形
    for (const obj of this.objects) {
      if (isAABBCollision(obj.aabb, range)) {
        result.add(obj.id);
      }
    }

    // 递归查询子节点
    if (this.children) {
      for (const child of this.children) {
        const childResult = child.query(range);
        childResult.forEach((id) => result.add(id));
      }
    }

    return result;
  }

  /** 清空四叉树 */
  clear(): void {
    this.objects = [];
    this.children = null;
  }
}

空间索引对比

特性	网格法	四叉树	R-Tree
实现难度	简单	中等	复杂
适合场景	图形大小均匀、分布较均	图形分布不均匀	大量静态数据、范围查询
插入性能	$O(1)$	$O(\log n)$	$O(\log n)$
查询性能	$O(1)$ 到 $O(k)$	$O(\log n + k)$	$O(\log n + k)$
动态更新	重建代价低	需要重建或增量更新	增量更新较好
典型应用	游戏碰撞	Canvas 编辑器	地图引擎、数据库

实战：Canvas 编辑器中的点击选中

在 Canvas 图形编辑器中，点击选中某个图形是最基本的交互。当图形有旋转、缩放等变换时，需要结合坐标转换和碰撞检测。

canvas-editor-hit-test.ts
interface EditorShape {
  id: string;
  type: 'rect' | 'circle' | 'polygon';
  // 图形中心位置
  cx: number;
  cy: number;
  // 尺寸
  width: number;
  height: number;
  radius?: number;
  vertices?: Vector2D[];
  // 变换
  angle: number;     // 旋转角度（弧度）
  scaleX: number;
  scaleY: number;
  // 层级（越大越靠上）
  zIndex: number;
}

interface Viewport {
  offsetX: number;  // 画布水平偏移
  offsetY: number;  // 画布垂直偏移
  zoom: number;     // 缩放倍率
}

/**
 * 将屏幕坐标转换为世界坐标
 * 屏幕坐标 → Canvas 坐标 → 世界坐标
 */
function screenToWorld(
  screenX: number,
  screenY: number,
  canvas: HTMLCanvasElement,
  viewport: Viewport
): Vector2D {
  const canvasRect = canvas.getBoundingClientRect();

  // 1. 屏幕坐标 → Canvas 坐标（考虑 Canvas 元素的位置和 CSS 缩放）
  const canvasX = (screenX - canvasRect.left) * (canvas.width / canvasRect.width);
  const canvasY = (screenY - canvasRect.top) * (canvas.height / canvasRect.height);

  // 2. Canvas 坐标 → 世界坐标（考虑视口平移和缩放）
  const worldX = (canvasX - viewport.offsetX) / viewport.zoom;
  const worldY = (canvasY - viewport.offsetY) / viewport.zoom;

  return { x: worldX, y: worldY };
}

/**
 * 判断世界坐标点是否命中某个图形
 * 核心：将点转换到图形的局部坐标系后做判断
 */
function hitTestShape(
  worldPoint: Vector2D,
  shape: EditorShape
): boolean {
  // 1. 将点转换到图形的局部坐标系
  const dx = worldPoint.x - shape.cx;
  const dy = worldPoint.y - shape.cy;

  // 反向旋转
  const cos = Math.cos(-shape.angle);
  const sin = Math.sin(-shape.angle);
  const localX = (dx * cos - dy * sin) / shape.scaleX;
  const localY = (dx * sin + dy * cos) / shape.scaleY;

  // 2. 在局部坐标系中做命中判断
  switch (shape.type) {
    case 'rect': {
      const hw = shape.width / 2;
      const hh = shape.height / 2;
      return Math.abs(localX) <= hw && Math.abs(localY) <= hh;
    }
    case 'circle': {
      const r = shape.radius ?? Math.min(shape.width, shape.height) / 2;
      return localX * localX + localY * localY <= r * r;
    }
    case 'polygon': {
      if (!shape.vertices) return false;
      return isPointInPolygon({ x: localX, y: localY }, shape.vertices);
    }
    default:
      return false;
  }
}

/**
 * 在编辑器中查找点击位置命中的图形
 * 从上层到下层遍历，返回最上层的命中图形
 */
function findShapeAtPosition(
  screenX: number,
  screenY: number,
  canvas: HTMLCanvasElement,
  viewport: Viewport,
  shapes: EditorShape[]
): EditorShape | null {
  const worldPoint = screenToWorld(screenX, screenY, canvas, viewport);

  // 按 zIndex 从大到小排序（上层优先）
  const sorted = [...shapes].sort((a, b) => b.zIndex - a.zIndex);

  for (const shape of sorted) {
    if (hitTestShape(worldPoint, shape)) {
      return shape; // 返回最上层的命中图形
    }
  }

  return null;
}

性能优化建议

当图形数量很多时（上百个），逐个做命中测试会有性能问题。优化策略：

AABB 预过滤：先用世界坐标做 AABB 检查，排除大部分不可能命中的图形
空间索引：用四叉树管理图形，只查询鼠标位置附近的图形
缓存 AABB：每个图形的 AABB 包围盒只在变换改变时重新计算

边界判断与约束

未旋转图形的边界约束

boundary-constraint.ts
/** 将未旋转矩形限制在容器内 */
function clampRectInBounds(
  rect: AABB,
  bounds: { width: number; height: number }
): AABB {
  return {
    ...rect,
    x: Math.max(0, Math.min(rect.x, bounds.width - rect.width)),
    y: Math.max(0, Math.min(rect.y, bounds.height - rect.height)),
  };
}

旋转图形的边界约束

对于旋转后的图形，需要计算其 AABB 包围盒来判断边界：

rotated-boundary.ts
/** 计算旋转矩形的 AABB 包围盒 */
function getRotatedRectAABB(rect: RotatedRect): AABB {
  const vertices = getRotatedRectVertices(rect);
  let minX = Infinity, minY = Infinity;
  let maxX = -Infinity, maxY = -Infinity;

  for (const v of vertices) {
    minX = Math.min(minX, v.x);
    minY = Math.min(minY, v.y);
    maxX = Math.max(maxX, v.x);
    maxY = Math.max(maxY, v.y);
  }

  return { x: minX, y: minY, width: maxX - minX, height: maxY - minY };
}

/** 判断旋转矩形是否超出容器 */
function isOutOfBounds(
  rect: RotatedRect,
  bounds: { width: number; height: number }
): boolean {
  const aabb = getRotatedRectAABB(rect);
  return (
    aabb.x < 0 ||
    aabb.y < 0 ||
    aabb.x + aabb.width > bounds.width ||
    aabb.y + aabb.height > bounds.height
  );
}

图片裁切的边界约束

场景：图片编辑器中，图片可以旋转、缩放，裁切框固定不动。需要确保裁切框始终在旋转后的图片范围内，不露出空白区域。

核心思路：将裁切框的四个角点转换到图片的局部坐标系中，检查它们是否都在图片矩形范围内。

crop-boundary.ts
interface ImageTransform {
  cx: number;      // 图片中心 x
  cy: number;      // 图片中心 y
  width: number;   // 图片原始宽度
  height: number;  // 图片原始高度
  angle: number;   // 旋转角度
  scale: number;   // 缩放倍率
}

interface CropRect {
  x: number;
  y: number;
  width: number;
  height: number;
}

/** 检查裁切框是否完全在旋转图片范围内 */
function isCropInsideRotatedImage(
  crop: CropRect,
  img: ImageTransform
): boolean {
  // 裁切框的四个角点
  const cropCorners: Vector2D[] = [
    { x: crop.x, y: crop.y },
    { x: crop.x + crop.width, y: crop.y },
    { x: crop.x + crop.width, y: crop.y + crop.height },
    { x: crop.x, y: crop.y + crop.height },
  ];

  const cos = Math.cos(-img.angle);
  const sin = Math.sin(-img.angle);
  const halfW = (img.width * img.scale) / 2;
  const halfH = (img.height * img.scale) / 2;

  // 将每个角点转到图片的局部坐标系，检查是否在范围内
  return cropCorners.every((corner) => {
    const dx = corner.x - img.cx;
    const dy = corner.y - img.cy;
    // 反向旋转
    const localX = dx * cos - dy * sin;
    const localY = dx * sin + dy * cos;
    return Math.abs(localX) <= halfW && Math.abs(localY) <= halfH;
  });
}

/** 计算使裁切框不超出边界所需的最小缩放 */
function getMinScaleForCrop(
  crop: CropRect,
  img: ImageTransform
): number {
  const cropCorners: Vector2D[] = [
    { x: crop.x, y: crop.y },
    { x: crop.x + crop.width, y: crop.y },
    { x: crop.x + crop.width, y: crop.y + crop.height },
    { x: crop.x, y: crop.y + crop.height },
  ];

  const cos = Math.cos(-img.angle);
  const sin = Math.sin(-img.angle);
  let maxRatioX = 0;
  let maxRatioY = 0;

  for (const corner of cropCorners) {
    const dx = corner.x - img.cx;
    const dy = corner.y - img.cy;
    const localX = Math.abs(dx * cos - dy * sin);
    const localY = Math.abs(dx * sin + dy * cos);

    // 计算每个角点需要的最小缩放比
    maxRatioX = Math.max(maxRatioX, localX / (img.width / 2));
    maxRatioY = Math.max(maxRatioY, localY / (img.height / 2));
  }

  return Math.max(maxRatioX, maxRatioY);
}

拖拽时的边界限制与旋转时的自动缩放

constrain-operations.ts
/** 拖拽旋转图片时，二分法查找最大可移动距离 */
function constrainDrag(
  img: ImageTransform,
  crop: CropRect,
  deltaX: number,
  deltaY: number
): { dx: number; dy: number } {
  const newImg = { ...img, cx: img.cx + deltaX, cy: img.cy + deltaY };

  if (isCropInsideRotatedImage(crop, newImg)) {
    return { dx: deltaX, dy: deltaY };
  }

  // 二分查找最大可移动比例
  let lo = 0, hi = 1;
  for (let i = 0; i < 10; i++) {
    const mid = (lo + hi) / 2;
    const testImg = {
      ...img,
      cx: img.cx + deltaX * mid,
      cy: img.cy + deltaY * mid,
    };
    if (isCropInsideRotatedImage(crop, testImg)) {
      lo = mid;
    } else {
      hi = mid;
    }
  }

  return { dx: deltaX * lo, dy: deltaY * lo };
}

/** 旋转图片时，动态调整缩放保证裁切框不超出 */
function constrainRotation(
  img: ImageTransform,
  crop: CropRect,
  newAngle: number
): ImageTransform {
  const rotatedImg = { ...img, angle: newAngle };

  if (isCropInsideRotatedImage(crop, rotatedImg)) {
    return rotatedImg;
  }

  const minScale = getMinScaleForCrop(crop, rotatedImg);
  return { ...rotatedImg, scale: Math.max(img.scale, minScale) };
}

碰撞检测算法对比

算法	适用形状	时间复杂度	是否支持旋转	适用阶段
AABB	未旋转矩形	$O(1)$	否	宽相位
圆-圆	圆形	$O(1)$	不需要	窄相位
圆-矩形	圆 + 未旋转矩形	$O(1)$	否	窄相位
点-旋转矩形	点 + 矩形	$O(1)$	是	窄相位
射线法	点 + 任意多边形	$O(n)$	是	窄相位
线段相交	线段	$O(1)$	是	辅助算法
SAT	凸多边形	$O(n \cdot m)$	是	窄相位
GJK	凸形状（含曲线）	$O(n)$ 平均	是	窄相位
Canvas isPointInPath	任意路径	浏览器实现	是	窄相位

常见面试问题

Q1: 什么是 AABB？有什么优缺点？

答案：

AABB（Axis-Aligned Bounding Box）是轴对齐包围盒，即不旋转的矩形。判断两个 AABB 是否碰撞只需 4 次比较， $O(1)$ 。

优点：极其简单高效，适合宽相位预检测。缺点：不支持旋转图形。对于旋转的或不规则的形状，AABB 包围盒会比实际图形大很多，产生大量误检（false positive），需要窄相位再次精确判断。

Q2: 什么是宽相位和窄相位？为什么要分两个阶段？

答案：

宽相位（Broad Phase）：用简单快速的算法（AABB + 空间索引）快速筛掉绝大部分不可能碰撞的图形对。从 $O(n^2)$ 降到接近 $O(n)$
窄相位（Narrow Phase）：对宽相位筛选出的少量候选对，用精确算法（SAT、GJK 等）做最终判定

分两阶段的原因：精确算法比较耗时，如果对所有图形对都做精确检测，性能无法接受。宽相位用极低成本排除大部分无关图形对，让窄相位只处理少量候选。

Q3: 解释分离轴定理（SAT）的原理和步骤

答案：

SAT 的核心定理是：两个凸多边形不碰撞，当且仅当存在一条轴，使得两个多边形在该轴上的投影区间不重叠。

步骤：

收集所有候选分离轴（两个多边形所有边的法向量）
将两个多边形的所有顶点分别投影到每个候选轴上（用点积），得到两个区间 [min, max]
检查两个区间是否重叠
只要有任何一个轴上不重叠 → 不碰撞（短路返回）；所有轴都重叠 → 碰撞

候选轴选择边法向量的原因：如果存在分离轴，它一定与某条边的法向量平行。

Q4: SAT 能处理凹多边形吗？

答案：

不能直接处理。SAT 只适用于凸多边形。对于凹多边形，有两种方案：

凸分解：将凹多边形分解为多个凸多边形，对每对凸多边形做 SAT
使用其他算法：如 GJK 算法（也只适用凸形状，需先凸分解），或者直接用射线法判断顶点包含关系 + 边相交检测

Q5: 如何检测点是否在旋转后的矩形内？

答案：

核心技巧是将点坐标转换到矩形的局部坐标系中：

将点相对矩形中心平移：(px - cx, py - cy)
反向旋转 -angle（使矩形在局部坐标系中"回正"）
在局部坐标系中做简单的 AABB 判断：|localX| ≤ halfWidth && |localY| ≤ halfHeight

这个"转换到局部坐标系"的思路非常通用，适用于任何有变换的图形的命中检测。

Q6: 点积和叉积在碰撞检测中有什么用？

答案：

点积：计算投影长度。SAT 中将顶点投影到分离轴用的就是点积。判断两个方向是同向还是反向也用点积（正=同向，负=反向，零=垂直）
叉积（2D，返回标量）：判断方向关系。正值=逆时针/左侧，负值=顺时针/右侧，零=共线。用于射线法（判断点在边的哪一侧）、线段相交检测、判断点是否在凸多边形内

Q7: 射线法（Ray Casting）的原理是什么？

答案：

从目标点向任意固定方向（通常水平向右）发出一条射线，统计射线与多边形边界的交叉次数：

奇数次 → 点在多边形内
偶数次 → 点在多边形外

直觉理解：从多边形外部出发，每穿过一条边就进入/离开一次，奇数次穿越说明最终在内部。

射线法的优势在于适用于任意多边形（凸或凹），时间复杂度 $O(n)$ （n 为边数）。

Q8: 如何优化大量图形的碰撞检测？常见的空间索引有哪些？

答案：

常见的空间索引结构：

结构	原理	适用场景
均匀网格	将空间划分为固定大小的格子	图形大小均匀、分布较均匀
四叉树	递归四等分空间，自适应密度	图形分布不均匀（Canvas 编辑器）
R-Tree	基于最小包围矩形的树结构	大量静态数据、范围查询（地图）
BVH	层次包围盒树	游戏引擎、光线追踪

优化流程：1. 用空间索引做宽相位，将 $O(n^2)$ 的两两检测减少到只检测同区域内的图形 → 2. 对候选对做 AABB 预检测 → 3. 对 AABB 碰撞的做精确检测（SAT 等）。

Q9: 什么是 GJK 算法？它和 SAT 有什么区别？

答案：

GJK（Gilbert-Johnson-Keerthi）是另一种凸形状碰撞检测算法，基于闵可夫斯基差（Minkowski Difference）。核心思想：如果两个凸形状 A 和 B 的闵可夫斯基差包含原点，则它们碰撞。

特性	SAT	GJK
原理	寻找分离轴	闵可夫斯基差是否包含原点
适用形状	需要顶点列表	只需 support 函数（可处理曲线）
返回信息	是否碰撞	是否碰撞 + 最小穿透深度（配合 EPA）
性能	候选轴数量 = 边数之和	通常 3-4 次迭代
常用于	2D 游戏、编辑器	物理引擎（Box2D, Chipmunk）

Q10: Canvas 的 isPointInPath 和手动碰撞检测怎么选？

答案：

isPointInPath 适合：图形少（< 50 个），路径复杂（贝塞尔曲线），不想手动实现碰撞算法。

手动碰撞检测 适合：图形多（> 100 个），需要空间索引优化，需要碰撞信息（穿透深度、碰撞法向量），需要图形间的碰撞检测（不仅仅是点击命中）。

实际项目中，小型编辑器用 isPointInPath 足够，大型编辑器（如 Figma）一定是手动实现 + 空间索引。

Q11: Canvas 编辑器中如何实现点击选中图形？

答案：

完整流程：

坐标转换：鼠标事件坐标（屏幕坐标）→ Canvas 坐标 → 世界坐标（考虑视口平移和缩放）
遍历图形：从上层到下层（zIndex 大的优先），对每个图形做命中测试
命中测试：将世界坐标点转换到图形的局部坐标系（反向平移+旋转+缩放），在局部坐标系中做简单判断
返回结果：返回第一个命中的图形

性能优化：先用四叉树查询鼠标位置附近的图形，再逐个做精确命中测试。

Q12: 图片编辑器中，旋转图片时如何保证裁切框不超出图片范围？

答案：

将裁切框的四个角点反向旋转到图片的局部坐标系中，检查每个角点的绝对值是否小于等于图片缩放后的半宽/半高。如果超出，有两种策略：

限制旋转角度：不允许旋转到会超出的角度
自动放大图片：计算每个角点需要的最小缩放比，取最大值作为新的缩放

Q13: 如何判断两条线段是否相交？

答案：

用叉积判断。两条线段 AB 和 CD 相交的条件：

A 和 B 分别在线段 CD 的两侧（叉积异号）
C 和 D 分别在线段 AB 的两侧（叉积异号）

具体实现：计算四个叉积值 cross(CD, CA)、cross(CD, CB)、cross(AB, AC)、cross(AB, AD)，如果前两个异号且后两个异号，则相交。还需处理共线的特殊情况。

Q14: 碰撞检测中为什么常用距离的平方而不是实际距离？

答案：

Math.sqrt() 是一个相对昂贵的浮点运算。因为 $d \leq r$ 等价于 $d^2 \leq r^2$ （两边都是非负数时），所以比较平方在数学上等价，但避免了开方运算。在每帧需要做大量碰撞检测时（比如游戏中数千个碰撞对），这个优化累积起来效果显著。

Q15: 如何处理像素级精确的碰撞检测？

答案：

对于不规则形状（如精灵图中的非透明区域），可以使用像素级检测：

先做 AABB 预检测，确认两个图形的包围盒重叠
计算重叠区域
在重叠区域内，逐像素检查两个图形是否都有非透明像素
可以通过离屏 Canvas + getImageData() 获取像素数据

优化：降低采样精度（每隔几个像素检测一次），或使用预计算的碰撞遮罩（1-bit bitmap）。像素级检测通常只在宽相位和简单窄相位都判定碰撞后才使用。

概述​

实际应用场景​

碰撞检测的两个阶段​

平面向量基础​

向量基本运算​

点积（Dot Product）​

叉积（Cross Product，2D）​

碰撞检测算法​

1. AABB 碰撞检测（未旋转矩形）​

2. 圆与圆碰撞​

3. 圆与矩形碰撞​

4. 点与旋转矩形碰撞​

5. 分离轴定理（SAT）​

核心思想​

为什么选边的法向量作为候选轴？​

完整的步骤演示（带数字）​

完整代码实现​

旋转矩形碰撞（基于 SAT）​

6. 射线法判断点在多边形内​

核心思想​

7. 线段相交检测​

核心思想：用叉积判断方向​

8. Canvas 内置命中检测​

空间索引优化​

网格法（Grid）​

四叉树（Quadtree）​

空间索引对比​

实战：Canvas 编辑器中的点击选中​

边界判断与约束​

未旋转图形的边界约束​

旋转图形的边界约束​

图片裁切的边界约束​

碰撞检测算法对比​

常见面试问题​

Q1: 什么是 AABB？有什么优缺点？​

Q2: 什么是宽相位和窄相位？为什么要分两个阶段？​

Q3: 解释分离轴定理（SAT）的原理和步骤​

Q4: SAT 能处理凹多边形吗？​

Q5: 如何检测点是否在旋转后的矩形内？​

Q6: 点积和叉积在碰撞检测中有什么用？​

Q7: 射线法（Ray Casting）的原理是什么？​

Q8: 如何优化大量图形的碰撞检测？常见的空间索引有哪些？​

Q9: 什么是 GJK 算法？它和 SAT 有什么区别？​

Q10: Canvas 的 isPointInPath 和手动碰撞检测怎么选？​

Q11: Canvas 编辑器中如何实现点击选中图形？​

Q12: 图片编辑器中，旋转图片时如何保证裁切框不超出图片范围？​

Q13: 如何判断两条线段是否相交？​

Q14: 碰撞检测中为什么常用距离的平方而不是实际距离？​

Q15: 如何处理像素级精确的碰撞检测？​

相关链接​

概述

实际应用场景

碰撞检测的两个阶段

平面向量基础

向量基本运算

点积（Dot Product）

叉积（Cross Product，2D）

碰撞检测算法

1. AABB 碰撞检测（未旋转矩形）

2. 圆与圆碰撞

3. 圆与矩形碰撞

4. 点与旋转矩形碰撞

5. 分离轴定理（SAT）

核心思想

为什么选边的法向量作为候选轴？

完整的步骤演示（带数字）

完整代码实现

旋转矩形碰撞（基于 SAT）

6. 射线法判断点在多边形内

核心思想

7. 线段相交检测

核心思想：用叉积判断方向

8. Canvas 内置命中检测

空间索引优化

网格法（Grid）

四叉树（Quadtree）

空间索引对比

实战：Canvas 编辑器中的点击选中

边界判断与约束

未旋转图形的边界约束

旋转图形的边界约束

图片裁切的边界约束

碰撞检测算法对比

常见面试问题

Q1: 什么是 AABB？有什么优缺点？

Q2: 什么是宽相位和窄相位？为什么要分两个阶段？

Q3: 解释分离轴定理（SAT）的原理和步骤

Q4: SAT 能处理凹多边形吗？

Q5: 如何检测点是否在旋转后的矩形内？

Q6: 点积和叉积在碰撞检测中有什么用？

Q7: 射线法（Ray Casting）的原理是什么？

Q8: 如何优化大量图形的碰撞检测？常见的空间索引有哪些？

Q9: 什么是 GJK 算法？它和 SAT 有什么区别？

Q10: Canvas 的 isPointInPath 和手动碰撞检测怎么选？

Q11: Canvas 编辑器中如何实现点击选中图形？

Q12: 图片编辑器中，旋转图片时如何保证裁切框不超出图片范围？

Q13: 如何判断两条线段是否相交？

Q14: 碰撞检测中为什么常用距离的平方而不是实际距离？

Q15: 如何处理像素级精确的碰撞检测？

相关链接