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

273

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)?

Fire Lancer
fonte
6
A segunda solução não é a ideal? Não deveria ser 128 por 224?
Mantas Vidutis
"as dimensões desse espaço devem ser potências de dois" Portanto, não faz diferença, pois o que era / é porque não posso assumir que a não-potência de dois é suportada incondicionalmente pelo hardware subjacente.
Fire Lancer
2
Enfim, fez o algoritmo mais simples, no final, (tentar encaixar tudo em 32x32, se nto tente 64x32, 64x64, em seguida, 128x64, etc) :)
Fogo Lancer
Eu coloquei um tipo de solução de força bruta aqui em cima stackoverflow.com/a/47698424/1641247 #
Sean

Respostas:

67

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.

SPWorley
fonte
1
Eu estava apenas brincando com algo parecido em um pedaço de papel, agora parece bastante melhor na maioria dos casos, mesmo sem girar os retângulos ou qualquer coisa
Fogo Lancer
1
Eu o implementei e executei um monte de dados de teste, parece fazer um bom trabalho, deixando apenas alguns dados desperdiçados. Agora eu só preciso reescrever minha implementação para ser mais eficiente do que uma busca linear para cada rect através do espaço disponível verificando cada pixel é que ponto é bloqueado (contra todas as rects existentes) ...
Fogo Lancer
4
Uma solução ideal é dada em jair.org/media/3735/live-3735-6794-jair.pdf
Jim Balter
2
Eu tive dificuldade em imaginar o quão ótimo isso poderia funcionar. Então, eu o codifiquei (com uma forma quadrada) e os resultados são ótimos. Aqui está uma animação demo: imgur.com/ISjxuOR
Attila Tanyi
@ JimBalter espaço quadrado sábio ... provavelmente ... em termos de velocidade e escalabilidade? Na verdade não?
Arek Bal
86

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.

Comportamento indefinido
fonte
6
Tudo isso exige conhecer a largura do espaço.
Quantum7
1
@ Quantum7 possivelmente não é muito importante, já que o OP exige que os lados sejam potências de dois, então podemos experimentar várias dimensões com área suficiente.
Ciro Santilli escreveu
19

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.

aib
fonte
Aqui está outro bom exemplo de um algoritmo de empacotamento de retângulo otimizado: codeproject.com/Articles/210979/…
Anderson Green
Problema também mencionado em: en.wikipedia.org/wiki/… Notavelmente, isso restringe o empacotamento de lixeira a uma única lixeira de tamanho desconhecido. Gostaria de saber se ainda está NP-completo lá.
Ciro Santilli escreveu
17

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.

Eric
fonte
9

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.

Blindy
fonte
3
Você provavelmente quer dizer NP-completo.
31129 starblue
7
Bem, se o NP estiver completo, será fácil resolver, basta resolver uma instância equivalente do vendedor ambulante e pronto. Mas é trivial mostrar que, como colocado, não é, pois os problemas de NP-completos são problemas de decisão (você recebe respostas sim / não) e tem um algoritmo de verificação de tempo polinomial. A pergunta "existe um arranjo de retângulos a, b, c ... que ocupam menos área do que 256 * 128 poderia ser NP-completo.
Eclipse
2
@ Eclipse está correto. De jair.org/media/3735/live-3735-6794-jair.pdf "O problema de otimização é difícil para NP, enquanto o problema de decidir se um conjunto de retângulos pode ser empacotado em uma determinada caixa delimitadora é NP completo, através de uma redução do empacotamento de caixas (Korf, 2003). " No entanto, observe que o PO solicitou "uma maneira razoavelmente ótima" e há soluções para isso em P, para definições suficientemente amplas de "razoavelmente".
Jim Balter
Eu também suspeito de dureza NP, mas precisamos de uma referência / prova.
Ciro Santilli escreveu
2
Fio sagrado necro, Batman. Este é um problema de embalagem, e já está provado ser NP-difícil na melhor das hipóteses: en.wikipedia.org/wiki/Packing_problems
Blindy
2

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);
}
Orbitus007
fonte
1

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.

Martin Beckett
fonte