我正在寻找一种可以找到相互重叠的相交矩形的算法。
问题是我的数据结构类似于带有边界框而不是点的四叉树。我正在做一个基本的矩形相交检查，但问题是当我放大树时，检测到子节点和父节点，如果父节点完全被给定相机矩形的子节点遮挡，我想排除父节点。
正如您从上图中看到的，当相机矩形（黑框）位于绿色节点内时，紫色节点仍然突出显示（填充），因此随着我越来越放大，父母总是突出显示，即使相机矩形可以仅用子节点完全填充。
这是有道理的，因为相机矩形仍在父级内部，但我已经搜索并考虑了一段时间，似乎无法找到一个优雅的解决方案。对于 3D 空间，似乎有几种方法可以做到这一点，但对于 2D AABB 矩形，我找不到任何简单的方法。
我想到的几个解决方案：
- 从父节点中减去子节点，得到凹多边形，然后执行多边形相交。
- 使用填充颜色检查哪些矩形是可见的，因此会遮挡后面的矩形。
- 执行光线投射或细分并检查给定部分的最小节点。
有一个更好的方法吗？谢谢
更新 1
我已经通过将相机细分为更小的部分来解决这个问题，并且对于每个部分都找到了最小的相交节点。这可行，但必须有一种更有效和更清洁的方式来做到这一点。
更新 2
感谢 Trentium 的回答。我可以清楚地看到，像这样的算法会比我目前正在做的更高效。
最终我会将它实现为将一个矩形分割成更小的矩形，而不是多边形，这听起来像是一个有趣的挑战。
此外，我对当前方法做了一些非常不科学的基准测试，过滤和绘制所有内容需要 0.5ms-1ms，所以现在性能仍然不是问题。
