¿Qué algoritmo se puede utilizar para empaquetar rectángulos de diferentes tamaños en el rectángulo más pequeño posible de una manera bastante óptima?

Ver esta página en el proyecto ARC para una encuesta de soluciones, hay un equilibrio entre la complejidad/tiempo de implementación y la optimalidad, pero hay una amplia gama de algoritmos para elegir.

Aquí hay un extracto de los algoritmos:

1. Algoritmo de Altura decreciente de Primer ajuste (FFDH)
   FFDH empaqueta el siguiente artículo R (en altura no creciente)en el primer nivel donde cabe R. Si ningún nivel puede acomodar R, se crea un nuevo nivel.
   Complejidad temporal de FFDH: O (n * log n).
   Relación de aproximación: FFDH (I)

2. Siguiente-Ajuste de la Altura decreciente (NFDH) algoritmo
   NFDH empaqueta el siguiente elemento R (en altura no creciente) en el nivel actual si R encaja. De lo contrario, el nivel actual es "cerrado" y se crea un nuevo nivel.
   Complejidad temporal: O (n * log n).
   Relación de aproximación: NFDH(I)

3. Disminución del Mejor Ajuste Algoritmo de altura (BFDH)
   BFDH empaqueta el siguiente elemento R (en altura no creciente) en el nivel, entre los que pueden acomodar R, para los cuales el espacio horizontal residual es el mínimo. Si ningún nivel puede acomodar R, se crea un nuevo nivel.

4. Algoritmo inferior izquierdo (BL)
   BL artículos de primer orden por ancho no creciente. BL empaqueta el siguiente artículo tan cerca de la parte inferior como quepa y luego tan cerca de la izquierda como pueda ir sin superponerse con ningún artículo empacado. Tenga en cuenta que BL no es un algoritmo de empaquetamiento orientado a niveles.
   Complejidad temporal: O (n^2).
   Relación de aproximación: BL (I)

5. Algoritmo Up-Down (UD) de Baker
   UD utiliza una combinación de BL y una generalización de NFDH. El ancho de la tira y los elementos se normalizan de modo que la tira sea de ancho de unidad. UD ordena los elementos en ancho no creciente y luego divide los elementos en cinco grupos, cada uno con ancho en el rango (1/2, 1], (1/3,1/2], (1/4,1/3], (1/5,1/4], (0,1/5]. La franja también se divide en cinco regiones R1·***, R5. Básicamente, algunos elementos de ancho en el rango (1/i+1, 1/i], para 1 Relación de aproximación: UD (I)

6. Algoritmo de ajuste inverso (RF)
   RF también normaliza el ancho de la tira y los elementos para que la tira sea de ancho de unidad. RF primero apila todos los elementos de ancho mayor que 1/2. Los elementos restantes se ordenan en no aumentar la altura y se embalará por encima de la altura H0 alcanzado por los mayores de 1/2. Entonces RF repite el siguiente proceso. En términos generales, RF empaqueta artículos de izquierda a derecha con su parte inferior a lo largo de la línea de altura H0 hasta que no haya más espacio. Luego empaqueta los elementos de derecha a izquierda y de arriba a abajo (llamado nivel inverso) hasta que el ancho total sea al menos 1/2. Luego, el nivel inverso se baja hasta que (al menos) uno de ellos toque algún elemento a continuación. El menú desplegable de alguna manera repetido.
   Relación de aproximación: RF (I)

7. Algoritmo de Steinberg
   El algoritmo de Steinberg, denotado como M en el documento, estima un límite superior de la altura H requerida para empacar todos los elementos de tal manera que se demuestre que los elementos de entrada se pueden empacar en un rectángulo de ancho W y altura H. Luego definen siete procedimientos (con siete condiciones), cada uno para dividir un problema en dos más pequeños y resolverlos recursivamente. Se ha demostrado que cualquier el problema tratable satisface una de las siete condiciones.
   Relación de aproximación: M (I)

8. Algoritmo de ajuste dividido (SF) SF divide los elementos en dos grupos, L1 con un ancho mayor que 1/2 y L2 como máximo 1/2. Todos los artículos de L1 son embalados primero por FFDH. Luego están dispuestos de manera que todos los artículos con un ancho superior a 2/3 estén por debajo de los que tienen un ancho máximo de 2/3. Esto crea un rectángulo R de espacio con ancho 1/3. Los artículos restantes en L2 se empaquetan en R y el espacio anterior ésos embalados con L1 usando FFDH. Los niveles creados en R se consideran inferiores a los creados por encima del embalaje de L1.
   Relación de aproximación: SF (I)

9. Algoritmo de Sleator
   El algoritmo de Sleater consta de cuatro pasos:

   1. Todos los artículos de ancho superior a 1/2 se embalan uno encima del otro en la parte inferior de la tira. Supongamos que h0 es la altura del embalaje resultante Todo el embalaje posterior ocurrirá por encima de h0.

   2. Los artículos restantes se ordenan por altura no creciente. Un nivel de artículos se empaquetan (en orden de altura no creciente) de izquierda a derecha a lo largo de la línea de altura h0.

   3. Luego se dibuja una línea vertical en el medio para cortar la tira en dos mitades iguales (tenga en cuenta que esta línea puede cortar un artículo que se empaqueta parcialmente en la mitad derecha). Dibuja dos segmentos de línea horizontal de longitud una mitad, una a través de la mitad izquierda (llamada la línea de base izquierda) y una a través de la mitad derecha (llamada la línea de base derecha) tan baja como sea posible de modo que las dos líneas no crucen ningún elemento.

   4. Elija la línea de base izquierda o derecha que sea de una altura más baja y empaque un nivel de artículos en la mitad correspondiente de la tira hasta que el siguiente artículo sea demasiado ancho.

   Se forma una nueva línea de base y el paso (4) se repite en la línea de base inferior hasta que se empaquetan todos los elementos.
   Complejidad temporal: O (n * log n).
   La relación de aproximación de El algoritmo de Sleator es 2.5, que es ajustado.

Eche un vistazo a problemas de embalaje. Creo que el tuyo cae bajo ' 2D bin packing."Usted debe ser capaz de aprender mucho de las soluciones a ese y otros problemas de embalaje.

Ver también: Empaquetar datos de imagen rectangulares en una textura cuadrada.

Existe una extensa literatura sobre este problema. Una buena heurística codiciosa es colocar rectángulos desde el área más grande hasta el más pequeño en la primera posición disponible hacia la parte inferior e izquierda del contenedor. Piense en la gravedad tirando de todos los elementos hacia abajo a la esquina inferior izquierda. Para una descripción de este google "Chazelle embalaje inferior izquierda".

Para soluciones óptimas, las técnicas de vanguardia pueden empaquetar más de 20 rectángulos en unos pocos segundos. Huang tiene un algoritmo que separa el problema de encontrar el cuadro delimitador más pequeño del problema de decidir si un conjunto de rectángulo puede caber o no en un cuadro delimitador de un tamaño específico. Le das a su programa un conjunto de rectángulos, y te dice el cuadro delimitador más pequeño requerido para empaquetarlos.

Para su caso, su bucle exterior debe iterar desde el cuadro delimitador más pequeño posible hacia arriba (con el ancho y la altura aumentando sucesivamente por potencias de dos). Para cada uno de estos límites cajas, prueba para ver si puedes encontrar un embalaje para tus rectángulos. Obtendrá un montón de respuestas" no", hasta la primera respuesta" sí", que se garantizará que sea la solución óptima.

Para el bucle interno de su algoritmo the el que responde "sí" o "no" a un cuadro delimitador de tamaño específico, buscaría la referencia de Huang y simplemente implementaría su algoritmo. Incluye una gran cantidad de optimizaciones en la parte superior del algoritmo básico, pero solo se necesita la carne básica y las patatas. Dado que desea manejar rotaciones, en cada punto de ramificación durante su búsqueda, simplemente intente ambas rotaciones y retroceda cuando ambas rotaciones no resulten en una solución.

Estoy bastante seguro de que este es un problema NP-hard, por lo que, para una solución óptima, tendría que implementar un algoritmo de retroceso que intente todas las combinaciones posibles.

La buena noticia es que debido a la necesidad de empaquetar rectángulos 2D en un espacio 2D limitado, puede podar muchas posibilidades desde el principio, por lo que podría no ser TAN malo.

Lo que necesitas es https://github.com/nothings/stb/blob/master/stb_rect_pack.h

Muestra:

stbrp_context context;

struct stbrp_rect rects[100];

for (int i=0; i< 100; i++)
{
    rects[i].id = i;
    rects[i].w = 100+i;
    rects[i].h = 100+i;
    rects[i].x = 0;
    rects[i].y = 0;
    rects[i].was_packed = 0;
}

int rectsLength = sizeof(rects)/sizeof(rects[0]);

int nodeCount = 4096*2;
struct stbrp_node nodes[nodeCount];


stbrp_init_target(&context, 4096, 4096, nodes, nodeCount);
stbrp_pack_rects(&context, rects, rectsLength);

for (int i=0; i< 100; i++)
{
    printf("rect %i (%hu,%hu) was_packed=%i\n", rects[i].id, rects[i].x, rects[i].y, rects[i].was_packed);
}

Una solución general no es trivial (las matemáticas hablan por completo ****ing imposible)
Generalmente la gente usa un algoritmo genético para probar posibles combinaciones, pero puedes hacerlo razonablemente bien simplemente poniendo la forma más grande primero y luego probando diferentes lugares para la siguiente más grande y así sucesivamente.