algorithm - 确定一个点是否在矩形的并集内

Question

我有一组轴平行的二维矩形，由它们的左上角和右下角定义(全部在整数坐标中)。给定一个点查询，您如何有效地确定它是否在其中一个矩形中？我只需要一个是/否的答案，而不需要担心它在哪个矩形中。

我可以通过查看 x 是否在 x1 和 x2 之间以及 y 是否在 y1 和 y2 之间来检查 (x,y) 是否在 ((x1, y1), (x2, y2)) 中。我可以为每个以矩形数量线性时间运行的矩形分别执行此操作。但由于我有很多矩形，而且我会做很多点查询，所以我希望速度更快。

Answer 1

答案在一定程度上取决于您有多少个矩形。蛮力法依次检查每个矩形对的坐标:

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) - 对于大型矩形集合和许多查找，性能改进将是显着的。您可以在 this earlier answer 中看到它的一个版本(它查看一个矩形与一组矩形的交集 - 但您很容易适应“点内”) .更一般的，看题目quad trees这正是解决此类二维问题所需的数据结构。

效率稍低(但速度更快)的方法是按左下角对矩形进行排序(例如)- 然后您只需要搜索矩形的一个子集。

如果坐标是整数类型，您可以制作一个二进制掩码 - 然后查找是一个单一的操作(在您的情况下，这将需要一个 512MB 的查找表)。如果您的空间相对稀疏(即“未命中”的概率相当大)，那么您可以考虑使用欠采样位图(例如使用坐标/8)——然后 map 大小下降到 8M，如果您有“不hit”你可以省去仔细观察的费用。当然，您必须向下舍入左/下坐标，并向上舍入上/右坐标才能使这项工作正确。

用一个例子稍微扩展一下:

想象坐标在 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.....
................

你可以把它变成一个由 0 和 1 组成的数组——所以“此时是否有一个矩形”与“这个位是否已设置”是一样的。一次查找会给你答案。为了节省空间，你可以对数组进行下采样——如果仍然没有命中，你就有了答案，但如果有命中，你需要检查“这是真的吗”——这样可以节省更少的时间，而且节省的时间取决于你的矩阵(稀疏=更快)。子采样数组看起来像这样(2 倍下采样):

.oxx....
.xxooo..
.oooxo..
...ooo..

我用x来标记“如果你碰到这个点，你肯定在一个矩形中”，用o来表示“其中一些是矩形”。很多点现在都是“可能”，节省的时间也少了。如果你做了更严格的下采样，你可能会考虑使用两位掩码:这将允许你说“整个 block 都充满了矩形”(即 - 不需要进一步处理:上面的 x)或“需要进一步处理”(如上面的 o)。这很快就开始比 Q 树方法更复杂......

底线:您预先对矩形进行的排序/组织越多，查找的速度就越快。