Empiler des rectangles dans la disposition la plus carrée possible

Question

Ma situation

• J'ai un N rectangles
• Les rectangles ont tous la même forme (par exemple, 2 pouces de large x 1 pouce de hauteur) - appelons cette taille Sw et Sh pour la largeur et la hauteur
• Je souhaite placer ces rectangles dans une grille de manière à ce qu'ils soient parfaitement superposés - comme ce que vous verriez dans un tableur
• Ce dont j'ai besoin, c'est ceci: Étant donné N, Sw et Sh, quels sont le nombre de lignes (R) et de colonnes (C) qui empileraient ces droits dans la disposition la plus carrée possible
• Il est entendu que R & amp; C peut fournir plus de cellules que nécessaire (par exemple, si N = 15, Sw = 1, Sh = 1, puis R = 4, C = 4, ce qui donne 16 "intervalles" pour 15 rectangles, ce qui est OK.
• Si Sw = Sh, mes modestes compétences en mathématiques suffisent - quand les rectangles ont des largeurs et des hauteurs différentes - eh bien, cela me dépasse.

Quelques notes

• Oui, j'ai lu cette question: Empiler des rectangles à prendre aussi peu d’espace que possible et non, cela n’a pas aidé. En outre, ce n'est pas la même question. Cette question concerne des rectangles pouvant avoir différentes tailles. Dans cette question, les rectangles ont la même taille
• Oui, j'ai effectué une recherche sur wolfram.com, etc., et aucune chance là-bas
• Je ne connais pas très bien les mathématiques, je crains donc que le problème ne soit pas résolu en tant que tel. J'ai déjà effectué plusieurs recherches dans les domaines de la mosaïque, de la dissection, de la décomposition et je n'y ai pas réussi. soit

Quelques exemples

the * indicates the edges of the rects
the | indicates that a cell is "filled-in"
Notice that not all R*C cells are filled in, but only and exactly N cells

IF N=1, Sw=2, Sh=1 THEN R=1, C=1

********
*||||||*
********

IF N=2, Sw=2, Sh=1 THEN R=2, C=1

********
*||||||*
********
*||||||*
********

IF N=3, Sw=2, Sh=1 THEN R=2, C=2


***************
*||||||*      *
***************
*||||||*||||||*
***************

IF N=4, Sw=2, Sh=1 THEN R=2, C=2


***************
*||||||*||||||*
***************
*||||||*||||||*
***************

IF N=5, Sw=2, Sh=1 THEN R=3, C=2


***************
*||||||*      *
***************
*||||||*||||||*
***************
*||||||*||||||*
***************

Mise en œuvre de la réponse d'AaronofTomorrow

# Implementation of AaronofTomorrow's answer
# implemented in python 2.6
# reasonable output
# works in constant time

import math

def f( N, Sw, Sh ) :
    cols = math.sqrt( float(N) * float(Sh) / float(Sw) )
    cols = round(cols)
    rows = float(N) / float(cols)
    rows = math.ceil(rows)
    return (int(cols),int(rows))

Une autre implémentation inspirée par la réponse de Will (Mise à jour le 2008-12-08) - C’est celle que j’ai finalement utilisée

# Another implementation inspired by Will's answer
# implemented in python 2.6
# reasonable output - a bit better in yielding more squarelike grids
# works in time proportional to number of rects
#
# strategy used it to try incrementaly adding a rect.
# if the resulting rect requires more space then two
# possibilities are checked - adding a new row or adding a new col
# the one with the best aspect ratio (1:1) will be chosen 


def g( N, Sw, Sh ) :
    slope = float(Sh)/float(Sw)
    cols = 1
    rows = 1
    for i in xrange( N ) :
        num_to_fit =i+1
        allocated_cells= cols* rows
        if ( num_to_fit <= allocated_cells ) :
            pass # do nothing
        else :
            hc,wc = float(Sh * rows), float(Sw * (cols+1))
            hr,wr = float(Sh * (rows+1)), float(Sw * cols)
            thetac = math.atan( hc/wc)
            thetar = math.atan( hr/wr)
            alpha = math.pi/4.0
            difr = abs(alpha-thetar)
            difc = abs(alpha-thetac)
            if ( difr < difc ) :
                rows = rows +1
            else:
                cols = cols + 1

    return (cols,rows)

Answer 1

En vous appuyant sur la réponse de Will Dean, trouvez le dérivé de sa formule (en ce qui concerne nCols):

-N * Sh / nCols + Sw

Puis réglez-le sur 0 et résolvez pour nCols, ce qui donne:

nCols = sqrt (N * Sh / Sw)

Arrondissez cela et vous devriez avoir le nombre optimal de colonnes:

cols = round (sqrt (N * Sh / Sw))
   rows = ceil (N / cols)

Answer 2

Je pense que vous constaterez que "la forme la plus carrée" est une étape sur la voie de la "forme la plus circulaire", qui est le point où la circonférence (longueur du périmètre) sera au minimum.

Votre circonférence est 2 * nRows * Sh + 2 * nCols Sw. Vous savez que nRows nCols > = N, et je pense que simplifier cela pour nRows * nCols = N serait OK dans le bit suivant.

Sans l'essayer, je pense que vous pourriez alors utilement essayer de trouver un (le) minimum de la fonction:

N/nCols*Sh + nCols*Sw

Je ne sais pas si cela fonctionnerait, mais cela m'a utilement permis de retarder le début de ma journée de travail de 5 minutes, pour que ce ne soit pas une perte sèche.

Answer 3

Si le nombre de rectangles est illimité, vous devrez trouver le plus petit dénominateur commun (LCD) de Sw et Sh. Ensuite, vous pouvez le diviser par Sw et Sh pour trouver le compte horizontal et vertical.

Comme c'est limité, c'est différent. Dois-je bien comprendre que vous devez utiliser TOUS les rectangles et que le résultat doit également être un rectangle? Je suppose que oui.

Dans un tel cas, vous n'avez pas vraiment beaucoup de choix quant à la manière d'organiser les rectangles. Il n'y a que le nombre de paires d'entiers qui donnent N quand on les multiplie ensemble.

Dans votre cas, j'essaierais de trouver toutes les paires d'entiers possibles (utilisez une simple boucle FOR) et de voir laquelle est la plus proche d'un carré. Dans la notification de boucle FOR, vous ne devez vérifier que jusqu’à sqrt (N), car chaque paire entière trouvée après sera identique à celle que vous avez déjà trouvée, mais en sens inverse.

Answer 4

D'abord, les rectangles ou les rectangles très carrés, dans lesquels les dimensions sont égales à zéro.

Sinon, pour des raisons de simplicité, construisez-le de manière itérative:

    add a new row until height is greater than width
    add a new column until width is greater than height

qui pourrait ressembler au code suivant:

    // place the first tile as an initialisation
    int tiles = num_tiles - 1;
    int rows = 1;
    int columns = 1;
    int width = sx;
    int height = sy;

    int i=1; // just because we're curious how many iterations we have

    // build the near-square
    while(tiles > 0) {
        while((tiles > 0)
        && ((width + sx) <= (height + sy))) {
            // add a column
            tiles -= rows;
            columns++;
            width += sx;
        i++;
        }
        while((tiles > 0)
        && ((height + sy) < (width + sx))) {
            // add a row
            tiles -= columns;
            rows++;
            height += sy;
        i++;
        }
    }

    // done
    printf("%d = %d (%dx%d) = %dx%d (%dx%d) in %d\n",
    num_tiles,tiles,sx,sy,rows,columns,width,height,i);

et quelques résultats:

100 = -5 (10x20) = 7x15 (150x140) in 21
1000 = -12 (10x20) = 22x46 (460x440) in 67
10000000 = -1628 (10x20) = 2236x4473 (44730x44720) in 6708
200 = 0 (7x13) = 10x20 (140x130) in 29
2000 = -13 (7x13) = 33x61 (427x429) in 93
20000000 = -3790 (7x13) = 3282x6095 (42665x42666) in 9376
400 = -14 (17x13) = 23x18 (306x299) in 40
4000 = -15 (17x13) = 73x55 (935x949) in 127
40000000 = -192 (17x13) = 7232x5531 (94027x94016) in 12762

pire des cas O (n), pour les rectangles très très minces, ou un petit nombre de rectangles. Mais O (sqrt (n)) dans les cas généraux?