mar*_*all 4 algorithm computational-geometry
我有一组轴平行的二维矩形，由它们的左上角和右下角定义（都在整数坐标中）。给定一个点查询，你如何有效地确定它是否在一个矩形中？我只需要一个是/否的答案，不需要担心它在哪个矩形中。
我可以通过查看 x 是否在 x1 和 x2 之间以及 y 是否在 y1 和 y2 之间来检查 (x,y) 是否在 ((x1, y1), (x2, y2)) 中。我可以为每个矩形单独执行此操作，这些矩形以矩形数量的线性时间运行。但是由于我有很多矩形并且我会做很多点查询，所以我想要更快的东西。
答案在一定程度上取决于您有多少个矩形。蛮力方法依次检查每个矩形对的坐标：
found = false
for each r in rectangles:
if point.x > r.x1 && point.x < r.x2:
if point.y > r.y1 && point.y < r.y2
found = true
break
您可以通过将矩形按区域排序并查看“边界矩形”来提高效率。然后，您在不断减少的边界矩形树中进行二分搜索。这需要更多的前期工作，但它使查找 O(ln(n)) 而不是 O(n) - 对于大型矩形集合和许多查找，性能改进将是显着的。您可以在此较早的答案中看到一个版本（它查看矩形与一组矩形的交集 - 但您很容易适应“内部点”）。更一般地说，看看四叉树的主题，这正是解决这样的二维问题所需的数据结构类型。
一种效率稍低（但速度更快）的方法会按左下角（例如）对矩形进行排序 - 然后您只需要搜索矩形的一个子集。
如果坐标是整数类型，您可以制作一个二进制掩码 - 那么查找是一个单一的操作（在您的情况下，这将需要一个 512MB 的查找表）。如果您的空间相对稀疏（即“未命中”的概率非常大），那么您可以考虑使用欠采样位图（例如使用坐标/8）-然后地图大小下降到 8M，如果您有“不击中”，您可以省去更仔细观察的费用。当然，您必须向下舍入左/底部，并向上舍入顶部/右侧坐标才能使这项工作正确。
用一个例子扩展一点：
想象一下，x 坐标可以是 0 - 15，y 坐标可以是 0 - 7。有三个矩形（所有[x1 y1 x2 y2]：[2 3 4 5]，[3 4 6 7]并且[7 1 10 5]我们可以在矩阵中绘制这些（我标志着左下角用矩形的数量-注意1和2重叠）：
...xxxx.........
...xxxx.........
..xxxxx.........
..x2xxxxxxx.....
..1xx..xxxx.....
.......xxxx.....
.......3xxx.....
................
你可以把它变成一个零和一的数组——这样“此时是否有一个矩形”与“这个位是否设置”相同。一次查找将为您提供答案。为了节省空间，您可以对数组进行下采样——如果仍然没有命中，你就有了答案，但是如果命中了，你需要检查“这是真的吗”——所以它节省的时间更少，节省的时间取决于稀疏性你的矩阵（稀疏=更快）。子采样数组如下所示（2x 下采样）：
.oxx....
.xxooo..
.oooxo..
...ooo..
我x过去常常标记“如果你达到这一点，你肯定在一个矩形中”，并o说“其中一些是一个矩形”。许多点现在是“可能”，节省的时间更少。如果您进行了更严重的下采样，您可能会考虑使用两位掩码：这将允许您说“整个块都填充了矩形”（即 - 不需要进一步处理：x上述）或“需要进一步处理”（例如在o上文）。这很快开始比 Q 树方法更复杂......
底线：预先对矩形进行的排序/组织越多，查找的速度就越快。