Algoritmo para maximizar la cobertura del área rectangular con azulejos de escala

Question

tengo N escalables azulejos cuadrados (botones) que necesitan ser colocado en el interior de la superficie rectangular de tamaño fijo (caja de herramientas). Me gustaría presentar los botones todos al mismo tamaño.

¿Cómo podría resolver el tamaño óptimo de las teselas que proporcionarían el área más grande de la superficie rectangular cubierta por tejas?

Answer 1

Vamos W y H sea la anchura y la altura del rectángulo.

Let s sea la longitud del lado de un cuadrado.

A continuación, el número de plazas n(s) que puede encajar en el rectángulo es floor(W/s)*floor(H/s). Desea encontrar el valor máximo de s para el cual n(s) >= N

Si traza el número de cuadrados contra s, obtendrá una función por partes constante. Las discontinuidades están en los valores W/i y H/j, donde i y j pasan por los enteros positivos.

piensa que no hay la más pequeña i para los que n(W/i) >= N, y del mismo modo el más pequeño para el que jn(H/j) >= N. Llame a estos valores más pequeños i_min y j_min. Entonces, el más grande de W/i_min y H/j_min es el s que desea.

I.e.s_max = max(W/i_min,H/j_min)

Para encontrar i_min y j_min, acaba de hacer una búsqueda de fuerza bruta: para cada uno, empezar desde 1, prueba, y el incremento.

En el caso de que N sea muy grande, puede ser desagradable buscar i y j a partir de 1 (aunque es difícil imaginar que haya una diferencia notable en el rendimiento). En este caso, podemos estimar los valores iniciales de la siguiente manera. Primero, una estimación aproximada del área de una loseta es W*H/N, correspondiente a un lado de sqrt(W*H/N). Si W/i <= sqrt(W*H/N), entonces i >= ceil(W*sqrt(N/(W*H))), de manera similar j >= ceil(H*sqrt(N/(W*H)))

Así, en lugar de iniciar los lazos en i=1 y j=1, podemos empezar a ellos en i = ceil(sqrt(N*W/H)) y j = ceil(sqrt(N*H/W))). Y OP sugiere que round funciona mejor que ceil - en el peor de los casos, una iteración extra.

Aquí es el algoritmo explicado en C++:

#include <math.h> 
#include <algorithm> 
// find optimal (largest) tile size for which 
// at least N tiles fit in WxH rectangle 
double optimal_size (double W, double H, int N) 
{ 
    int i_min, j_min ; // minimum values for which you get at least N tiles 
    for (int i=round(sqrt(N*W/H)) ; ; i++) { 
     if (i*floor(H*i/W) >= N) { 
      i_min = i ; 
      break ; 
     } 
    } 
    for (int j=round(sqrt(N*H/W)) ; ; j++) { 
     if (floor(W*j/H)*j >= N) { 
      j_min = j ; 
      break ; 
     } 
    } 
    return std::max (W/i_min, H/j_min) ; 
} 

Lo anterior está escrito para mayor claridad. El código se puede ajustar considerablemente de la siguiente manera:

double optimal_size (double W, double H, int N) 
{ 
    int i,j ; 
    for (i = round(sqrt(N*W/H)) ; i*floor(H*i/W) < N ; i++){} 
    for (j = round(sqrt(N*H/W)) ; floor(W*j/H)*j < N ; j++){} 
    return std::max (W/i, H/j) ; 
} 

Answer 2

La primera heurístico, muy áspera es tomar

s = floor(sqrt((X x Y)/N)) 

donde s es el botón del lado de longitud, X y Y son la anchura y la altura de la caja de herramientas, y N es el número de botones .

En este caso, s será el lado de longitud máxima posible. Sin embargo, no es necesariamente posible asignar este conjunto de botones a la barra de herramientas.

Imagine una barra de herramientas que es de 20 unidades por 1 unidad con 5 botones. La heurística le dará una longitud lateral de 2 (área de 4), con un área total de cobertura de 20. Sin embargo, la mitad de cada botón estará fuera de la barra de herramientas.

Answer 3

Me gustaría tener un enfoque iterativo aquí. Verificaría si es posible colocar todos los botones en una sola fila. De lo contrario, verifique si es posible encajar en dos filas, y así sucesivamente.

Say W es el lado más pequeño de la caja de herramientas. H es el otro lado.

Para cada iteración, me gustaría comprobar lo mejor y peor de los casos posibles, en ese orden. El mejor caso significa, digamos que es la enésima iteración, que probaría un tamaño de botones W/n X W/n. Si el valor de h es suficiente, entonces terminamos. De lo contrario, el peor caso es probar (W/(n + 1)) + 1 X (W/(n + 1)) + 1 botones de tamaño. Si es posible ajustar todos los botones, probaría un método de bisección entre W/n y (W/(n + 1)) + 1. Si no, la iteración continúa en n + 1.

Answer 4

Sea n (s) el número de cuadrados que pueden caber y su lado. Deje W, H ser los lados del rectángulo para llenar. Luego n (s) = piso (W/s) * piso (H/s). Esta es una función monótonamente decreciente en sy también constante por partes, por lo que puede realizar una ligera modificación de la búsqueda binaria para encontrar las más pequeñas de forma que n (s)> = N pero n (s + eps) < N. Usted comienza con un límite superior e inferior en su = min (W, H) yl = piso (min (W, H)/N) luego calcule t = (u + l)/2. Si n (t)> = N entonces l = min (W/piso (W/t), H/piso (H/t)) de lo contrario u = max (W/piso (W/t), H/piso (H/t)). Deténgase cuando usted y yo permanezcamos iguales en iteraciones consecutivas. Así que es como la búsqueda binaria, pero explota el hecho de que la función es por partes constante y los puntos de cambio son cuando W o H son un múltiplo exacto de s. Buen pequeño problema, gracias por proponerlo.

Answer 5

Sabemos que cualquier solución óptima (puede haber dos) llenará el rectángulo ya sea horizontal o verticalmente. Si encontró una solución óptima que no llenó el rectángulo en una dimensión, siempre puede aumentar la escala de las teselas para llenar una dimensión.

Ahora, cualquier solución que maximice la superficie cubierta tendrá una relación de aspecto cercana a la relación de aspecto del rectángulo. La relación de aspecto de la solución es vertical tile count/horizontal tile count (y la relación de aspecto del rectángulo es Y/X).

Puede simplificar el problema forzando Y>=X; en otras palabras, si X>Y, transpone el rectángulo. Esto le permite solo pensar en relaciones de aspecto> = 1, siempre que recuerde transponer la solución de regreso.

Una vez que haya calculado la relación de aspecto, que desea encontrar soluciones al problema de la V/H ~= Y/X, donde V es el recuento de baldosas vertical y H es el recuento de baldosas horizontal. Encontrará hasta tres soluciones: la más cercana V/H a Y/X y V+1, V-1. En ese punto, simplemente calcule la cobertura según la escala usando V y H y tome el máximo (podría haber más de uno).

Answer 6

Creo que esto se puede resolver como un problema de minimización limitado, que requiere un cálculo básico. .

Definiciones:

a, l -> rectangle sides 
    k -> number of squares 
    s -> side of the squares 

Se tienen que minimizar la función:

f[s]:= a * l/s^2 - k 

sujeto a las limitaciones:

IntegerPart[a/s] IntegerPart[l/s] - k >= 0 
    s > 0 

I programado una pequeña función de Mathematica para hacer el truco

f[a_, l_, k_] := NMinimize[{a l/s^2 - k , 
           IntegerPart[a/s] IntegerPart[l/s] - k >= 0, 
           s > 0}, 
           {s}]  

Fácil de leer ya que las ecuaciones son las mismas que las de arriba.

El uso de esta función que compone una tabla de asignación de plazas

por lo que yo puedo ver, los resultados son correctos.

Como dije, puede usar un paquete de cálculo estándar para su entorno, o también puede desarrollar su propio algoritmo y programas de minimización. Toca el timbre si decides la última opción y te daré algunos buenos consejos.

HTH!

Editar

Sólo por diversión hice un diagrama con los resultados.

Y durante 31 azulejos:

Edición 2: Parámetros característicos

El problema tiene tres parámetros característicos:

1. el tamaño resultante de las baldosas
2. el número de baldosas
3. la relación L/a del rectángulo que encierra

Tal vez el último puede resultar un tanto sorprendente, pero es fácil de entender: si tiene un problema con un rectángulo de 7x5 y 6 fichas para colocar, mirando en la tabla de arriba, el tamaño de los cuadrados será 2.33. Ahora, si tiene un rectángulo de 70x50, obviamente los mosaicos resultantes serán 23.33, escalando isométricamente con el problema.

Entonces, podemos tomar esos tres parámetros y construir una representación 3D de su relación, y eventualmente hacer coincidir la curva con alguna función más fácil de calcular (usando mínimos cuadrados, por ejemplo, o computando regiones de valores iso).

De todos modos, la trama escalado resultante es:

Answer 7

Soy consciente de que es un hilo viejo, pero recientemente he resuelto este problema de una manera que creo que es eficiente y siempre da la respuesta correcta. Está diseñado para mantener una relación de aspecto determinada. Si desea que los niños (botones en este caso) sean cuadrados simplemente use una relación de aspecto de 1. Actualmente estoy usando este algoritmo en algunos lugares y funciona muy bien.

 double VerticalScale; // for the vertical scalar: uses the lowbound number of columns 
     double HorizontalScale;// horizontal scalar: uses the highbound number of columns 
     double numColumns; // the exact number of columns that would maximize area 
     double highNumRows; // number of rows calculated using the upper bound columns 
     double lowNumRows; // number of rows calculated using the lower bound columns 
     double lowBoundColumns; // floor value of the estimated number of columns found 
     double highBoundColumns; // ceiling value of the the estimated number of columns found 


     Size rectangleSize = new Size(); // rectangle size will be used as a default value that is the exact aspect ratio desired. 
     // 
     // Aspect Ratio = h/w 
     // where h is the height of the child and w is the width 
     // 
     // the numerator will be the aspect ratio and the denominator will always be one 
     // if you want it to be square just use an aspect ratio of 1 
     rectangleSize.Width = desiredAspectRatio; 
     rectangleSize.Height = 1; 

     // estimate of the number of columns useing the formula: 
     //       n * W * h  
     // columns = SquareRoot( ------------- ) 
     //       H * w   
     // 
     // Where n is the number of items, W is the width of the parent, H is the height of the parent, 
     // h is the height of the child, and w is the width of the child 
     numColumns = Math.Sqrt((numRectangles * rectangleSize.Height * parentSize.Width)/(parentSize.Height * rectangleSize.Width)); 

     lowBoundColumns = Math.Floor(numColumns); 
     highBoundColumns = Math.Ceiling(numColumns); 

     // The number of rows is determined by finding the floor of the number of children divided by the columns 
     lowNumRows = Math.Ceiling(numRectangles/lowBoundColumns); 
     highNumRows = Math.Ceiling(numRectangles/highBoundColumns); 

     // Vertical Scale is what you multiply the vertical size of the child to find the expected area if you were to find 
     // the size of the rectangle by maximizing by rows 
     // 
     //      H 
     // Vertical Scale = ---------- 
     //     R * h 
     // 
     // Where H is the height of the parent, R is the number of rows, and h is the height of the child 
     // 
     VerticalScale = parentSize.Height/lowNumRows * rectangleSize.Height; 

     //Horizontal Scale is what you multiply the horizintale size of the child to find the expected area if you were to find 
     // the size of the rectangle by maximizing by columns 
     // 
     //      W 
     // Vertical Scale = ---------- 
     //     c * w 
     // 
     //Where W is the width of the parent, c is the number of columns, and w is the width of the child 
     HorizontalScale = parentSize.Width/(highBoundColumns * rectangleSize.Width); 

     // The Max areas are what is used to determine if we should maximize over rows or columns 
     // The areas are found by multiplying the scale by the appropriate height or width and finding the area after the scale 
     //      
     // Horizontal Area = Sh * w * ((Sh * w)/A) 
     //      
     // where Sh is the horizontal scale, w is the width of the child, and A is the aspect ratio of the child 
     // 
     double MaxHorizontalArea = (HorizontalScale * rectangleSize.Width) * ((HorizontalScale * rectangleSize.Width)/desiredAspectRatio); 
     // 
     //      
     // Vertical Area = Sv * h * (Sv * h) * A 
     // Where Sv isthe vertical scale, h is the height of the child, and A is the aspect ratio of the child 
     // 
     double MaxVerticalArea = (VerticalScale * rectangleSize.Height) * ((VerticalScale * rectangleSize.Height) * desiredAspectRatio); 


     if (MaxHorizontalArea >= MaxVerticalArea) // the horizontal are is greater than the max area then we maximize by columns 
     { 
      // the width is determined by dividing the parent's width by the estimated number of columns 
      // this calculation will work for NEARLY all of the horizontal cases with only a few exceptions 
      newSize.Width = parentSize.Width/highBoundColumns; // we use highBoundColumns because that's what is used for the Horizontal 
      newSize.Height = newSize.Width/desiredAspectRatio; // A = w/h or h= w/A 

      // In the cases that is doesnt work it is because the height of the new items is greater than the 
      // height of the parents. this only happens when transitioning to putting all the objects into 
      // only one row 
      if (newSize.Height * Math.Ceiling(numRectangles/highBoundColumns) > parentSize.Height) 
      { 
       //in this case the best solution is usually to maximize by rows instead 
       double newHeight = parentSize.Height/highNumRows; 
       double newWidth = newHeight * desiredAspectRatio; 

       // However this doesn't always work because in one specific case the number of rows is more than actually needed 
       // and the width of the objects end up being smaller than the size of the parent because we don't have enough 
       // columns 
       if (newWidth * numRectangles < parentSize.Width) 
       { 
        //When this is the case the best idea is to maximize over columns again but increment the columns by one 
        //This takes care of it for most cases for when this happens. 
        newWidth = parentSize.Width/Math.Ceiling(numColumns++); 
        newHeight = newWidth/desiredAspectRatio; 

        // in order to make sure the rectangles don't go over bounds we 
        // increment the number of columns until it is under bounds again. 
        while (newWidth * numRectangles > parentSize.Width) 
        { 
         newWidth = parentSize.Width/Math.Ceiling(numColumns++); 
         newHeight = newWidth/desiredAspectRatio; 
        } 

        // however after doing this it is possible to have the height too small. 
        // this will only happen if there is one row of objects. so the solution is to make the objects' 
        // height equal to the height of their parent 
        if (newHeight > parentSize.Height) 
        { 
         newHeight = parentSize.Height; 
         newWidth = newHeight * desiredAspectRatio; 
        } 
       } 

       // if we have a lot of added items occaisionally the previous checks will come very close to maximizing both columns and rows 
       // what happens in this case is that neither end up maximized 

       // because we don't know what set of rows and columns were used to get us to where we are 
       // we must recalculate them with the current measurements 
       double currentCols = Math.Floor(parentSize.Width/newWidth); 
       double currentRows = Math.Ceiling(numRectangles/currentCols); 
       // now we check and see if neither the rows or columns are maximized 
       if ((newWidth * currentCols) < parentSize.Width && (newHeight * Math.Ceiling(numRectangles/currentCols)) < parentSize.Height) 
       { 
        // maximize by columns first 
        newWidth = parentSize.Width/currentCols; 
        newHeight = newSize.Width/desiredAspectRatio; 

        // if the columns are over their bounds, then maximized by the columns instead 
        if (newHeight * Math.Ceiling(numRectangles/currentCols) > parentSize.Height) 
        { 
         newHeight = parentSize.Height/currentRows; 
         newWidth = newHeight * desiredAspectRatio; 
        } 
       } 

       // finally we have the height of the objects as maximized using columns 
       newSize.Height = newHeight; 
       newSize.Width = newWidth; 

      } 

     } 
     else 
     { 
      //Here we use the vertical scale. We determine the height of the objects based upong 
      // the estimated number of rows. 
      // This work for all known cases 
      newSize.Height = parentSize.Height/lowNumRows; 
      newSize.Width = newSize.Height * desiredAspectRatio; 
     } 

Al final del algoritmo 'newSize' tiene el tamaño adecuado. Esto está escrito en C#, pero sería bastante fácil de trasladar a otros idiomas.