algoritmo de horizonte

Question

¿Cómo puedo encontrar los vértices de la línea quebrada que rodea la silueta en esta imagen?

Una posible entrada para el ejemplo anterior es:

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

Así que para este ejemplo la solución sería

 
[(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 es donde inicialmente vi el problema

Y Algorithmist tiene una explicación de la solución: http://www.algorithmist.com/index.php/UVa_105

Answer 2

En el caso ingenuo, esto no parece como un muy difícil algoritmo. ¿Sabes si el tamaño de entrada será grande/qué tan grande?

Mi intento inicial: intente moverse de izquierda a derecha. Primero elige el bloque con el borde más a la izquierda que existe en la línea de origen. Sube a su cima. Encuentra todos los bloques con un borde izquierdo entre el punto actual y el punto superior derecho del bloque actual. De ese conjunto, elija el más cercano (pero revise si hay casos extremos, juego de palabras no intencionado). Si el conjunto está vacío, comienza a trabajar hacia abajo en el lado derecho del bloque, buscando otros bloques que puedas interceptar.

Básicamente, así es como lo trazarías con tu ojo.

Puede hacer algunas optimizaciones simples manteniendo listas ordenadas y luego buscando en las listas en lugar de encontrar conjuntos y explorarlos. Por ejemplo, puede mantener 4 listas ordenadas de los bloques, cada una ordenada por la coordenada xo y de uno de los lados.

Si tiene muchos, muchos bloques, podría considerar el uso de una estructura de datos multidimensional para organizar aún más la información.

Answer 3

Esto es bastante simple. Haga una matriz que tenga la longitud del eje X, inicialice a 0. Mientras lee las entradas, escriba las alturas en esta matriz si la altura es> = el valor actual en esa ubicación en la matriz.

Luego simplemente recorra la matriz, y cada vez que cambie el valor, es un vértice.

Básicamente:

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

Hice una clase Java para tratar de solucionar esto. La clase incluye métodos para generar, resolver e imprimir conjuntos de datos. No he probado exhaustivamente, puede haber algunos errores restantes. Además, mi solución puede ser innecesariamente complicada, pero está diseñada para funcionar (en teoría) para valores de coordenadas y altura no discretos.

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

He resuelto este problema mediante el algoritmo de barrido de línea. Esta es una solución de clase python.

hay dos claves: 1) usando la variable "puntos" para guardar todos los puntos izquierdo y derecho y sus alturas y el signo de la altura para indicar si los puntos son hacia la izquierda o hacia la derecha. 2) la variable "activo" se usa para guardar todas las líneas activas que se han escaneado.

solución de clase: # @ Param {enteros [] []} edificios # @return {número entero [] []} def getSkyline (auto, edificios): si len (edificios) == 0: return [] si len (edificios) == 1: retorno [[edificios [0] [0], edificios [0] [2]], [edificios [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

Mi solución al problema como se describe aquí https://leetcode.com/problems/the-skyline-problem/ itera la lista de edificios dos veces, sin embargo, esto podría combinarse en una sola iteración. Sin embargo, hay métodos más óptimos si se tiene en cuenta la solución pura algoritmo se explica aquí 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; 
     } 
    }; 
};