logo标签列表

寻找覆盖查询点的最小面积矩形。

algorithmgeometryquadtreespatial-queryr-tree
4

我正在进行一个涉及计算几何的个人项目。标题中的问题是我正在尝试解决的一个小子问题的抽象，但我很难高效地解决它。希望这个问题足够通用，可能不仅对我有用！

问题

假设我们有一个平面上的矩形集合S，所有矩形的边都平行于坐标轴（没有旋转）。对于我的问题，我们将假设矩形交叉非常普遍。但是它们也非常好：如果两个矩形相交，我们可以假设其中一个始终完全包含另一个。因此不存在“部分”重叠。

我想以一种方式存储这些矩形，使得：

  • 我们可以高效地添加新的矩形。
  • 给定查询点(x,y)，我们可以有效地报告包含该点的最小面积矩形。

插图提供了后者的动机。我们总是想找到包含查询点的最深嵌套矩形，因此总是最小面积的那个。

.

我的想法

我知道R树和四叉树经常用于空间索引问题，并且在某些情况下都可以很好地工作。 R树的问题是在最坏情况下性能会退化为线性性能。

我考虑基于嵌套性建立一组平衡二叉树。节点r的左子树包含所有在矩形r内部的矩形。右子树包含所有包含r的矩形。所示示例将有三棵树。

但是如果没有矩形嵌套怎么办？那么你需要O(n)个只有1个元素的树，而且我们又回到了像线性扫描盒子一样表现不佳的状态。

我该如何在最坏情况下渐进次线性地解决这个问题？即使这意味着在最好的情况下牺牲一些性能或存储要求。（我假设对于这样的问题，可能需要维护两个数据结构，这很酷）
我确信允许矩形相交的非常特定的方式应该有助于解决这个问题。事实上，对我来说，它看起来像是对数性能的候选人，但我却没有任何进展。
感谢您提前提供的任何想法！
4个回答
4
我建议按嵌套级别存储矩形，并逐级处理矩形查找。一旦找到点所在的顶层矩形，就可以查看该矩形内部的二级矩形，使用相同的方法找到包含点的矩形，然后查看第三级等。为避免最坏情况下O(n)的矩形查找，可以使用三叉空间树，反复在空间中绘制垂直线并将矩形分成三组：左侧的（蓝色），与之相交的（红色）和右侧的（绿色）。对于相交矩形的组（或者当垂直线会相交大多数或所有矩形时），切换到水平线并将矩形分成上方、相交和下方的组。

ternary spatial tree

你需要反复检查点是否在线的左侧/右侧或上方/下方，并继续检查同侧和被线相交的矩形。在这个例子中，只需要检查四个矩形即可找到包含该点的矩形。
如果我们对例子中的矩形使用以下编号：

rectangle numbering

那么三元空间树大概是这样的：

ternary spatial tree

如果所有矩形覆盖整个区域，那么如何避免O(n)的最坏情况？我没有看到你的方法有最坏情况的保证。你的例子假设它们不重叠，但是R树已经可以很好地处理这种情况了。 - Has QUIT--Anony-Mousse
@Anony-Mousse 我并不是假设矩形没有嵌套，我只是建议按层级存储和搜索它们。但你说得对，我的三叉树建议只能改善每个层级的搜索，如果查询点在每个矩形中，它们都必须被考虑，因此仍然是O(n)。 - m69 ''snarky and unwelcoming''
1
您可以沿着矩形的边界将区域从 xMin 到 xMax 和 yMin 到 yMax 进行分区。这最多可得到 (2n - 1)^2 个字段。每个字段要么完全为空，要么被可见（部分）单个矩形占据。现在，您可以轻松地创建一个带有指向顶部矩形的链接的树结构（例如，在x和y方向上计算划分的数量，在中间进行更多的划分并创建一个节点...进行递归）。因此查找将需要 O(log n^2)，即次线性。数据结构需要 O(n^2) 的空间。

以下是更好的复杂度实现，因为索引的搜索可以分开，而搜索顶部矩形只需要 O(log n)，不管矩形的配置如何，且相当简单易实现：。

private int[] x, y;
private Rectangle[][] r;

public RectangleFinder(Rectangle[] rectangles) {
    Set<Integer> xPartition = new HashSet<>(), yPartition = new HashSet<>();
    for (int i = 0; i < rectangles.length; i++) {
        xPartition.add(rectangles[i].getX());
        yPartition.add(rectangles[i].getY());
        xPartition.add(rectangles[i].getX() + rectangles[i].getWidth());
        yPartition.add(rectangles[i].getY() + rectangles[i].getHeight());
    }
    x = new int[xPartition.size()];
    y = new int[yPartition.size()];
    r = new Rectangle[x.length][y.length];
    int c = 0;
    for (Iterator<Integer> itr = xPartition.iterator(); itr.hasNext();)
        x[c++] = itr.next();
    c = 0;
    for (Iterator<Integer> itr = yPartition.iterator(); itr.hasNext();)
        y[c++] = itr.next();
    Arrays.sort(x);
    Arrays.sort(y);
    for (int i = 0; i < x.length; i++)
        for (int j = 0; j < y.length; j++)
            r[i][j] = rectangleOnTop(x[i], y[j]);
}

public Rectangle find(int x, int y) {
    return r[getIndex(x, this.x, 0, this.x.length)][getIndex(y, this.y, 0, this.y.length)];
}

private int getIndex(int n, int[] arr, int start, int len) {
    if (len <= 1)
        return start;
    int mid = start + len / 2;
    if (n < arr[mid])
        return getIndex(n, arr, start, len / 2);
    else
        return getIndex(n, arr, mid, len - len / 2);
}
1
几乎任何索引都可能降至最坏情况O(n)。
问题在于你是否会有这样有害的数据，以及你是优化最坏情况还是真实数据。
考虑n个相同大小、重叠的矩形和交点中的一个点……你在这里没有太多优化的机会。
R树是一个相当不错的选择。你可以进行优先搜索，并优先选择较小的矩形。
但是你的草图表明，你的矩形通常是嵌套而不是重叠的。标准R树处理这种情况并不好。相反，你可能需要修改R树来使用这种结构，并将嵌套的矩形作为父节点的一部分存储。
问题中指出，没有部分重叠的矩形。然而，这些矩形可能全部都在彼此内部，并且查询点也在它们所有矩形的内部，因此你的观点仍然成立。 - m69 ''snarky and unwelcoming''
如果所有的矩形都在彼此内部，那么O(log n)就很容易实现。检查点是否在中间深度的矩形内，如果是，则该点只能在这个或更高的矩形内；如果不是，则必须在更深的矩形内重复递归。 - maraca
1

如何考虑使用PH-Tree？PH-Tree本质上是一个四叉树形状的位级尝试，但具有一些独特的属性，可能非常适合您的情况，例如非常高效的更新和小矩形的局部性。

基础知识：

  • PH-Tree是一个位级尝试，这意味着它在每个位位置上在所有维度上分割。这意味着，对于64位浮点数据，树的最大深度为64。
  • 树是隐式z排序的
  • 查询速度通常与R * Tree或STR-Tree相当，在您的情况下可能会更快，请参见下文。
  • 插入/删除速度等于或优于STR-Trees，并且优于我所知道的任何其他R-Tree类型。
  • 树形状仅由数据确定，而不是由插入顺序确定。这意味着永远不会有任何昂贵的重新平衡。实际上，该树保证任何插入或删除都不会影响超过两个节点（具有子/父关系）。
存储矩形：PH-Tree只能存储数据向量，即点。为了存储（轴对齐的）矩形，默认情况下它采用“左下”和“右上”角并将它们放入单个向量中。例如，2D矩形（2,2）-（4,5）被存储为4维向量（2,2,4,5）。这种表示方式可能不明显，但仍然允许进行高效的查询，例如窗口查询和最近邻查询，请参见一些结果here和一些更多解释here。
树不能直接存储相同的矩形两次。相反，您需要为每个“键”关联一个计数器。对于具有“n”个相同矩形的特殊情况，这实际上具有优势，因为生成的树将只包含一个键，因此可以几乎在常数时间内确定与最小矩形的重叠。
查询性能: 从性能结果可以看出，PH-Tree（根据数据集）在返回少量结果的小查询窗口中最快（这里，图16）。我不确定性能优势是否与小查询窗口大小或小结果大小有关。但如果与前者有关，则您的查询应该非常快，因为本质上您的查询窗口是一个点。
优化小矩形尺寸: 由于将矩形编码为单个向量，最小矩形很可能（保证？）位于也包含您搜索点的叶节点中。 通常，查询按Z顺序遍历，因此要利用小矩形的局部性，您需要编写特殊查询。我认为这不难，我可以简单地使用PH-Tree k最近邻实现并提供自定义距离函数。当前的kNN从定位具有搜索点的节点开始，然后扩展搜索区域直到找到所有最近的邻居。我确信使用自定义距离函数应该足够，但您可能需要进行一些研究来证明它。

PH-Tree的完整Java代码可在上面的链接中找到。为了比较，您可能想要查看我其他索引实现这里（R*Tree，四叉树，STR-Tree）。

是的，那就是我。我注意到一段时间以前，在树中矩形的位置部分取决于它们的大小。例如，靠近空间对角线（0,0,0...）/（MAX，MAX，MAX，...）的节点都很小。反之只有部分是真的，距离对角线最远的矩形可以是小的或大的，这取决于象限。我从来没有时间进一步研究这个问题，更不用说找到一个用例了。如果您感兴趣，我可以提供更多关于这种行为的细节。 - TilmannZ
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接