algorithm - 找到覆盖查询点的最小面积矩形

我正在从事一个与计算几何相关的个人项目。标题中的问题是我正在尝试但正在努力有效解决的一个小子问题的抽象。希望它足够通用，可能不仅仅对我有用!

问题

假设我们在平面上有一组 S 个矩形，所有矩形的边都平行于坐标轴(无旋转)。对于我的问题，我们假设矩形交叉点非常普遍。但它们也非常好:如果两个矩形相交，我们可以假设其中一个总是完全包含另一个。所以没有“部分”重叠。

我想以一种方式存储这些矩形:

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

所以我知道 R-Trees 和 Quad-Trees 都经常用于空间索引问题，而且确实在某些情况下两者都可以很好地工作。 R-Trees 的问题在于它们在最坏的情况下会退化为线性性能。

我想到了构建一组基于嵌套的平衡二叉树。节点 r 的左子树包含矩形 r 内的所有矩形。右子树包含 r 所在的所有矩形。所示示例将具有三棵树。

但是如果没有嵌套的矩形呢？然后你需要 1 个元素的 O(n) 树，我们又一次得到了一些表现与通过框的线性扫描一样差的东西。

在最坏的情况下，我如何以渐近次线性时间的方式解决这个问题？即使这意味着在最佳情况或存储要求下牺牲一些性能。 (我假设对于这样的问题，可能需要维护两个数据结构，这很酷)

我确信允许矩形相交的非常具体的方式应该有助于解决这个问题。事实上，对我来说它看起来像是对数性能的候选者，但我只是没有取得任何进展。

提前感谢您的任何想法!

最佳答案

我建议按嵌套级别存储矩形，并处理按级别查找矩形的问题。一旦找到该点在哪个顶层矩形，就可以查看该矩形内的二级矩形，用同样的方法找到该点所在的矩形，然后查看三级，等等。

为了避免 O(n) 的最坏情况来找到矩形，您可以使用一种三元空间树，在其中重复绘制一条垂直线穿过空间并将矩形分成三组:左边(蓝色)，与(红色)相交的那些，以及右边(绿色)的那些。对于一组相交的矩形(或者一旦一条垂直线与大部分或所有矩形相交)，您切换到一条水平线并将矩形分成在线上方、相交和下方的组。

然后您将反复检查该点是在线的左侧/右侧还是上方/下方，然后继续检查同一侧的矩形以及与该线相交的矩形。

在这个例子中，实际上只需要检查四个矩形来找出哪个矩形包含该点。

如果我们在示例中对矩形使用以下编号:

那么三元空间树就是这样的:

关于algorithm - 找到覆盖查询点的最小面积矩形，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43127159/