skyline algorithm

Question

Как найти вершины ломаной линии, которая окружает силуэт на этом изображении?

возможный вход для приведенного выше примера:

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

Таким образом, для данного примера решение будет

 
[(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 где я изначально видел неполадку

И Algorithmist имеет объяснение решения: http://www.algorithmist.com/index.php/UVa_105

Answer 2

В наивной случае, это не похоже, очень трудно алгоритм. Знаете ли вы, будет ли размер ввода большим/большим?

Моя первоначальная попытка: Попробуйте переместиться слева направо. Сначала выберите блок с самым левым краем, который существует на исходной линии. Поднимитесь на вершину. Найдите все блоки с левым краем между текущей точкой и верхней правой точкой текущего блока. Из этого набора выберите ближайший (но проверьте для случаев краев, каламбур не предназначен). Если набор пуст, начните работать по правой стороне блока, ищите другие блоки, которые вы можете перехватить.

В основном это именно то, как вы проследите его своим глазом.

Вы можете сделать некоторую простую оптимизацию, сохранив отсортированные списки, а затем выполнив поиск в списках, а не найдя наборы и копая вокруг. Например, вы можете сохранить 4 отсортированных списка блоков, каждый из которых сортируется по координате x или y одной из сторон.

Если у вас много, много блоков, вы можете рассмотреть возможность использования многомерной структуры данных для дальнейшей организации информации.

Answer 3

Это довольно просто. Создайте массив, который является длиной оси X, инициализируйте до 0. Когда вы читаете на входах, записывайте высоты в этот массив, если высота> = текущее значение в этом месте в массиве.

Затем просто перебирайте массив и каждый раз, когда значение изменяется, оно является вершиной.

В основном:

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

Я сделал класс Java, чтобы попытаться решить эту проблему. Класс включает в себя методы генерации, решения и печати наборов данных. Я не тестировал экстенсивно, возможно, осталось несколько ошибок. Кроме того, мое решение может быть излишне сложным, но оно предназначено для работы (теоретически) для недискретных значений высоты и координат.

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

Я решил эту проблему, используя алгоритм развертки. Это решение класса python.

есть две клавиши: 1) используя переменные «точки» для сохранения всех левых и правых точек и их высот и знака высоты, чтобы указать, остались ли точки слева или справа. 2) переменная «активная» используется для сохранения всех активных строк, которые были отсканированы.

класс Решение: # @param {Integer [] []} здания # @return {целое число [] []} Защиту getSkyline (самоповреждения, здания): если Len (здания) == 0: возвращение [] , если Len (здания) == 1: возвращение [[здание [0] [0], здание [0] [2]], [здание [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

Мое решение проблемы, описанное здесь https://leetcode.com/problems/the-skyline-problem/, оно дважды повторяет список зданий, однако это можно объединить в одну итерацию. Тем не менее, есть более оптимальные подходы, если вы считаете, чистое решение алгоритма описание которой приводится здесь 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; 
     } 
    }; 
};