5

我正在尝试解决著名的天际线问题（见 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 坐标，在每个路口，我应该这样接近它吗？

4

2 回答 2

8

我认为这应该是一种更容易理解的方法：

  • 将 x 坐标拆分为每个矩形的开始和结束对象，如下所示：

    rect(x1, y, x2) -> (x1, y, "start", reference to rect),
                   (x2, y, "finish", reference to rect)

    所以像：

    class MyStruct
{
   Rectangle rect;
   int x, y;
   bool isStart;
}
  • 按 x 坐标 ( O(n log n))对这些对象进行排序
  • 创建一组（最初为空）矩形（将按 y 坐标排序，例如BST）
  • 循环遍历这些对象（按现在排序的顺序）（O(n)）
    • 每当遇到一个开始
      • 将矩形添加到矩形集 ( O(log n))
      • 如果它是新的最高矩形，则将该起点添加到输出 ( O(1))
    • 每当遇到完成
      • 从矩形集中移除矩形 ( O(log n))
      • 如果它是最高的矩形，则在集合中找到下一个最高的矩形并将该点添加(current.finishX, new.y)到输出 ( O(1)) （如果集合为空，则添加(current.finishX, 0)到输出）

所以O(n log n)。

于 2013-02-20T11:06:28.033 回答
0

这可以通过修改归并排序算法来实现。天际线的算法如下所示：

构建天际线

    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(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);
     }
  }
于 2015-02-09T15:15:35.537 回答