algorytm skyline

Question

Jak znaleźć wierzchołki przerywanej linii otaczającej sylwetkę na tym obrazku?

Możliwe wejście na powyższym przykładzie jest:

 
WIDTH HEIGHT POSITION 
    3  9  17 
    5  9  9 
12  4  8 
    3  11  3 
10  7  1 
    2  3  19 

Więc na tym przykładzie rozwiązaniem byłoby

 
[(1, 0), (1, 7), (3, 7), (3, 11), (6, 11), (6, 7), 
(9, 7), (9, 9), (14, 9), (14, 4), (17, 4), (17, 9), 
(20, 9), (20, 3), (21, 3), (21, 0)] 

Answer 1

http://online-judge.uva.es/p/v1/105.html gdzie ja pierwotnie widział problemu nie

I Algorithmist ma wyjaśnienie rozwiązanie: http://www.algorithmist.com/index.php/UVa_105

Answer 2

W naiwnej razie, to nie wydaje się to bardzo trudne algorytm. Czy wiesz, czy rozmiar wejściowy będzie większy/jak duży?

Moja pierwsza próba: Spróbuj przejść od lewej do prawej. Najpierw wybierz blok z najbardziej wysuniętą na lewo krawędzią, która istnieje w linii początkowej. Wspinaj się na jego szczyt. Znajdź wszystkie bloki z lewą krawędzią między bieżącym punktem i górnym prawym punktem bieżącego bloku. Z tego zestawu, wybierz najbliższy (ale sprawdź w przypadku krawędzi, kalambur nie jest przeznaczony). Jeśli zestaw jest pusty, zacznij pracę w dół po prawej stronie bloku, szukając innych bloków, które możesz przechwycić.

Zasadniczo jest to sposób, w jaki można go prześledzić wzrokiem.

Możesz przeprowadzić prostą optymalizację, sortując listy, a następnie przeszukując listy, zamiast znajdować zestawy i kopać. Na przykład możesz przechowywać 4 posortowane listy bloków, z których każde jest sortowane według współrzędnych x lub y jednej ze stron.

Jeśli masz wiele bloków, możesz rozważyć użycie wielowymiarowej struktury danych w celu dalszego uporządkowania informacji.

Answer 3

to dość proste. Stwórz tablicę, która jest długością osi X, zainicjuj na 0. Kiedy czytasz na wejściach, wpisz wysokości do tej tablicy, jeśli wysokość jest> = aktualna wartość w tej lokalizacji w tablicy.

Następnie wystarczy pętli na tablicy i za każdym razem, gdy wartość zmienia się, jest to wierzchołek.

Zasadniczo:

int heights[SIZE] = {0}; 
int i, width, pos, height, prev = -1; 
while (scanf("%d %d %d", &width, &height, &pos) == 3) { 
    for (i = 0; i < width; ++i) { 
     if (heights[pos+i] < height) 
      heights[pos+i] = height; 
    } 
} 

for (i = 0; i < SIZE; ++i) { 
    if (heights[i] != prev) { 
     printf("(%d,%d) ", i+1, heights[i]); 
     prev = heights[i]; 
    } 
} 
printf("\n"); 

Answer 4

Zrobiłem klasy Java, aby spróbować rozwiązać ten. Klasa obejmuje metody generowania, rozwiązywania i drukowania zbiorów danych. Nie testowałem zbyt wiele, może pozostało kilka błędów. Ponadto, moje rozwiązanie może być niepotrzebnie skomplikowane, ale jest zaprojektowane do pracy (w teorii) dla niedyskretnych wysokości i wartości współrzędnych.

import java.util.Random; 

public class Skyline { 

    private int[][] buildings; 
    private int[][] skyline; 

    private int maxLength; 
    private int maxHeight; 

    public Skyline(int buildings, int maxLength, int maxHeight) { 
     this.maxLength = maxLength; 
     this.maxHeight = maxHeight; 
     makeRandom(buildings); 
    } 

    public Skyline(int[][] buildings, int dimensions) { 
     this.maxLength = maxLength; 
     this.maxHeight = maxHeight; 
     this.buildings = buildings; 
    } 

    public void makeRandom(int buildings) { 
     this.buildings = new int[buildings][3]; 

     Random rand = new Random(); 

     for(int i = 0; i < buildings; i++) { 
      int start = rand.nextInt(maxLength-3); 
      int end = rand.nextInt(maxLength - start - 1) + start + 1; 
      int height = rand.nextInt(maxHeight-1) + 1; 

      this.buildings[i][0] = start; 
      this.buildings[i][1] = height; 
      this.buildings[i][2] = end; 
     } 

     boolean swapped = true; 
     while(swapped) { 
      swapped = false; 
      for(int i = 0; i < this.buildings.length-1; i++) { 
       if(this.buildings[i][0] > this.buildings[i+1][0]) { 
        swapped = true; 
        int[] temp = this.buildings[i]; 
        this.buildings[i] = this.buildings[i+1]; 
        this.buildings[i+1] = temp; 
       } 
      } 
     } 

//  this.buildings[0][0] = 2; 
//  this.buildings[0][1] = 3; 
//  this.buildings[0][2] = 8; 
    } 

    public void printBuildings() { 
     print(this.buildings, false); 
    } 
    public void printSkyline() { 
     print(this.buildings, true); 
    } 

    public void print(int[][] buildings, boolean outline) { 
     char[][] str = new char[this.maxLength][this.maxHeight]; 
     for(int i = 0; i < this.maxLength; i++) { 
      for(int j = 0; j < this.maxHeight; j++) { 
       str[i][j] = '.'; 
      } 
     } 

     for(int i = 0; i < buildings.length; i++) { 
      int start = buildings[i][0]; 
      int height = buildings[i][1]; 
      int end = buildings[i][2]; 

      //print the starting vertical 
      for(int j = 0; j < height; j++) { 
       if(outline) str[start][j] = str[start][j] == '|' ? '.' : '|'; 
       else str[start][j] = '|'; 
      } 

      //print the ending vertical 
      for(int j = 0; j < height; j++) { 
       if(outline) str[end][j] = str[end][j] == '|' ? '.' : '|'; 
       else str[end][j] = '|'; 
      } 

      //print the horizontal 
      if(height > 0) { 
       for(int j = start; j <= end; j++) { 
        str[j][height] = str[j][height] == '|' ? '|' : '-'; 
       } 
      } 

     } 

     for(int i = maxHeight-1; i >= 0; i--) { 
      for(int j = 0; j < maxLength; j++) { 
       System.out.print(str[j][i]); 
      } 
      System.out.println(); 
     } 

     System.out.println(); 
    } 

    public void solveSkyline() { 

     for(int i = 0; i < buildings.length; i++) { 
      boolean reduced = true; 
      while(reduced) { 
       reduced = false; 
       for(int j = i+1; j < buildings.length; j++) { 
        if(buildings[j][0] < buildings[i][2] && buildings[j][1] > buildings[i][1] && buildings[j][2] >= buildings[i][2]) { //if intersecting building is taller, and longer 
         buildings[i][2] = buildings[j][0]; 
         reduced = true; 
         break; 
        } else if(buildings[j][0] < buildings[i][2] && buildings[j][1] <= buildings[i][1] && buildings[j][2] >= buildings[i][2]) { //intersecting building is shorter, but longer 
         buildings[j][0] = buildings[i][2]; 
         reduced = true; 
         break; 
        } else if(buildings[j][0] < buildings[i][2] && buildings[j][1] > 0 && buildings[j][1] < buildings[i][1] && buildings[j][2] <= buildings[i][2]) { //building is invisible, so ignore it 
         buildings[j][1] = 0; 
         reduced = true; 
         break; 
        } else if(buildings[j][0] < buildings[i][2] && buildings[j][2] <= buildings[i][2] && buildings[j][1] > buildings[i][1]) { 
         int[] newBuilding = new int[]{buildings[j][2], buildings[i][1], buildings[i][2]}; 
         int[][] newBuildings = new int[buildings.length+1][3]; 
         boolean inserted = false; 
         buildings[i][2] = buildings[j][0];  
         for(int k = 0; k < buildings.length; k++) { 
          if(inserted == false) { 
           if(newBuilding[0] < buildings[k][0]) { 
            newBuildings[k] = newBuilding; 
            newBuildings[k+1] = buildings[k]; 
            inserted = true; 
           } else { 
            newBuildings[k] = buildings[k]; 
           } 
          } 
          if(inserted == false && k == buildings.length - 1) { 
           newBuildings[k+1] = newBuilding; 
          } else { 
           newBuildings[k+1] = buildings[k]; 
          } 
         } 
         buildings = newBuildings; 
         reduced = true; 
         break; 
        } 
       } 
      } 
     } 
    } 

    public static void main(String args[]) { 
     Skyline s = new Skyline(5, 100, 10); 

     s.printBuildings(); 
     s.solveSkyline(); 
     s.printBuildings(); 

     s.printSkyline(); 
    } 
} 

Answer 5

Rozwiązałem ten problem za pomocą algorytmu liniowego. To jest rozwiązanie klasy Pythona.

tam dwa klucze: 1) za pomocą zmiennej "punkty", aby zapisać wszystkie punkty lewa i prawa oraz ich wysokość i znak wysokości, aby wskazać, czy punkty są w lewo, czy w prawo. 2) zmienna "aktywna" służy do zapisywania wszystkich aktywnych linii, które zostały zeskanowane.

klasy Rozwiązanie: # @param {całkowite [] []} budynków # @return {całkowitą [] []} def getSkyline (self, budynki) jeśli len (budynki) == 0: powrót [] jeśli len (budynki) == 1: powrót [[budynków [0] [0], budynki [0] [2]] [budynków [0] [1], 0]]

points=[] 
    for building in buildings: 
     points+=[[building[0],building[2]]] 
     points+=[[building[1],-building[2]]] # the negative sign means this point is a right point 
    points=sorted(points, key=lambda x: x[0]) 

    moving, active, res, current=0, [0], [],-1 

    while moving<len(points): 
     i=moving 
     while i<=len(points): 
      if i<len(points) and points[i][0]==points[moving][0]: 
       if points[i][1]>0: 
        active+=[points[i][1]] 
        if points[i][1]>current: 
         current=points[i][1] 
         if len(res)>0 and res[-1][0]==points[i][0]: 
          res[-1][1]=current 
         else: 
          res+=[[points[moving][0], current]] 
       else: 
        active.remove(-points[i][1]) #remove height of the lines than have been finished with scanning 
       i+=1 
      else: 
       break 
     if max(active)<current: 
      current=max(active) 
      res+=[[points[moving][0], current]] 
     moving=i 
    return res 

Answer 6

Moje rozwiązanie problemu opisane tutaj https://leetcode.com/problems/the-skyline-problem/ iteruje listę budynków dwukrotnie, jednak można to połączyć w jedną iterację. Jednakże istnieją bardziej optymalne podejście jeśli wziąć pod uwagę czystą rozwiązanie algorytm tu wyjaśnione http://www.algorithmist.com/index.php/UVa_105

class Solution { 
public: 
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) { 
     // The final result. 
     vector<pair<int, int>> result; 

     // To hold information about the buildings 
     std::set<BuildingInformation> buildingInformation; 

     // Go through each building, and store information about the start and end heights. 
     for (vector<vector<int>>::iterator buildingIt = buildings.begin(); buildingIt != buildings.end(); ++buildingIt) { 
      BuildingInformation buildingStart; 
      buildingStart.x = (*buildingIt)[0]; 
      buildingStart.h = (*buildingIt)[2]; 
      buildingStart.StartOrEnd = Start; 
      buildingInformation.insert(buildingStart); 
      buildingStart.x = (*buildingIt)[1]; 
      buildingStart.StartOrEnd = End; 
      buildingInformation.insert(buildingStart); 
     } 

     // Keep track of the current height. 
     int currentHeight = 0; 

     // A map of active building heights against number of buildings (to handle multiple buildings overlapping with same height). 
     // As it is a map, it'll be sorted by key, which is the height. 
     std::map<int, int> heights; 

     // Go through each building information that we generated earlier. 
     for (std::set<BuildingInformation>::iterator it = buildingInformation.begin(); it != buildingInformation.end(); ++it) { 
      if (it->StartOrEnd == Start) { 
       // This is a start point, do we have this height already in our map? 
       if (heights.find(it->h) != heights.end()) { 
        // Yes, increment count of active buildings with this height/ 
        heights[ it->h ] += 1;  
       } else { 
        // Nope, add this building to our map. 
        heights[ it->h ] = 1; 
       } 

       // Check if building height is taller than current height. 
       if (it->h > currentHeight) { 
        // Update current height and add marker to results. 
        currentHeight = it->h; 
        result.push_back(pair<int, int>(it->x, currentHeight)); 
       } 
      } else { 
       // This is an end point, get iterator into our heights map. 
       std::map<int, int>::iterator heightIt = heights.find(it->h); 

       // Reduce by one. 
       heightIt->second -= 1; 

       // If this was the last building of the current height in the map... 
       if (heightIt->second == 0) { 
        // Remove from heights map. 
        heights.erase(heightIt); 

        // If our height was the current height... 
        if (it->h == currentHeight) { 
         // If we have no more active buildings... 
         if (heights.size() == 0) { 
          // Current height is zero. 
          currentHeight = 0; 
         } else { 
          // Otherwise, get iterator to one past last. 
          heightIt = heights.end(); 

          // Go back to get last valid iterator. 
          --heightIt; 

          // Store current height. 
          currentHeight = heightIt->first; 
         } 

         // Add marker to results. 
         result.push_back(pair<int, int>(it->x, currentHeight)); 
        } 
       } 
      } 
     } 

     return result; 
    } 
private: 
    // Is this a building start or end? 
    enum BuildingStartOrEnd 
    { 
     Start = 0, 
     End 
    }; 

    // Information about building, there are two of these for each building, one for start, one for end. 
    struct BuildingInformation 
    { 
     int x; 
     int h; 
     BuildingStartOrEnd StartOrEnd; 

     // The ordering algorithm for the key, the rules we want to implement is keys are put in X order, and 
     // in the case of a tie (x values the same), we want Start pieces to come before End pieces (this is 
     // to handle cases where an old building ends and a new building begins on same X index, in which case 
     // we want to process the new start before processing the old end), however if we have two Start pieces 
     // at the same index, we wish to favour taller pieces (in this scenario we want to add a marker for the 
     // tallest building), finally if we have two End pieces at the same index, we wish to prefer lower 
     // pieces, as when multiple buildings end, we only want to add one result for the ultimate lowest point. 
     bool operator < (const BuildingInformation & rhs) const 
     { 
      if (x == rhs.x) 
      { 
       if (StartOrEnd == rhs.StartOrEnd) { 
        if (StartOrEnd == Start) 
         return h > rhs.h; 
        else 
         return h < rhs.h; 
       } else { 
        return StartOrEnd < rhs.StartOrEnd; 
       } 
      } 

      return x < rhs.x; 
     } 
    }; 
};