Qual algoritmo pode ser usado para empacotar retângulos de tamanhos diferentes no menor retângulo possível de uma maneira bastante ideal?

Eu tenho um monte de objetos retangulares que preciso colocar no menor espaço possível (as dimensões desse espaço devem ser potências de dois).

Estou ciente de vários algoritmos de empacotamento que empacotarão os itens da melhor maneira possível em um determinado espaço, no entanto, neste caso, preciso do algoritmo para determinar o tamanho desse espaço também.

Por exemplo, digamos que tenho os seguintes retângulos

• 128 * 32
• 128 * 64
• 64 * 32
• 64 * 32

Eles podem ser embalados em um espaço de 128 * 128

 _________________
128 * 32
| ________________ |
128 * 64
| |
| |
| ________________ |
64 * 32 | 64 * 32 |
| _______ | ________ |

No entanto, se houvesse também 160 * 32 e 64 * 64, seria necessário um espaço de 256 * 128

 ________________________________
| 128 * 32 | 64 * 64 | 64 * 32 |
| ________________ | | _______ |
128 * 64 64 * 32
| | _______ | _______ |
| | |
| ________________ | ___ |
160 * 32 |
| ____________________ | ___________ |

Quais algoritmos são capazes de empacotar um monte de retângulos e determinar o tamanho necessário para o contêiner (com uma potência de 2 e dentro de um determinado tamanho máximo para cada dimensão)?

A solução rápida e suja do primeiro passe é sempre ótima, como uma comparação, se nada mais.

Posicionamento ganancioso de grande a pequeno.

Coloque o maior retângulo restante em sua área compactada. Se não caber em qualquer lugar, coloque-o em um local que estenda a região da embalagem o mínimo possível. Repita até terminar com o menor retângulo.

Não é perfeito, mas é fácil e uma boa linha de base. Ele ainda compacta perfeitamente o seu exemplo original e fornece uma resposta equivalente para o segundo.

Veja esta página no projeto ARC para uma pesquisa de soluções, existe uma troca entre complexidade / tempo e otimização da implementação, mas há uma ampla variedade de algoritmos para você escolher.

Aqui está um extrato dos algoritmos:

1. Algoritmo de altura decrescente de primeiro ajuste (FFDH) O
   FFDH compacta o próximo item R (em altura não crescente) no primeiro nível em que R se encaixa. Se nenhum nível puder acomodar R, um novo nível será criado.
   Complexidade temporal de FFDH: O (n · log n).
   Relação de aproximação: FFDH (I) <= (17/10) · OPT (I) +1; o limite assintótico de 17/10 é apertado.

2. O algoritmo de altura decrescente do próximo ajuste (NFDH)
   NFDH compacta o próximo item R (em altura não crescente) no nível atual, se R se encaixar. Caso contrário, o nível atual é "fechado" e um novo nível é criado.
   Complexidade temporal: O (n · log n).
   Razão de aproximação: NFDH (I) <= 2 · OPT (I) +1; o limite assintótico de 2 é apertado.

3. Algoritmo de altura decrescente de melhor ajuste (BFDH) O
   BFDH agrupa o próximo item R (em altura não crescente) no nível, entre aqueles que podem acomodar R, para os quais o espaço horizontal residual é o mínimo. Se nenhum nível puder acomodar R, um novo nível será criado.

4. Algoritmo inferior esquerdo (BL)
   Itens de primeira ordem BL por largura não crescente. O BL embala o próximo item o mais próximo possível do fundo, e o mais próximo possível da esquerda, sem sobrepor-se a nenhum item embalado. Observe que BL não é um algoritmo de empacotamento orientado por nível.
   Complexidade temporal: O (n ^ 2).
   Relação de aproximação: BL (I) <= 3 · OPT (I).

5. Algoritmo Up-Down (UD) de Baker
   UD usa uma combinação de BL e uma generalização de NFDH. A largura da faixa e os itens são normalizados para que a faixa tenha largura unitária. UD ordena os itens com largura não crescente e depois os divide em cinco grupos, cada um com largura no intervalo (1/2, 1], (1 / 3,1 / 2], (1 / 4,1 / 3 ], (1 / 5,1 / 4], (0,1 / 5]. A faixa também é dividida em cinco regiões R1, ···, R5. Basicamente, alguns itens de largura no intervalo (1 / i + 1, 1 / i], para 1 <= i <= 4, são compactados na região Ri pelo BL. Como o BL deixa um espaço de largura crescente de cima para baixo no lado direito da faixa, a UD aproveita essa vantagem primeiro embalando o item em Rj para j = 1, ···, 4 (em ordem) de cima para baixo.Se não houver espaço, o item será embalado em Ri pelo BL. Finalmente, itens de tamanho no máximo 1/5 são compactados nos espaços em R1, ···, R4 pelo algoritmo (generalizado) NFDH.
   Razão de aproximação: UD (I) <= (5/4) · OPT (I) + (53/8) H, onde H é a altura máxima dos itens; o limite assintótico de 5/4 é apertado.

6. Algoritmo de ajuste reverso (RF)
   RF também normaliza a largura da faixa e os itens para que a faixa tenha largura unitária. O RF empilha primeiro todos os itens de largura maior que 1/2. Os itens restantes são classificados em altura não crescente e serão compactados acima da altura H0 alcançada por aqueles maiores que 1/2. Em seguida, o RF repete o seguinte processo. Grosso modo, a RF empacota itens da esquerda para a direita com o fundo ao longo da linha de altura H0 até não haver mais espaço. Empacota os itens da direita para a esquerda e de cima para baixo (chamado de nível reverso) até que a largura total seja de pelo menos 1/2. Em seguida, o nível reverso é reduzido até que (pelo menos) um deles toque em algum item abaixo. A lista suspensa é repetida de alguma forma.
   Relação de aproximação: RF (I) <= 2 · OPT (I).

7. Algoritmo de Steinberg O algoritmo de
   Steinberg, indicado como M no artigo, estima um limite superior da altura H necessária para embalar todos os itens, de modo que se prove que os itens de entrada podem ser compactados em um retângulo de largura W e altura H. Eles então defina sete procedimentos (com sete condições), cada um para dividir um problema em dois menores e resolvê-los recursivamente. Foi demonstrado que qualquer problema tratável satisfaz uma das sete condições.
   Relação de aproximação: M (I) <= 2 · OPT (I).

8. Algoritmo Split-Fit (SF) SF divide itens em dois grupos, L1 com largura maior que 1/2 e L2 no máximo 1/2. Todos os itens de L1 são embalados pela FFDH. Em seguida, eles são organizados de forma que todos os itens com largura superior a 2/3 fiquem abaixo daqueles com largura no máximo 2/3. Isso cria um retângulo R de espaço com largura 1/3. Os itens restantes em L2 são empacotados para R e o espaço acima daqueles empacotados com L1 usando FFDH. Os níveis criados em R são considerados inferiores aos criados acima da embalagem de L1.
   Relação de aproximação: SF (I) <= (3/2) · OPT (I) + 2; o limite assintótico de 3/2 é apertado.

9. Algoritmo de Sleator O algoritmo de
   Sleater consiste em quatro etapas:

   1. Todos os itens com largura superior a 1/2 são embalados um sobre o outro na parte inferior da faixa. Suponha que h0 seja a altura da gaxeta resultante. Toda gaxeta subsequente ocorrerá acima de h0.

   2. Os itens restantes são ordenados por altura não crescente. Um nível de itens é compactado (em ordem de altura não crescente) da esquerda para a direita ao longo da linha de altura h0.

   3. Uma linha vertical é então desenhada no meio para cortar a tira em duas metades iguais (observe que essa linha pode cortar um item que está parcialmente empacotado na metade direita). Desenhe dois segmentos de linhas horizontais de comprimento e meio, um na metade esquerda (chamada linha de base esquerda) e outro na metade direita (chamada linha de base direita) o mais baixo possível, de modo que as duas linhas não cruzem nenhum item.

   4. Escolha a linha de base esquerda ou direita que tem uma altura mais baixa e coloque um nível de itens na metade correspondente da faixa até que o próximo item seja muito largo.

   Uma nova linha de base é formada e a Etapa (4) é repetida na linha de base inferior até que todos os itens sejam empacotados.
   Complexidade temporal: O (n · log n).
   A taxa de aproximação do algoritmo do Sleator é de 2,5, o que é pequeno.

Dê uma olhada nos problemas de embalagem . Eu acho que o seu se enquadra em 'embalagem de lixeira 2D'. Você deve aprender muito com as soluções para esse e outros problemas de embalagem.

Consulte também: Empacotando dados de imagem retangular em uma textura quadrada.

Há extensa literatura sobre esse problema. Uma boa heurística gananciosa é colocar retângulos da maior área para a menor na primeira posição disponível na parte inferior e esquerda do contêiner. Pense na gravidade puxando todos os itens para o canto inferior esquerdo. Para uma descrição deste google "Chazelle inferior esquerdo da embalagem".

Para soluções ideais, as técnicas de ponta podem empacotar mais de 20 retângulos em alguns segundos. Huang tem um algoritmo que separa o problema de encontrar a menor caixa delimitadora do problema de decidir se um conjunto de retângulos pode ou não caber em uma caixa delimitadora de tamanho específico. Você fornece ao programa um conjunto de retângulos e ele informa a menor caixa delimitadora necessária para embalá-los.

Para o seu caso, seu loop externo deve percorrer da menor caixa delimitadora possível para cima (com a largura e a altura aumentando sucessivamente por potências de duas). Para cada uma dessas caixas delimitadoras, teste para encontrar uma embalagem para seus retângulos. Você receberá várias respostas "não", até a primeira resposta "sim", que será garantida como a solução ideal.

Para o loop interno do seu algoritmo - aquele que responde "sim" ou "não" a uma caixa delimitadora de tamanho específico, eu procurava a referência Huang e apenas implementava seu algoritmo. Ele inclui muitas otimizações sobre o algoritmo básico, mas você realmente precisa apenas da carne e batatas básicas. Como você deseja lidar com rotações, em todos os pontos de ramificação durante sua pesquisa, tente as duas rotações e a recuar quando as duas rotações não resultarem em uma solução.

Estou bastante certo de que este é um problema difícil de NP ; portanto, para uma solução ideal, você teria que implementar um algoritmo de retorno que tente todas as combinações possíveis.

A boa notícia é que, devido à necessidade de empacotar retângulos 2D em um espaço 2D limitado, você pode remover muitas possibilidades desde o início, para que não seja tão ruim assim.

O que você precisa está em https://github.com/nothings/stb/blob/master/stb_rect_pack.h

amostra:

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

Uma solução geral não é trivial (a matemática fala por completo, é impossível).
Geralmente, as pessoas usam um algoritmo genético para tentar combinações possíveis, mas você pode se sair razoavelmente justificando apenas colocar a maior forma em primeiro lugar e, em seguida, tentar lugares diferentes. próximo maior e assim por diante.