4

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

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

4

3 回答 3

6

答案取决于你有多少个矩形。蛮力方法依次检查每个矩形对的坐标：

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) - 对于大型矩形集合和许多查找，性能改进将是显着的。您可以在这个较早的答案中看到一个版本（它查看一个矩形与一组矩形的交集 - 但您很容易适应“点内”）。更一般地，看一下四叉树的主题，这正是像这样的 2D 问题所需要的那种数据结构。

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

如果坐标是整数类型，您可以制作一个二进制掩码 - 然后查找是一个单一的操作（在您的情况下，这将需要一个 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.....
................

你可以把它变成一个由 0 和 1 组成的数组——这样“此时是否有一个矩形”与“是否设置了这个位”相同。一次查找将为您提供答案。为了节省空间，你可以对数组进行下采样——如果仍然没有命中，你就有答案，但如果有命中，你需要检查“这是真的吗”——这样可以节省更少的时间，节省取决于稀疏性你的矩阵（稀疏=更快）。二次采样数组看起来像这样（2x 下采样）：

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

我用x标记“如果你达到这一点，你肯定在一个矩形中”，并o说“其中一些是一个矩形”。许多点现在都是“可能”，节省的时间更少。如果您进行了更严格的下采样，您可能会考虑使用两位掩码：这将允许您说“整个块都充满了矩形”（即 - 不需要进一步处理：x上述）或“需要进一步处理”（比如o以上）。这很快就开始比 Q-tree 方法更复杂......

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

于 2013-11-12T14:58:57.100 回答
0

将矩形的坐标部分存储到树结构中。对于任何左值，创建一个指向相应右值的条目，该右值指向相应的顶部值，指向相应的底部值。

要进行搜索，您必须对照左值检查点的 x 值。如果所有左值都不匹配，这意味着它们大于您的 x 值，则您知道该点位于任何矩形之外。否则，您检查 x 值与相应左值的右值。同样，如果所有正确的值都不匹配，那么您就在外面。否则与顶部和底部值相同。一旦找到匹配的底部值，您就知道您在任何矩形内并且您已完成检查。

正如我在下面的评论中所说，有很大的优化空间，例如最小的左侧和顶部值以及最大的右侧和底部值，以快速检查您是否在外面。

以下方法在 C# 中，需要适应您的首选语言：

public class RectangleUnion
{
    private readonly Dictionary<int, Dictionary<int, Dictionary<int, HashSet<int>>>> coordinates =
        new Dictionary<int, Dictionary<int, Dictionary<int, HashSet<int>>>>();

    public void Add(Rectangle rect)
    {
        Dictionary<int, Dictionary<int, HashSet<int>>> verticalMap;

        if (coordinates.TryGetValue(rect.Left, out verticalMap))
            AddVertical(rect, verticalMap);
        else
            coordinates.Add(rect.Left, CreateVerticalMap(rect));
    }

    public bool IsInUnion(Point point)
    {
        foreach (var left in coordinates)
        {
            if (point.X < left.Key) continue;

            foreach (var right in left.Value)
            {
                if (right.Key < point.X) continue;

                foreach (var top in right.Value)
                {
                    if (point.Y < top.Key) continue;

                    foreach (var bottom in top.Value)
                    {
                        if (point.Y > bottom) continue;

                        return true;
                    }
                }
            }
        }

        return false;
    }

    private static void AddVertical(Rectangle rect,
        IDictionary<int, Dictionary<int, HashSet<int>>> verticalMap)
    {
        Dictionary<int, HashSet<int>> bottomMap;
        if (verticalMap.TryGetValue(rect.Right, out bottomMap))
            AddBottom(rect, bottomMap);
        else
            verticalMap.Add(rect.Right, CreateBottomMap(rect));
    }

    private static void AddBottom(
        Rectangle rect,
        IDictionary<int, HashSet<int>> bottomMap)
    {
        HashSet<int> bottomList;
        if (bottomMap.TryGetValue(rect.Top, out bottomList))
            bottomList.Add(rect.Bottom);
        else
            bottomMap.Add(rect.Top, new HashSet<int> { rect.Bottom });
    }

    private static Dictionary<int, Dictionary<int, HashSet<int>>> CreateVerticalMap(
        Rectangle rect)
    {
        var bottomMap = CreateBottomMap(rect);
        return new Dictionary<int, Dictionary<int, HashSet<int>>>
                   {
                       { rect.Right, bottomMap }
                   };
    }

    private static Dictionary<int, HashSet<int>> CreateBottomMap(Rectangle rect)
    {
        var bottomList = new HashSet<int> { rect.Bottom };
        return new Dictionary<int, HashSet<int>>
                   {
                       { rect.Top, bottomList }
                   };
    }
}

它并不漂亮，但应该为您指明正确的方向。

于 2013-11-12T16:26:36.067 回答
0

对于各种 2D 几何查询，我最喜欢的是Sweep Line Algorithm。它在 CAD 软件中被广泛使用，这将是我对您程序目的的疯狂猜测。

基本上，您沿 X 轴对所有点和所有多边形顶点（在您的情况下为所有 4 个矩形角）进行排序，并沿 X 轴从一个点前进到下一个点。在非曼哈顿几何的情况下，您还将引入中间点，即线段交叉点。

数据结构是点和多边形（矩形）边与当前 X 位置的垂直线相交的平衡树，在 Y 方向上排序。如果结构维护得当，很容易判断当前 X 位置的点是否包含在矩形中：只需检查与点边缘交叉点垂直相邻的 Y 方向。如果允许矩形重叠或有矩形孔，它只是有点复杂，但仍然非常快。

N 个点和 M 个矩形的总体复杂度为 O((N+M)*log(N+M))。人们实际上可以证明这是渐近最优的。

于 2013-11-12T17:29:00.560 回答