Grille optimisée pour articles rectangulaires

Question

J'ai N éléments rectangulaires avec un rapport d'aspect Aitem (X: Y).
J'ai une zone d'affichage rectangulaire avec un rapport d'aspect Aview

Les éléments doivent être disposés selon une disposition de type table (par exemple, r lignes, colonnes C).

Quelles sont les lignes de grille idéales x colonnes, de sorte que les éléments individuels sont les plus grands? (rows * colums> = N, bien sûr, c'est-à-dire qu'il peut y avoir des emplacements de grille "inutilisés"). Un algorithme simple peut itérer sur les lignes = 1..N, calculer le nombre de colonnes requis et conserver la paire ligne/colonne avec les éléments les plus importants.

Je me demande s'il existe un algorithme non itératif, bien que (par exemple pour Aitem = Aview = 1, les lignes/cols peuvent être approximés par sqrt (N)).

Answer 1

Note: Je ne comprenais pas très bien la réponse de Frédéric, alors j'ai résolu le problème moi-même et j'ai trouvé ce qui semblait être la même solution. J'ai pensé que je pourrais aussi bien expliquer ce que j'ai fait au cas où cela serait utile.

D'abord j'ai normalisé le rapport d'aspect de la vue à celui des articles. (Je suppose que vous ne voulez pas faire pivoter les éléments.)

a = (view_width/view_height)/(item_width/item_height) 

emballage maintenant un rectangle de rapport largeur/hauteur a avec des carrés est équivalente à la vue avec l'emballage des articles. serait le cas idéal pour notre grille (des carrés maintenant) pour remplir le rectangle complètement, ce qui nous donnerait

a = c/r 

où r et c sont le nombre de lignes et de colonnes:

N = r*c 

Multiplication/divisant ces deux équations nous donne

N*a = c^2    N/a = r^2 
c = sqrt(N*a)   r = sqrt(N/a) 

Si la grille est parfaite, et rc seront entiers, mais sinon, vous devez essayer les trois options Frédéric dessus et garder celui où r*c est le plus petit, mais encore plus N:

• floor(r), ceil(c)
• ceil(r), floor(c)
• ceil(r), ceil(c)

Answer 2

Bonne question. Si votre point de vue a des dimensions A x B (fixe) et vos articles ont des dimensions axb (variable, à maximisée), alors vous avez besoin:

trunc(A/a) * trunc(B/b) >= N

Je ne sais pas comment résoudre ce problème si - le trunc est la partie délicate, car elle est non linéaire.

Answer 3

Votre solution peut être facilement améliorée pour traiter le cas générique:

Si nous (temporaire) oublier la nécessité d'avoir un nombre entier de lignes et de colonnes, nous avons

lignes * colonnes = N

x = y * AItem

aview = rangées * x = rangées * * y AItem

colonnes 1 = * y = (N/lignes) * (aview/[ait em * lignes]) = N * aview/(AItem * rows²)

donc rangs = sqrt (N * aview/AItem) et colonnes = N/lignes = sqrt (N * AItem/AView)

Ensuite, ceil (lignes) et ceil (colonnes) est une solution alors que le sol (lignes) et le sol (colonnes) sont trop petits pour être une solution ensemble (si les lignes et les colonnes ne sont pas des nombres entiers). Cela laisse 3 solutions possibles:

• étage (lignes) ceil (colonnes)
• Ceil (lignes) sol (colonnes)
• Ceil (lignes) ceil (colonnes)

édités pour corriger les équations. Le premier résultat était erroné (voir les commentaires)