Merge skylines, divide and conquer

问题:

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?

回答1:

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).

回答2:

This can be achieved by modifying the algorithm for merge sort. The algorithm for skyline looks like:

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

  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);
     }
  }