面向Dashboard应用的Widget矩形重叠检测有哪些高效数据结构与方法？

首先所有方案的核心判定基础是轴对齐矩形的重叠逻辑（Dashboard场景下Widget均为无旋转的轴对齐矩形，不需要考虑斜切场景）：

两个矩形不存在重叠的充分条件，满足任意一条即可直接判定为不重叠：

• 矩形1的右边界 ≤ 矩形2的左边界
• 矩形1的左边界 ≥ 矩形2的右边界
• 矩形1的下边界 ≤ 矩形2的上边界
• 矩形1的上边界 ≥ 矩形2的下边界
  只要以上四条全不满足，两个矩形就一定存在重叠。

按Widget规模选适配的数据结构 #

小量级场景（<100个Widget） #

直接暴力全量遍历即可。

• 实现逻辑：把所有已有Widget存成普通数组，新增检测时挨个套用上面的重叠判定公式，收集所有命中的对象
• 优势：代码零复杂度，没有额外的索引维护开销，性能完全足够，不要上来就上复杂空间结构过度设计。

中等量级场景（100~1000个Widget） #

用网格分桶（Grid Bucketing），是Dashboard场景性价比最高的方案。

• 实现逻辑：把整个Dashboard画布按固定大小切分为二维网格，网格单元大小取场景下常见的Widget最小尺寸（一般和Dashboard自带的网格吸附单元对齐），每个网格单元维护一个列表，存放所有和该单元有交集的Widget对象
• 检测流程：拿到新增Widget后，先计算它的坐标范围覆盖了哪几个网格单元，只需要遍历这些单元内存的Widget列表做精准重叠判定，不需要扫全画布的Widget
• 维护成本：新增/删除/移动Widget时，只需要更新该Widget覆盖的那几个网格单元的列表即可，没有复杂的树结构平衡调整开销，比其他空间结构的更新成本低很多，完全适配Dashboard里Widget频繁拖拽移动的场景。

大量级场景（>1000个Widget，超大型可视化画布） #

使用专用空间索引结构：

• R树（R-Tree）：天生适配轴对齐矩形的范围查询需求，每个树节点存储对应区域的外接边界框，查询时可以直接跳过完全不与待检测Widget重叠的分支节点，大幅减少遍历量；同时对动态插入、删除操作的支持友好，不需要全量重建索引，适合Widget位置高频变动的场景。
• 自适应四叉树（Quadtree）：和网格分桶逻辑类似，但会根据每个块内的Widget密度自适应细分：如果单个块内的Widget数量超过阈值，就把块拆成四个等大的子块，直到每个块内的Widget数量低于设定阈值。相比固定大小的网格，在Widget分布极不均匀（比如局部挤了大量小Widget、其他区域都是大尺寸Widget）的场景下，查询冗余更少，内存利用效率更高。

工程落地优化点 #

• 快速剪枝：做矩形判定时优先做轴向上的边界比较，只要有一个轴上完全分离就直接跳过，减少不必要的运算
• 坐标整数化：如果Dashboard的Widget支持网格吸附，所有坐标统一存为整数，把浮点数比较替换为整数比较，降低运算开销
• 结果去重：因为同一个Widget可能被多个网格/树节点同时标记为潜在重叠对象，收集结果时需要按Widget的唯一ID去重，避免重复返回
• 避坑：不要为了追求“高级感”选择KD树、范围树这类适合高维点查询的结构，这类结构在二维矩形重叠检测的场景下性能远不如上述方案，还会带来极高的维护成本。

内容的提问来源于stack exchange，提问作者Cameron Toy