Algorithme de présentation de l'exposition

Question

Je crée des éléments qui ressemblent à ceux de Mac OS X avec Windows dans Exposé. Il s'adapte au rapport d'aspect des articles et au rapport d'aspect de la zone disponible.

Fondamentalement, la zone disponible est divisée en lignes et en colonnes. Un élément est placé dans chaque cellule (l'intersection d'une ligne et d'une colonne). Les éléments doivent conserver leur ratio d'aspect (ici width/height) malgré le format de la cellule. Le nombre de cellules doit être supérieur ou égal au nombre d'éléments. Dans le cas où le nombre de cellules est supérieur au nombre d'éléments, la dernière rangée ne sera pas entièrement utilisée. Le but est d'avoir autant de surface disponible utilisée par les articles que possible. Je suis à peu près sûr que plus le ratio d'aspect de chaque cellule est proche du format de l'élément, mieux c'est.

Les ouvrages suivants et lorsque le ratio d'aspect de surface disponible est égal au rapport d'aspect des produits:

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

Où: count est le nombre d'éléments; round(x) arrondit x à la valeur intégrale la plus proche, en arrondissant à mi-chemin les cas éloignés de zéro; et ceiling(x) renvoie la plus petite valeur intégrale non inférieure à x.

Je sais que Compiz utilise l'algorithme similaire suivant, mais il ne prend pas en compte les rapports d'aspect des éléments et la surface disponible:

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

Où: floor(x) retourne la plus grande valeur intégrale non supérieure à x .

Je ai mis en place l'algorithme O (n) suivant qui teste chaque combinaison de lignes et de colonnes et cherche le meilleur ajustement, mais il y a sûrement un algorithme O (1) car cela produit exactement les mêmes (1)) algorithme lorsque les rapports d'aspect des articles et de la zone disponible sont les mêmes:

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

Où: abs(x) renvoie la valeur absolue de x.

REMARQUE: Vous remarquerez peut-être ce n'est pas optimisé du tout

Alors, quelle est la meilleure façon d'avoir la zone la plus disponible utilisé par les éléments que possible? (En d'autres termes, comment puis-je trouver la meilleure solution?)

Answer 1

Vous pouvez emballer les articles avec

1. aucun écart horizontal
2. pas d'espace vertical

Ok, laissez emballer de sans écart vertical.Ensuite, l'écart horizontal est:

Gh = nrows * availRatio - ncolumns * itemRatio 

ou écrit avec N

Gh = x * availRatio - N * itemRatio/x 

Gh est proche de 0 à

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

Vous devez vérifier Ceil (x) et le plancher (x) , et y = plancher (N/x)

Emballage sans écart horizontal rendements:

y = sqrt(N * availRatio/itemRatio) 

Vous devez vérifier Ceil (y) et le sol (y), et x = étage (N/y)

Donc, il y a jusqu'à 4 combinaisons pour vérifier l'écart. Ensuite, choisissez celui avec le plus petit écart positif.

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

Au lieu d'utiliser l'espace, vous pouvez également utiliser la zone minimale de décider, depuis la dernière ligne/colonne peut être pas rempli très bien.