查找 n 个矩形中是否存在任何重叠的矩形

Question

假设每个矩形都是直线定向的（边平行于 x 和 y 轴），以便我们用其最小和最大 x 和 y 坐标表示矩形。给出一个O.n lg n/-time算法来决定一个集合是否如此表示的 n 个矩形包含两个重叠的矩形。你的算法不需要报告所有相交对，但它必须报告重叠存在，如果一个矩形完全覆盖另一个矩形，即使边界线不相交。

我的解决方案：设 R 是一个包含矩形的数组，表示为 (x_int, y_int)，其中 x_int 表示区间 [x1, x2]，y_int 表示区间 [y1, y2]，如果rectacle 的 4 个角分别是 (x1, y1), (x1, y2), (x2, y1) 和 (x2, y2)。让索引从 1 开始。此解决方案基于以下事实：当且仅当两个矩形重叠如果它们 x_int 重叠并且 y_int 重叠。

FindOverlap(R, n):
  T = IntervalTree()   // T is a interval tree capable of checking if a given
                       // interval is overlapping with any interval in the tree
                       // and inserting interval in the tree in log(n) time.
  for i in [1,n]:
      x_int, y_int = R[i][1], R[i][2]

      interval_Index = T.IntervalSearch(x_int)  // Returns 0 if there is no interval 
                                           // in T which overlaps x_int , else 
                                           // returns index of the interval which
                                           // overlaps x_int 
      if interval_Index != 0:

          if R[interval_Index][2] overlaps y_int:

              return i, interval_Index

      T.InsertInterval(x_int, i)          // inserts interval x_int into T with 
                                          //associated index i
  return False

这有什么问题吗？这个算法能正常工作吗？

Answer 1

基于@Matt Timmermans 的评论：这不起作用，因为您可能会遇到这样的情况，即三个矩形在 X 中重叠，而只有最后两个矩形在 Y 中重叠。在这种情况下，您只检查 Y 中的重叠第三个和第一个，不在第三个和第二个之间

此外，如果您尝试检查在 X 中与当前矩形重叠的所有矩形是否在 Y 中重叠，在最坏的情况下，您最终的复杂度为 O(N^2)：假设所有 N 个矩形在 X 中重叠，但只有Y 中的最后两个重叠。

你需要的是一棵二维区间树，即X中的区间树，其中每个节点还包含Y中的区间树作为子树。插入和查询仍然是O(log N)，这使得整个算法O(N log N).

Answer 2

这里给出一个符合要求的扫描线算法：

您需要一个二叉搜索树 (BST) 来保持矩形按最小 X 坐标排序，以及一个优先级队列来保持矩形按最大 Y 坐标排序。

按最小 Y 坐标对矩形进行排序：O(N log N)
以最小 Y 顺序遍历矩形。为每一个：
1. 从优先级队列和 BST 中移除所有最大 Y 坐标小于新矩形最小 Y 的矩形：一起 O(N log N)
2. 将新矩形插入到 BST 中。如果你检测到它的 X 区间与 BST 中它左边或右边的矩形重叠，那么你就找到了重叠，你就完成了。此步骤也需要 O(N log N)。
3. 将新矩形插入到优先级中，以便您知道何时在步骤 2.1 中删除它。再次 O(N log N)

查找 n 个矩形中是否存在任何重叠的矩形

to find if any overlapping rectangles exist in n number of rectangles

algorithm

data-structures

intervals

pseudocode