A idéia central do algoritmo é particionar recursivamente um retângulo ou um L em duas peças, cada uma podendo ser de novo um retângulo ou um L.
Restringimos os parâmetros , definidos a seguir, como sendo inteiros. Definimos uma peça na posição padrão, onde e , como um retângulo cuja diagonal vai de a menos o retângulo cuja diagonal vai de a (como mostrado na Figura ). Assim todos os L's podem ser representados com apenas uma quádupla. A área de é dada por . Em particular, é o retângulo cuja diagonal vai a . Note que pode ser visto com um L em que ou . Um que é um retângulo é dito degenerado. Um é dito não-degenerado se e .
Existem cinco distintos modos de subdividir um L não degenerado em dois L's de área menor (como mostrado na Figura ) e existem dois modos distintos de subdividir um L degenerado (retângulo) em dois L's de área menor (como mostrado na Figura ).
Dado , denotamos por , com , o conjunto dos pontos de todas as possíveis subdivisões em L. Os pontos da subdivisão , com , podem ser representados apenas com uma dupla e os pontos de subdivisão e , apenas com uma tripla (veja as Figuras e ). Para cada subdivisão , com , existe um intervalo de valores válidos para esses pontos e, portanto, cada pode ser definido como:
Para cada subdivisão , com , definimos duas funções e que fazem com que os dois novos L's gerados pela subdivisão fiquem na posição padrão. Essas funções são definidas como:
Quando uma peça é dividida em duas menores, para que a divisão seja uma divisão de fato, as duas peças menores deve ter área maior que 0. Portanto, podemos descartar as subdivisões em que uma das peças é nula. Definimos então como o subconjunto de , tal que , onde é a área de L, para .
Dado um L podemos definir limitantes inferiores e superiores para a quantidade de retângulos que podem ser empacotados. Um limite superior pode ser definido como o maior inteiro que é menor que . Explicitamente:
Um limite inferior pode ser definido como o número máximo de retângulos contidos em um empacotamento homogêneo. Empacotamento homogêneo é quando os retângulos são empacotados em apenas uma orientação. Definimos:
Definimos recursivamente como:
A idéia básica é que se o valor de , então é possível empacotar n retângulos de dimensões em L. O algoritmo L consitem em, dado L, calcular a função . Para reduzir o custo do cálculo da função , vamos reduzir o domínio dessa função.
Seja a seqüência infinita , de combinações lineares não-negativas de 's e 's. Definimos a grade de pontos de como o conjunto dos pontos com .
Prova Veja [26].
Com a proposição acima, todas as peças que aparecem no cálculo de podem ser trocadas por , onde , , e . Para simplificar a notação, denotamos como .
Temos que ajustar a definições das funções
e
, pois em a diferença não é fechada.
Portanto, a coordenada que aparece em
ou
deve ser trocada por:
Trocamos também algumas notações:
Também, podemos diminuir o número de peças a serem consideradas através das eliminações de peças simétricas e de L's degenerados que não são explicitamente retângulos. Duas peças são simétricas, se elas são iguais através de rotações ou reflexões. Um degenerado não é explicitamente um retângulo, se ( e ) ou ( e ).
Durante a execução do algoritmo, podem aparecer quáduplas que não estão normalizadas. Normalizar significa eliminar peças simétricas (usando apenas peças ``deitadas'') e eliminar L's degenerados que não são explicitamente retângulos. Essas quáduplas são normalizadas para:
Os itens são para eliminar L's degenerados que não são explicitamente retângulos. Os itens são para deitar as peças. Para ser mais claro, o item serve para deitar retângulos e os itens e são para deitar L's.
A seguir definimos as funções e para que a partição de um retângulo ou de um L resulte em retângulos ou L's normalizados:
O AlgoritmoL é estruturalmente simples. Ele usa uma função indicadora solucao que indica qual tipo de solução foi usado para resolver cada subproblema (indica se foi resolvido com empacotamento homogêneo ou com uma das subdivisões - B1,...,B7). Essa função é inicializada como ``não tendo solução''. Assim que os valores corretos de nRet para cada subproblema são encontrados, solucao indica qual tipo de solução foi usado. ptoDiv guarda o ponto de subdivisão da solução usada. Se o tipo de solução para uma peça é o empacotamento homogêneo, então ptoDiv fica indefinido para ela.
A seguir descrevemos a função AlgoritmoL.
O AlgoritmoL chama a função recursiva Resolve. Para cada L, se o valor de solucao para essa peça L é o empacotamento homogêneo, que é fácil de calcular e não precisa mais ser subdividida. O valor de ptoDiv para esse L fica indefinido. Caso contrário, Resolve examina recursivamente cada subdivisão (isto é, e ) para todos os pontos em .
A seguir descrevemos a função recursiva Resolve.
Depois de encontrar a melhor solução para o L, o AlgoritmoL chama a função recursiva DesenhaSolucao para desenhar a solução do problema. Desenhar significa descobrir as coordenadas dos retângulos em relação ao retângulo maior.
A função DesenhaSolucao é recursiva. Se o tipo de solução é o empacotamento homogêneo, então são desenhados os retângulos. Caso contrário, DesenhaSolucao divide a peça, usando subdivisão indicada em solucao, e chama recursivamente para cada uma das novas peças geradas.
No final da função Resolve, a solução para o problema não está de uma forma muito amigável. Todas as peças estão na posição padrão e normalizadas. Portanto, as coordenadas dos retângulos menores, que estão dentro da peça, estarão em relação a essa peça e não ao retângulo maior. A função recursiva DesenhaSolucao verifica qual solução foi usada e coloca as coordenadas dos retângulos em relação ao retângulo maior. No final dessa função, todos as coordenadas dos retângulos estarão em relação ao retângulo maior.
Seja , onde é o vértice inferior esquerdo do retângulo e é o vértice superior direito do retângulo (como mostrado na Figura ). Para representar um retângulo é necessário de apenas uma quádupla. Com essa quádupla é possível descobrir as coordenadas dos quatro vértices do retângulo.
Dado um na posição padrão e normalizado, queremos descobrir como essa peça estava antes. Denotamos por , com , as transformações que são necessárias para deixar essa peça como estava antes de ser colocada na posição padrão e de ser normalizada. Antes, essa peça L poderia estar em oito posições (como mostrado na Figura ).
Cada uma dessas tranformações , com é definida como:
Quando uma peça é dividida, ela gera duas novas peças, e . Para cada peça gerada de cada subdivisão, pode ser possível usar duas transformações, mas apenas uma será usada. Na Tabela são mostradas as tranformações possíveis para cada um. Por exemplo, usando a subdivisão , a peça , que está na posição padrão e normalizada, pode usar a transformação ou (mas usará apenas uma delas) para voltar à posição que estava antes. Para descobrir qual das duas transformações usar, devemos verificar a largura e a altura de cada peça depois de colocá-las na posição padrão, sem normalizá-las, eliminado apenas os L's degenerados que não são explicitamente retângulos.
Em particular, se então usamos as tranformações ou .
Depois dessa transformação precisamos transladar a peça para que fique na sua posição correta.
A seguir descrevemos a função recursiva DesenhaSolucao.