画布框选节点变慢时可以用四叉树先筛掉无关区域

从画布框选说起

画布应用常见一个交互：用户拖拽鼠标拉出矩形选框，把框住的节点全部选中。最直接的实现是遍历所有节点，逐个判断矩形是否相交：

function getNodesInSelection(selectRect) {
  return nodes.filter(node => {
    const r = { x: node.x, y: node.y, w: node.el.offsetWidth, h: node.el.offsetHeight };
    return !(r.x + r.w < selectRect.x || r.x > selectRect.x + selectRect.w
          || r.y + r.h < selectRect.y || r.y > selectRect.y + selectRect.h);
  });
}

每次 mousemove 都跑一遍。节点数量只有几十到上百个时，这种全量遍历通常够用。

节点数量继续增长后，问题会变成：选框只覆盖画布一小块区域，代码却仍然检查所有节点。

O(n) 遍历的痛点不在于单个判断慢，而在于绝大部分判断是浪费的。鼠标框选了画布左上角 3 个节点，代码仍然老老实实地和右下角 497 个节点逐一比对。

空间索引的思路：把位置当索引用

数据库用 B-tree 索引避免全表扫描，空间索引也用于减少全量扫描。它的索引键是 (x, y) 坐标。

核心策略只有一句话：先把"哪些节点可能在选框里"算出来，只对候选节点做精确判断。

这就是"粗筛 → 精筛"两阶段机制：

原始数据 ──[粗筛]──→ 候选集 ──[精筛]──→ 结果
 (n个)   空间索引    (k~m个)  AABB判断   (k个)

粗筛用空间结构快速淘汰整片不相关的区域，留下少量候选。精筛用精确的矩形相交判断收尾。精筛的复杂度是 O(m)，m 远小于 n。

四叉树的结构

四叉树（Quadtree）是最直观的空间索引之一。把画布递归四等分，直到每个格子里节点数小于某个阈值（通常 4~8 个）：

画布 800×600，共 18 个节点

┌──────────┬──────────┐
│ ··       │   ·      │
│   NW  ·  │  NE   ·  │
│          │     ··   │
├──────────┴──────────┤
│    ·    │      ·    │
│  SW  ·  │   SE ··   │
│  ·      │     ·  ·  │
└─────────┴───────────┘

四叉树:
              root (800×600)
      ┌────────┼────────┬────────┐
     NW      NE       SW       SE
  (400×300) (400×300)(400×300)(400×300)
  [5个节点] [4个节点] [3个节点] [6个节点]

每个节点存 4 样东西：

四个子象限的引用（NW / NE / SW / SE）
自己的空间边界
落在这个区域内的对象列表（仅叶子节点存储）

当某个象限里节点超过阈值，就继续分裂。直到每个叶子格子里节点数 ≤ 阈值。

查询过程

框选一个矩形后，从根开始递归：

query(rect, node):
  if node.bounds 与 rect 完全不相交 → return []  // 整块跳过
  if node 是叶子:
    return node.items.filter(item → AABB相交(item, rect))
  // 否则递归查四个子节点
  result = []
  for child in [node.NW, node.NE, node.SW, node.SE]:
    result.push(...query(rect, child))
  return result

关键在第一条分支。当某个象限的边界和选框完全不重叠时，这个象限及其所有子节点一次性全部跳过，回到用户之前的话——"只需要搜索涉及区域里面的节点就可以了"。

选框在 NE 角:
┌──────────┬──────────┐
│  ✗跳过   │  ✓进入   │
│   NW     │  NE ··   │
│          ├──────────┤
│          │     ✗    │
│          │     SE   │
│          │   (跳过)  │
└──────────┴──────────┘

SW 完全在选框外 → 整棵 SW 子树淘汰，0 次 AABB 判断
NE 与选框重叠 → 进入 NE，对其中 4 个节点做 AABB

复杂度分析

操作	全量遍历	四叉树
建树	O(1)	O(n log n)
单次查询	O(n)	O(log n + k)
插入/移动	O(1)	O(log n)

查询复杂度中，log n 来自树的层数（逐层定位到相关叶子），k 是结果集中的节点数（精筛阶段无法避免）。只要 k ≪ n，加速就是数量级的。

具体到数字：500 个节点，选框选中 3 个。

全量遍历：判断 500 次
四叉树（深度 4 层，选中的叶子格子里 8 个节点）：访问约 12~20 个树节点 + 8 次 AABB → 约 20 次判断

什么时候不该用

四叉树有自己的成本：

构建成本。每次插入、删除、移动节点都要更新树。如果节点频繁拖拽（信号处理实验室正是这样），移动操作要重新定位节点所在的格子。

JS 对象分配开销。四叉树在 JavaScript 中靠递归和对象属性访问实现。当节点数在 200 以下时，一次 for 循环 + 矩形判断可能比递归查询四叉树更快——函数调用和属性查找的开销反而成了瓶颈。

交叉点大约在 500~1000 个对象。低于这个数，粗暴遍历就是最优解。这就是信号处理实验室没有引入四叉树的理由：流程图的节点数几乎不可能超过 200。

不止于四叉树

四叉树只是空间索引家族的一员。相似的思路还有：

R-tree：为磁盘存储优化，数据库的空间索引首选。每个节点存一个最小包围矩形，节点之间可以有重叠。
网格索引：把空间切成等大的格子。实现比四叉树更简单，但浪费内存在空旷区域。
KD-tree：每次只沿一个维度切分，交替使用 x 和 y 轴。适合最近邻搜索。

它们共享同一个设计哲学：用空间换时间，用结构换遍历。预先花一点代价把对象按位置组织好，查询时就能跳过绝大部分无关对象。

总结

分级筛选的思路不限于空间索引。数据库的 B-tree、搜索引擎的倒排索引、布隆过滤器，本质上都是"粗筛 → 精筛"——先用廉价操作淘汰掉大部分数据，再用精确操作收尾。

下次写全量遍历的时候可以问自己一句：我要处理的对象里，有多少是真正有关的？

本文由 AI 辅助生成，可能存在错误或遗漏，请以实际资料和官方文档为准。