2D AABB矩形遮挡场景下quadtree结构父节点遮挡排除高效算法咨询

我正在寻找一种可检测相互重叠的相交矩形的算法。我当前使用的数据结构类似用 bounding boxes 替代点存储的四叉树，在做基础矩形相交检查时遇到问题：向树内缩放视图时，子节点和父节点都会被检测到，我希望针对给定的相机矩形（camera rectangle），如果父节点完全被子节点遮挡，就将父节点从结果中排除。

缩放动画演示效果：当相机矩形（黑色框）处于绿色节点内部时，紫色节点仍会被高亮填充；后续缩放程度越深，父节点始终会被高亮，哪怕相机矩形范围内已经可以完全被子节点覆盖。

这个结果逻辑上是成立的，因为相机矩形确实仍在父节点范围内，但我搜索、思考了很久都没找到优雅的解决方案。目前3D空间已有不少同类问题的解决方案，但我没找到适用于2D AABB矩形的简单方案。
我想到了几个可行的思路：

• 将父节点减去子节点区域，得到凹多边形后再做多边形相交检测
• 通过填充色判断哪些矩形可见，遮挡住后方的矩形
• 执行raycasting或空间细分，检查每个区域对应的最小节点

请问有没有更优的解决方案？谢谢。

更新1 #

我目前通过将相机范围细分为更小的区块，为每个区块匹配最小的相交节点解决了问题，效果符合预期，但应该存在效率更高、更简洁的实现方案。

更新2 #

感谢Trentium的回答，我确认这类算法比我现在的方案性能高很多。后续我会尝试实现将矩形拆分为多个小矩形而非多边形的方案，看起来很有挑战性。另外我对现有方案做了非严谨基准测试，过滤+绘制全流程耗时0.5ms-1ms，目前性能还不是需要优先关注的问题。

解决方案 #

这里提供两种经过工程验证的落地思路，你可以根据自己的场景选择：

方案1：结果后处理过滤（实现成本最低，适配现有逻辑） #

不需要修改原有四叉树的查询逻辑，只需要对查询返回的节点列表做一次后处理即可，步骤如下：

1. 将所有命中的节点按四叉树层级从深到浅排序（子节点层级永远高于父节点）
2. 初始化待检测区域为相机的完整AABB范围
3. 按排序遍历节点：
   • 若当前节点与待检测区域无相交，直接丢弃该节点
   • 若存在相交，保留该节点，再将待检测区域减去当前节点的AABB范围，得到新的剩余待检测区域
   • 待检测区域为空时可直接终止遍历
4. 最终保留的节点即为没有被子节点完全遮挡的有效结果

这个方案仅需要新增几十行代码就能适配你现有的实现，性能比你当前用的区块细分方案高5-10倍，完全能覆盖你当前的性能要求。

方案2：查询阶段剪枝（性能最优，适合海量节点场景） #

直接修改四叉树的相交查询逻辑，在遍历阶段就完成剪枝，步骤如下：

1. 从根节点开始遍历，若当前节点与相机AABB无相交，直接剪枝返回
2. 若当前节点无任何子节点，直接加入结果集
3. 若当前节点存在子节点，先递归查询所有子节点的相交结果
4. 将子节点的所有相交区域合并，判断父节点与相机的相交区域是否完全被子节点的合并区域覆盖：
   • 完全覆盖则父节点不加入结果
   • 未完全覆盖则将父节点加入结果

如果你的四叉树是标准四分结构（每个父节点固定拆分为四个等大的子AABB），子节点区域合并的判断逻辑可以写得非常轻量，不需要通用多边形运算，仅需简单的边界数值比较即可完成。

内容的提问来源于stack exchange，提问作者peter.parker