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

Question

假设每个矩形都是直线形的（与x和y轴），因此我们用其最小和最大x和y坐标表示一个矩形。给出一个lg n /时间算法来确定一个集合是否这样表示的n个矩形中的n个包含两个重叠的矩形。您的算法不需要报告所有相交的对，但是如果一个矩形完全覆盖了另一个矩形，即使边界线不相交。

我的解决方案：令R为一个包含以（x_int，y_int）表示的矩形的数组，其中如果矩形的四个角为（x1，y1），（x1，y2），则x_int表示区间[x1，x2]且y_int表示区间[y1，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）。