合并天际线，分而治之

Question

我正在努力解决著名的天际线问题(参见gif)：

​

输入

(1,11,5)，(2,6,7)，(3,13,9)，(12,7,16)，(14,3,25)，(19，18 22)，(23,13,29)，(24,4,28)

如果返回，其他建筑物后面的点应该消失，Y轴变化的坐标应该在返回的天际线上：

(1，11)，(3，13)，(9，0)，(12，7)，(16，3)，(19，18)，(22，3)，(23，13)，(29，0)

我试图通过使用分而治之的方法来实现算法的运行时间为O(n lg n)，但我仍然停留在合并部分。

每次我想到它，我都会感到困惑。例如，我首先检查哪些是天际线，例如，哪个的x坐标较低，然后我将它的高度加到我的新的天际线上。但是当我遇到另外两条天际线后面的天际线时，我怎么才能发现这种“碰撞”呢？

我是否首先通过检查left.x2 < right.x1来检查天际线是否有重叠？但我想我应该先查些什么？在x轴上优先级的重叠，一切都变成了一团鸡蛋蛋。

也许我想的太复杂了？我需要的是最高的y坐标集合，在每个十字路口，我应该这样处理它吗？

Answer 1

我认为这应该是一种更容易让人头脑清醒的方法：

• 将x坐标拆分为每个矩形的开始和完成对象，如下所示： (x1，y，x2) -> (x1，y，"start"，引用rect)，(x2，y，"finish"，引用rect) 所以，就像： 类MyStruct {矩形矩形；int x，y；bool isStart；}
• 通过x坐标(O(n log n))对这些对象进行排序。
• 创建一组(内部为空的)矩形(按y坐标排序，例如BST)。
• 循环遍历这些对象(按现在排序的顺序) (O(n))
  • 每当遇到启动时，
    • 将矩形添加到矩形集(O(log n))
    • 如果是新的最高矩形，将该起始点添加到输出(O(1))中。

​

- Whenever a finish is encountered 
    - Remove the rectangle from the set of rectangles (`O(log n)`)
    - If it's the highest rectangle, find the next highest rectangle in the set and add the point `(current.finishX, new.y)` to the output (`O(1)`) (if the set is empty, add `(current.finishX, 0)` to the output instead)

​

​

所以O(n log n)。

Answer 2

这可以通过修改合并排序的算法来实现。天际线的算法看起来如下：

ConstructSkyLine

    ConstructSkyLine(List B ) --------------- O(nlogn)
    {
        If(B.size() == 1)
        {
            List skyLineList = new List();
            SKYLINE = new SKYLINE(B.XL, B.XR, B.H);
            skyLineList.add(SKYLINE);
            Return skyLineList;
        }
        B1, B2 <-- Split(B);
        List S1 <-- ConstructSkyLine(B1);
        List S2 <-- ConstructSkyLine(B2);
        List S <-- MergeSkyline(S1, S2);
        Return S;
    }

MergeSkyline

    MergeSkyline(List S1, List S2) --------------- O(n)
    {
        List< SKYLINEENTRY> skylineEntryList = new ArrayList<SKYLINEENTRY>();
        while (S1.isEmpty() && S2.isEmpty())--------------- O(n)
        {
           S1Item <-- S1.get(0);
           S2Item <-- S2.get(0);
           If (S1Item.XL < S2Item.XL)
           {
             Merge(S1, S2, skylineEntryList);   --------------- O(n)
           }
           Else
           {
             Merge(S2, S1, skylineEntryList); --------------- O(n)
           }
         }

         If(!S1.isEmpty())
         {
            skylineEntryList.add(S1);
         }

         If(!S2.isEmpty())
         {
           skylineEntryList.add(S2);
         }
         Retrun skylineEntryList;
      }

合并

  Merge(S1, S2, skylineEntryList) --------------- O(n)
  {
    SKYLINEENTRY <-- null;
    S1Item <-- S1.get(0);
    S2Item <-- S2.get(0);
    SKYLINEENTRY.XL = S1Item.XL;
    If(S1Item.XR > S2Item.XL) // means over lap 
    {
        If(S1Item.H > S2Item.H) // S1 is higher.
        {
           SKYLINEENTRY.XR = S1Item.XR;
           SKYLINEENTRY.H = S1Item.H;
           S1.remove(S1Item); --------------- O(n)
           skylineEntryList.add(SKYLINEENTRY);
           if(S2Item.XR < S1Item.XR) // full overlap
           {
              S2.remove(S2Item); --------------- O(n)
           }
           Else // partial overlap
           {
              S2Item.XL <-- S1Item.XR;
           }            
        }
        Else //S2 is higher
        {
           SKYLINEENTRY.XR = S2Item.XL;
           SKYLINEENTRY.H = S1Item.H;
           if(S2Item.XR < S1Item.XR) // full overlap with S2
           {
              S1Item.XL = S2Item.XR;
           }
           Else // partial overlap
           {
              S1.remove(S1Item); --------------- O(n)
           }    
           skylineEntryList.add(SKYLINEENTRY);  
        }   
     }
     Else // no overlap
     {
        SKYLINEENTRY.XR = S1Item.XR;
        SKYLINEENTRY.H = S1Item.H;
        S1.remove(S1Item); --------------- O(n)
        skylineEntryList.add(SKYLINEENTRY);
     }
  }