① 拖拽防重叠：工艺图上摆放设备，重叠 = 不允许（今天的主战场）
② 命中检测：点击/悬停选中哪个图元（Day 34 已入门，今天系统化）
③ 拖拽预览提示：连线时靠近目标节点 → 自动吸附
④ 游戏化场景：粒子不穿透仪表盘、AGV 小车避障

所有碰撞判定归根结底是两类几何问题：

问题 A：两个形状有没有公共部分？（相交测试）
问题 B：一个点在不在某个形状里？（包含测试）

今天的三个算法都是这两问的组合。

AABB = Axis-Aligned Bounding Box（轴对齐包围盒）

┌────────────────┐
│ ┌─────┐        │      不管图元长啥样（设备图标、复杂 SVG 造型），
│ │ ░░░ │←─ 复杂 │      用一个"不旋转的矩形"把它框起来：
│ │░░░░░│   图元 │      这个框就是 AABB
│ └─────┘        │
└────────────────┘
"轴对齐"= 矩形的边平行于 x/y 轴（没旋转）

interface Box {
  x: number;      // 左边界
  y: number;      // 上边界
  w: number;      // 宽
  h: number;      // 高
}

/**
 * AABB 相交判定
 * 思路（反向思考更清晰）：
 *   什么时候【不相交】？—— a 在 b 的左边 / 右边 / 上边 / 下边，共四种"逃离"姿态
 *   排除这四种，剩下的就是相交
 */
function aabbIntersect(a: Box, b: Box): boolean {
  return !(
    a.x + a.w < b.x        // a 整体在 b 左侧
    || b.x + b.w < a.x     // a 整体在 b 右侧
    || a.y + a.h < b.y     // a 整体在 b 上方
    || b.y + b.h < a.y     // a 整体在 b 下方
  );
}

/**
 * 点 vs AABB（包含测试）—— Day 34 提过的矩形命中
 */
function pointInBox(p: { x: number; y: number }, b: Box): boolean {
  return p.x >= b.x && p.x <= b.x + b.w && p.y >= b.y && p.y <= b.y + b.h;
}

a.x+a.w < b.x          b.x+b.w < a.x
 ┌──┐   ┌───┐           ┌───┐   ┌──┐
 │a │   │ b │           │ b │   │a │
 └──┘   └───┘           └───┘   └──┘
   └─ 分离 ─┘             └─ 分离 ─┘

a.y+a.h < b.y          b.y+b.h < a.y
 ┌──┐                    ┌──┐
 │a │                    │b │
 └──┘                    └──┘
 ┌──┐                    ┌──┐
 │b │                    │a │
 └──┘                    └──┘
   └─ 分离 ─┘             └─ 分离 ─┘

四种都不成立 → 必然有重叠 ✅

优点：4 次比较，快到极致；实现无脑；缓存友好（每帧更新位置即可）
缺点：
  ① 旋转的图元不准（斜 45° 的长条，AABB 变得巨大）
  ② 凹形图元不准（L 形的 AABB 把缺口也框进去了）

工程态度：工业组态的图元 95% 是轴对齐矩形/圆形 → AABB 是默认选择。
        精确形状判定（多边形相交）属于游戏引擎领域，可视化很少需要。

interface Circle {
  x: number; y: number; r: number;
}

/**
 * 圆-圆相交判定
 * 数学：两圆圆心距 < 半径和 → 相交
 * 优化：两边平方比较，避免开方（sqrt 比乘法慢 10~30 倍）
 */
function circleIntersect(a: Circle, b: Circle): boolean {
  const dx = a.x - b.x;
  const dy = a.y - b.y;
  const rSum = a.r + b.r;
  return dx * dx + dy * dy < rSum * rSum;   // d² < (r1+r2)² ⟺ d < r1+r2
}
// Day 34 的 hitTestCircle 就是"点(半径0)-圆"的特例

// 新手写法：
const d = Math.sqrt(dx * dx + dy * dy);   // 开方：10~30 个时钟周期
return d < rSum;

// 平方写法：
return dx * dx + dy * dy < rSum * rSum;   // 2 次乘法：几个周期

// 一次检测省 20 周期看着不多，但：
// 100 个图元两两检测 = 4950 次/帧 × 20 周期 = 差距可测
// 更重要的：这是"性能意识"的肌肉记忆——一切能免掉的开销都不留

/**
 * 圆-圆相交深度：返回推离所需的位移向量
 * @returns null（不相交）或 {dx, dy, depth}
 */
function circleOverlap(a: Circle, b: Circle): { dx: number; dy: number; depth: number } | null {
  const dx = b.x - a.x, dy = b.y - a.y;
  const distSq = dx * dx + dy * dy;
  const rSum = a.r + b.r;
  if (distSq >= rSum * rSum) return null;

  const dist = Math.sqrt(distSq);        // 响应阶段才开方（判定阶段没开）
  // ⚠ 边界：两圆完全重合（dist=0）时方向未定义 → 任选一个方向
  if (dist === 0) return { dx: 1, dy: 0, depth: rSum };

  return {
    dx: dx / dist,                        // 单位方向向量（从 a 指向 b）
    dy: dy / dist,
    depth: rSum - dist,                   // 穿透深度
  };
}

问题：圆和矩形碰没碰？

神来之笔：找矩形上【离圆心最近的点】，
          它到圆心的距离 < 半径 → 相交

    ┌──────────┐
    │   ┌──────│──┐
    │   │最近点P│  │←─ 圆心 C
    │   └──────│──┘
    └──────────┘
    P 的求法：把圆心坐标"钳制"进矩形范围
    P.x = clamp(C.x, 矩形左, 矩形右)
    P.y = clamp(C.y, 矩形顶, 矩形底)

/**
 * 圆 vs AABB 相交判定（最近点法）
 */
function circleBoxIntersect(c: Circle, b: Box): boolean {
  // ① 圆心钳制到矩形内 → 矩形上离圆心最近的点
  const px = Math.min(Math.max(c.x, b.x), b.x + b.w);
  const py = Math.min(Math.max(c.y, b.y), b.y + b.h);

  // ② 最近点到圆心的距离 < 半径？
  const dx = c.x - px, dy = c.y - py;
  return dx * dx + dy * dy < c.r * c.r;    // 又是平方比较 ✅
}

情况 1：圆心在矩形内
  钳制后 P = 圆心本身 → 距离 0 < r → 相交 ✅（圆心进去了当然算）

情况 2：圆心在矩形外附近
  P 是圆心在矩形上的"投影" → 距离真实 → 正确判定 ✅

情况 3：圆心在矩形外的对角方向
  P 是最近的角点 → 圆恰好擦到角也判定相交 ✅
  （这就是最近点法对"角"的天然正确处理）

┌─────────┐          ┌─────┐
│ ░░░░░░░ │          │░░░░░│ ↗ 旋转 45° 的长条图元
│ ░░░░░░░ │   →      └─────┘
│ ░░░░░░░ │           它的 AABB（虚线）：
└─────────┘           面积暴涨，相邻图元"被误判碰撞"

/**
 * 旋转矩形（OBB）vs 点：把点变换到矩形的"局部坐标系"，退化成 AABB 问题
 * 
 * 局部系思维（Day 37 桌布模型的逆向应用）：
 *   与其在世界系里算旋转几何，不如把点"转回去"，在矩形自己的轴对齐系里算
 */
interface RotBox {
  x: number; y: number;    // 中心
  w: number; h: number;    // 宽高
  angle: number;           // 旋转角（弧度）
}

function pointInRotBox(p: { x: number; y: number }, b: RotBox): boolean {
  // ① 平移：以矩形中心为原点
  const lx = p.x - b.x;
  const ly = p.y - b.y;

  // ② 反向旋转 -angle（把矩形的倾斜"转正"）
  const cos = Math.cos(-b.angle), sin = Math.sin(-b.angle);
  const rx = lx * cos - ly * sin;
  const ry = lx * sin + ly * cos;

  // ③ 现在矩形是轴对齐的了 → 普通 AABB 包含测试
  return Math.abs(rx) <= b.w / 2 && Math.abs(ry) <= b.h / 2;
}
// OBB vs OBB（两个旋转矩形）= SAT 分离轴定理，游戏引擎经典题，
// 可视化领域极少需要——知道"变换到局部系"这个思路比背 SAT 更有价值

策略 A：禁止移动（最简单）
  拖到与别人重叠的位置 → 干脆不许放（回弹到原位）
  适用：强规则场景（电路设计）

策略 B：推离（今天实现）
  重叠时自动计算最小位移，把拖拽的图元"挤"到不重叠的位置
  适用：自由布局场景（组态画面摆放）

策略 C：仅警示（最宽松）
  允许重叠，但重叠的图元边框变红提示
  适用：布局建议场景（编辑器软约束）

/**
 * 策略 B 的核心：把 a 推到刚好不与 b 重叠
 * 用第三节的 circleOverlap：沿"方向向量的反方向"退回 depth 距离
 */
function pushApart(a: Circle, b: Circle): void {
  const hit = circleOverlap(a, b);
  if (!hit) return;

  // b 不动，a 沿反方向退 depth（各退一半的版本：双方各退 depth/2）
  a.x -= hit.dx * hit.depth;
  a.y -= hit.dy * hit.depth;
}

/**
 * AABB 推离：计算 x/y 两个方向各自的重叠量，沿【较小】的那个推出
 * （"最小穿透轴"策略——避免穿过对方）
 */
function pushApartBox(moving: Box, staticB: Box): void {
  // x 方向重叠量：两矩形在 x 上的公共区间长度
  const overlapX = Math.min(moving.x + moving.w, staticB.x + staticB.w)
                 - Math.max(moving.x, staticB.x);
  // y 方向重叠量
  const overlapY = Math.min(moving.y + moving.h, staticB.y + staticB.h)
                 - Math.max(moving.y, staticB.y);

  if (overlapX <= 0 || overlapY <= 0) return;   // 没重叠（判定又算了一遍）

  if (overlapX < overlapY) {
    // x 穿透更浅 → 沿 x 推出：往 moving 在 staticB 的哪边就往哪边推
    const pushDir = (moving.x + moving.w / 2) < (staticB.x + staticB.w / 2) ? -1 : 1;
    moving.x += pushDir * overlapX;
  } else {
    const pushDir = (moving.y + moving.h / 2) < (staticB.y + staticB.h / 2) ? -1 : 1;
    moving.y += pushDir * overlapY;
  }
}

// day45-collision.ts —— 防重叠图元拖拽场（连锁推离）
import { bootCanvas } from "../day29/canvas-boot.js";

const { ctx, cssWidth, cssHeight } = bootCanvas(document.querySelector("#board")!);

interface Coin {
  x: number; y: number; r: number;
  color: string;
  selected: boolean;
}

// 随机撒 12 个硬币（初始位置保证两两不重叠的简单生成法：网格 + 抖动）
const coins: Coin[] = [];
for (let i = 0; i < 12; i++) {
  coins.push({
    x: 100 + (i % 4) * 160 + Math.random() * 30,
    y: 100 + Math.floor(i / 4) * 140 + Math.random() * 30,
    r: 34,
    color: ["#4a6fa5", "#00a86b", "#b8860b", "#8b4a6b"][i % 4],
    selected: false,
  });
}

// ===== 1. 松弛求解：多轮迭代推离（处理连锁挤压）=====
/**
 * 关键认知：一次 pushApart 只解决一对。
 * 连锁情况（A→B→C）需要【多轮迭代】，每轮解决一轮挤压。
 * 轮数越多越精确，8~12 轮在视觉上已"完全松弛"。
 * ——这是物理引擎（Box2D 等）"迭代求解器"的最小原型
 */
function relax(iterations: number): void {
  for (let it = 0; it < iterations; it++) {
    for (let i = 0; i < coins.length; i++) {
      for (let j = i + 1; j < coins.length; j++) {
        pushApart(coins[i], coins[j]);     // 第六节的双圆推离
      }
    }
  }
}

/** 圆形推离（含边界：不推出画布） */
function pushApart(a: Coin, b: Coin): void {
  const dx = b.x - a.x, dy = b.y - a.y;
  const rSum = a.r + b.r;
  const distSq = dx * dx + dy * dy;
  if (distSq >= rSum * rSum || distSq === 0) return;

  const dist = Math.sqrt(distSq);
  const depth = rSum - dist;
  const ux = dx / dist, uy = dy / dist;    // a→b 单位向量

  // 被拖拽的不动（selected），另一个退；都没被拖则各退一半
  const aMove = a.selected ? 0 : b.selected ? 1 : 0.5;
  const bMove = b.selected ? 0 : a.selected ? 1 : 0.5;

  a.x -= ux * depth * aMove;
  a.y -= uy * depth * aMove;
  b.x += ux * depth * bMove;
  b.y += uy * depth * bMove;
}

// ===== 2. 渲染（重叠的变红警示——策略 C 的视觉反馈）=====
function hasOverlap(c: Coin): boolean {
  return coins.some((o) => o !== c && circleIntersect(c, o));
}

function render(): void {
  ctx.clearRect(0, 0, cssWidth, cssHeight);
  for (const c of coins) {
    ctx.beginPath();
    ctx.arc(c.x, c.y, c.r, 0, Math.PI * 2);
    ctx.fillStyle = c.selected ? "#00ff88" : c.color;
    ctx.fill();
    ctx.lineWidth = 3;
    ctx.strokeStyle = hasOverlap(c) ? "#ff4d4f" : "rgba(255,255,255,0.25)";   // 重叠红框
    ctx.stroke();
  }
}

// ===== 3. 拖拽交互（Day 34/38 套路）=====
let dragCoin: Coin | null = null;
let offX = 0, offY = 0;

canvas.addEventListener("mousedown", (e) => {
  const rect = canvas.getBoundingClientRect();
  const px = e.clientX - rect.left, py = e.clientY - rect.top;

  // 命中检测：圆（从上往上找——后画的在上面，Day 48 会正式讲优先级）
  for (let i = coins.length - 1; i >= 0; i--) {
    const c = coins[i];
    const dx = px - c.x, dy = py - c.y;
    if (dx * dx + dy * dy < c.r * c.r) {
      dragCoin = c;
      c.selected = true;
      offX = px - c.x; offY = py - c.y;
      break;
    }
  }
});

window.addEventListener("mousemove", (e) => {
  if (!dragCoin) return;
  const rect = canvas.getBoundingClientRect();
  dragCoin.x = e.clientX - rect.left - offX;
  dragCoin.y = e.clientY - rect.top - offY;

  // ⭐ 拖一步，松弛一轮：连锁推离实时发生
  relax(10);
  render();
});

window.addEventListener("mouseup", () => {
  if (dragCoin) dragCoin.selected = false;
  dragCoin = null;
  render();
});

render();

拖拽鼠标 → 更新被拖硬币位置 → relax(10 轮)：
  每轮：所有两两组合 pushApart（消除一轮挤压）
  连锁：A 顶着 B 顶到 C → 第 1 轮解决 A-B，第 2 轮解决 B-C……
        → 10 轮内视觉完全松弛
→ render：重叠的画红框（理论上 relax 后无重叠，红框只在拖拽"穿过"的瞬间闪现）

N 个图元两两检测：N × (N-1) / 2 次

N = 12：   66 次/帧     无压力
N = 100：  4,950 次/帧  AABB 每次 4 比较还行
N = 1000： 499,500 次/帧 ≈ 50 万次/帧 → 掉帧！

/**
 * 网格法（空间哈希的简化版）：
 * 把画布分成格子，图元只与自己【同格/邻格】的图元做精确检测
 * 
 * 效果：远处的图元（必然不同格）根本不进入两两循环
 *       1000 个图元的有效检测对从 50 万降到 ~2000（分布均匀时）
 */

// ① 分格
const CELL = 120;   // 格子尺寸 ≈ 图元直径的 1~2 倍
function cellOf(x: number, y: number): string {
  return `${Math.floor(x / CELL)}_${Math.floor(y / CELL)}`;
}

// ② 图元登记进格子
const grid = new Map<string, Coin[]>();
function rebuildGrid(): void {
  grid.clear();
  for (const c of coins) {
    const key = cellOf(c.x, c.y);
    (grid.get(key) ?? grid.set(key, []).get(key)!).push(c);
  }
}

// ③ 检测时只查邻格
function* neighbors(c: Coin): Generator<Coin> {
  const [cx, cy] = cellOf(c.x, c.y).split("_").map(Number);
  for (let dx = -1; dx <= 1; dx++) {
    for (let dy = -1; dy <= 1; dy++) {
      for (const other of grid.get(`${cx + dx}_${cy + dy}`) ?? []) {
        if (other !== c) yield other;
      }
    }
  }
}
// 完整的网格法还要处理"图元跨格"（登记进多个格子）——可视化场景先掌握思想

组态编辑器实际规模：几十~两百个节点
→ 朴素两两 AABB 就够了（<2 万次比较/帧，毫无压力）
→ 什么时候才需要空间分区：上千粒子、大规模 AGV 仿真
纪律（Day 41）：先测量，超标了再上数据结构。

function circleBox(c: Circle, b: Box): boolean {
  const px = Math.min(Math.max(c.x, b.x), b.x + b.w);
  const py = Math.min(Math.max(c.y, b.y), b.y + b.h);
  const d = Math.sqrt((c.x - px) ** 2 + (c.y - py) ** 2);
  return d < c.r;
}

Day 45 碰撞检测
├── 问题本质
│   ├── 相交测试（形状 vs 形状）
│   └── 包含测试（点 vs 形状）
├── 三大算法
│   ├── AABB：排除四种分离姿态（4 次比较）
│   ├── 圆-圆：距离平方比较（免 sqrt）
│   └── 圆-矩形：最近点法（clamp 圆心进矩形）
├── 进阶认知
│   └── 旋转矩形 = 变换到局部系退化成 AABB
├── 响应策略
│   ├── 禁止移动 / 推离 / 仅警示
│   └── AABB 推离 = 最小穿透轴
├── 连锁求解
│   └── 多轮 relax 迭代（物理引擎求解器雏形）
├── 规模化
│   └── 空间分区网格（粗筛+精筛）
└── 实战
    └── 防重叠拖拽场（推离 + 红框警示 + 命中倒序）