Algoritmo de diseño de Exposé

Question

Estoy haciendo algo que establece elementos similares a lo que Mac OS X hace con Windows en Exposé. Se adapta a la relación de aspecto de los elementos y a la relación de aspecto del área disponible.

Básicamente, el área disponible se divide en filas y columnas. Se coloca un elemento en cada celda (la intersección de una fila y columna). Los elementos deben mantener su relación de aspecto (aquí width/height) a pesar de la relación de aspecto de la celda. El número de celdas debe ser mayor o igual que el número de elementos. En el caso en que la cantidad de celdas sea mayor que la cantidad de elementos, la última fila no se utilizará por completo. El objetivo es tener la mayor cantidad de área disponible utilizada por los elementos como sea posible. Estoy bastante seguro de que cuanto más se aproxime la relación de aspecto de cada celda a la relación de aspecto del elemento, mejor.

Los siguientes funciona bien cuando la relación de aspecto del área disponible de es igual a las relaciones de aspecto de los artículos:

rows := round(sqrt(count)); 
columns := ceiling(sqrt(count)); 

Donde: count es el número de elementos; round(x) redondea x al valor integral más cercano, redondeando casos a medio camino de cero; y ceiling(x) devuelve el valor integral más pequeño no menos de x.

Sé Compiz utiliza el siguiente algoritmo similar, pero no tiene en cuenta las relaciones de aspecto de los artículos y área disponible:

rows := floor(sqrt(count + 1)); 
columns := ceiling(count/rows); 

Dónde: floor(x) devuelve el mayor valor entero no mayor de x .

Armado el siguiente algoritmo O (n) que prueba cada combinación de filas y columnas y busca el mejor ajuste, pero seguramente hay un algoritmo O (1) ya que produce exactamente los mismos resultados que el primero (O (1)) algoritmo cuando las relaciones de aspecto de los artículos y área disponible son los mismos:

fit (itemCount, itemRatio, availableRatio) 
{ 
    bestRows := infinity; 
    bestColumns := infinity; 
    bestDiff := infinity; 

    for (rows := 1; rows <= count; rows += 1) 
    { 
     columns := ceiling(count/rows); 

     cellWidth := availableRatio/columns; 
     cellHeight := 1.0/rows; 
     cellRatio := cellWidth/cellHeight; 

     diff := abs(cellRatio - itemRatio); 

     if (diff < bestDiff) 
     { 
      bestRows := rows; 
      bestColumns := columns; 
      bestDiff := diff; 

      if (diff = 0) 
       break; 
     } 
    } 

    return (bestRows, bestColumns); 
} 

Donde: abs(x) devuelve el valor absoluto de x.

NOTA: Usted puede notar que esto no está optimizado en absoluto

Así que, ¿cuál es la mejor manera de tener disponible la zona más utilizada por los elementos como sea posible? (En otras palabras, ¿cómo puedo encontrar el mejor ajuste?)

Answer 1

puede empaquetar los artículos con

1. ningún hueco horizontal
2. hay espacio vertical

OK, vamos a empacar sin espacio verticalEntonces la brecha horizontal es:

Gh = nrows * availRatio - ncolumns * itemRatio 

o escrita con N

Gh = x * availRatio - N * itemRatio/x 

Gh está cerca de 0 a

x² = N * itemRatio/availRatio 
x = sqrt(N * itemRatio/availRatio) 

Usted tiene que comprobar ceil (x) y el suelo (x) , y y = piso (N/x)

Embalaje sin rendimientos de rendija horizontal:

y = sqrt(N * availRatio/itemRatio) 

usted tiene que comprobar ceil (y) y el suelo (y), y x = suelo (N/a)

por lo que hay un máximo de 4 combinaciones para comprobar la brecha. Luego elige eso con el espacio positivo más pequeño.

fit (itemCount, itemRatio, availableRatio) { 
    x := sqrt(itemcount * itemRatio/availableRatio); 
    x1 := floor(x); 
    y1 := ceil(itemCount/x1); 
    x2 := ceil(x); 
    y2 := ceil(itemCount/x2); 

    y := sqrt(itemcount * availableRatio/itemRatio); 
    y3 := floor(x); 
    x3 := ceil(itemCount/y3); 
    y4 := ceil(x); 
    x4 := ceil(itemCount/y4); 

    gap := y1 * availableRatio - x1 * itemRatio; 
    x := x1; 
    y := y1; 

    gap2 := y2 * availableRatio - x2 * itemRatio; 
    if (gap2 >= 0 && gap2 < gap || gap < 0) { 
     gap := gap2; 
     x := x2; 
     y := y2; 
    } 

    gap3 := x3 * itemRatio/availRatio - y3; 
    if (gap3 >= 0 && gap3 < gap || gap < 0) { 
     gap := gap3; 
     x := x3; 
     y := y3; 
    } 

    gap4 := x4 * itemRatio/availRatio - y4; 
    if (gap4 >= 0 && gap4 < gap || gap < 0) { 
     gap := gap4; 
     x := x4; 
     y := y4; 
    } 

    return (x, y); 
} 

En lugar de utilizar la brecha también se puede utilizar el área mínima para decidir, desde la última fila/columna podría no ser llenado muy bien.