合并天际线，分裂征服 [英] Merge skylines, divide and conquer

问题描述

我正在努力解决着名的天际线问题（见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,28），（22,3），（23,13），（29，0）

通过对算法进行分割和征服来实现O（n lg n）的运行时间，但是我被困在合并部分上。

我是否首先检查天际线是否有重叠，方法是检查left.x2< right.x1？但是我想我应该先检查一下在X轴上的优先重叠，一切变成一个大的鸡蛋混乱。

也许我觉得太复杂了？我需要的是一组最高的y坐标，在每个十字路口，我应该像这样接近吗？

解决方案

我认为这应该是一个更容易围绕的方法：

• 将x坐标拆分为每个矩形的起始和完成对象，如下所示：

   code> rect（x1，y，x2） - > （x1，y，start，引用rect），
  （x2，y，finish，引用rect）
    

  所以这样的东西：

    class MyStruct 
   {
   Rectangle直肠
   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.finish X，0）代替）
    
    
  
  






所以 O（n log n）。




I'm trying to solve the famous skyline problem (see gif):

Input

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

Should return, the points that are behind other buildings should be gone and the coordinates of changes in the Y-axis should be in the returning skyline:

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

I'm trying to do so by using a divide and conquer approach to the algorithm as to achieve a running time of O(n lg n), but I'm stuck on the merge part.

Everytime I think about it I get confused. For example, I check which one the skylines is first e.g. which has the lower x-coordinate, then I add that + its hight to my new skyline. But then I encounter a skyline thats behind two other skylines, how can I detect this 'collision'?

Do I first check if the skylines have any overlap by checking if left.x2 < right.x1? But then I think what should I check first? Overlap of precedence on the x-axis and everything turns into a big chicken-egg mess.

Maybe I'm thinking too complicated? What I need is the set of highest y coordinates, at every intersection, should I approach it like this?

解决方案

I think this should be an approach that's easier to wrap one's head around:

• Split x-coordinates into start and finish objects for each rectangle, as follows:

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

  So something like:

  class MyStruct
  {
     Rectangle rect;
     int x, y;
     bool isStart;
  }
  

• Sort these objects by x-coordinate (O(n log n))
• Create an (intially empty) set of rectangles (which will be sorted by y-coordinate, e.g. a BST)
• Loop through these objects (in the now-sorted order) (O(n))
  • Whenever a start is encountered
    • Add the rectangle to the set of rectangles (O(log n))
    • If it's the new highest rectangle, add that start point to the output (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)

So O(n log n).

这篇关于合并天际线，分裂征服的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！