Algoritmo

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 $X,Y,x,y$, definidos a seguir, como sendo inteiros. Definimos uma peça $L(X,Y,x,y)$ na posição padrão, onde $X\geq x$ e $Y\geq y$, como um retângulo cuja diagonal vai de $(0,0)$ a $(X,Y)$ menos o retângulo cuja diagonal vai de $(x,y)$ a $(X,Y)$ (como mostrado na Figura ). Assim todos os L's podem ser representados com apenas uma quádupla. A área de $L(X,Y,x,y)$ é dada por $XY-(X-x)(Y-y)$. Em particular, $L(X,Y,X,Y)=R(X,Y)$ é o retângulo cuja diagonal vai $(0,0)$ a $(X,Y)$. Note que $R(X,Y)$ pode ser visto com um L em que $x=X$ ou $y=Y$. Um $L(X,Y,x,y)$ que é um retângulo é dito degenerado. Um $L(X,Y,x,y)$ é dito não-degenerado se $0<x<X$ e $0<y<Y$.

Figure: Posição padrão $L(X,Y,x,y)$

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

Figure: Subdivisões $B_1, B_2, B_3, B_4$ e $B_5$ de um L em dois L's.

Figure: Subdivisões $B_6$ e $B_7$ de um retângulo em dois L's.

Dado $L=L(X,Y,x,y)$, denotamos por $P'_k(L)$, com $k\in \{1,2,3,4,5,6,7\}$, o conjunto dos pontos de todas as possíveis subdivisões $B_k$ em L. Os pontos da subdivisão $B_k$, com $k\in \{1,2,3,4,5\}$, podem ser representados apenas com uma dupla e os pontos de subdivisão $B_6$ e $B_7$, apenas com uma tripla (veja as Figuras e ). Para cada subdivisão $B_k$, com $k\in \{1,2,3,4,5,6,7\}$, existe um intervalo de valores válidos para esses pontos e, portanto, cada $P'_k(L)$ pode ser definido como:

$$P'_1(L) = \{ p_1 = (x',y') \mid 0 \leq x' \leq x, 0 \leq y' \leq y \}\hspace{1.7cm}$$

$$P'_2(L) = \{ p_2 = (x',y') \mid 0 \leq x' \leq x, y \leq y' \leq Y \}\hspace{1.6cm}$$

$$P'_3(L) = \{ p_3 = (x',y') \mid 0 \leq x' \leq x, 0 \leq y' \leq y \}\hspace{1.7cm}$$

$$P'_4(L) = \{ p_4 = (x',y') \mid x \leq x' \leq X, 0 \leq y' \leq y \}\hspace{1.6cm}$$

$$P'_5(L) = \{ p_5 = (x',y') \mid 0 \leq x' \leq x, 0 \leq y' \leq y \}\hspace{1.7cm}$$

$$P'_6(L) = \{ p_6 = (x',x'',y') \mid 0 \leq x' \leq x'' \leq X, 0 \leq y' \leq Y \}$$

$$P'_7(L) = \{ p_7 = (x',y',y'') \mid 0 \leq x' \leq X, 0 \leq y' \leq y'' \leq Y \}$$

Para cada subdivisão $B_k$, com $k\in \{1,2,3,4,5,6,7\}$, definimos duas funções $\ell _1(L,k,p_k)$ e $\ell _2(L,k,p_k)$ que fazem com que os dois novos L's gerados pela subdivisão $B_k$ fiquem na posição padrão. Essas funções são definidas como:

$$B_1: \ell _1( L,1,p_1 ) = L( x, Y-y', x' , Y-y )\hspace{2.5cm}$$

$$\ell _2( L,1,p_1 ) = L( X, y , X-x', y' )\hspace{2.3cm}$$

$$B_2: \ell _1( L,2,p_2 ) = L( x, Y-y, x-x', Y-y' )\hspace{1.8cm}$$

$$\ell _2( L,2,p_2 ) = L( X, y' , x' , y )\hspace{3.1cm}$$

$$B_3: \ell _1( L,3,p_3 ) = L( X , Y , x' , y' )\hspace{3.8cm}$$

$$\ell _2( L,3,p_3 ) = L( X-x', Y-y', x-x', y-y' )$$

$$B_4: \ell _1( L,4,p_4 ) = L( x' , Y, x , y' )\hspace{3.9cm}$$

$$\ell _2( L,4,p_4 ) = L( X-x, y, X-x', y-y' )\hspace{0.9cm}$$

$$B_5: \ell _1( L,5,p_5 ) = L( x , Y, x' , Y-y' )\hspace{3.2cm}$$

$$\ell _2( L,5,p_5 ) = L( X-x', y, X-x, y' )\hspace{1.7cm}$$

$$B_6: \ell _1( L,6,p_6 ) = L( x'' , Y, x' , Y-y' )\hspace{3.1cm}$$

$$\ell _2( L,6,p_6 ) = L( X-x', Y, X-x'', y' )\hspace{1.5cm}$$

$$B_7: \ell _1( L,7,p_7 ) = L( X, Y-y', x' , Y-y'' )\hspace{2.3cm}$$

$$\ell _2( L,7,p_7 ) = L( X, y'' , X-x', y' )\hspace{2.3cm}$$

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 $P_k(L)$ como o subconjunto de $P'_k(L)$, tal que $P_k(L)=\{p_k\in P'_k(L) \mid A(\ell _1(L,k,p_k))>0, A(\ell _2(L,k,p_k))>0\}$, onde $A(L)$ é a área de L, para $k\in \{1,2,3,4,5,6,7\}$.

Dado um L podemos definir limitantes inferiores e superiores para a quantidade de retângulos que podem ser empacotados. Um limite superior $limSup(L)$ pode ser definido como o maior inteiro que é menor que $A(L)/(lw)$. Explicitamente:

$$limSup(L) = \lfloor A(L)/(lw)\rfloor.$$

Um limite inferior $limInf(L)$ pode ser definido como o número máximo de retângulos $(l,w)$ contidos em um empacotamento homogêneo. Empacotamento homogêneo é quando os retângulos são empacotados em apenas uma orientação. Definimos:

• se L é degenerado
  
  $$limInf(L) = \max\{ \lfloor X/l \rfloor \lfloor Y/w \rfloor, \lfloor X/w \rfloor \lfloor Y/l \rfloor \},$$
  
  

• se L é não degenerado
  
  $$limInf(L) = \max\{ limInf( R(x,Y) ) + limInf( R(X-x,y) ), limInf( R(x,Y-y) ) + limInf( R(X,y) ) \}.$$
  
  

Definimos $nRet(L)$ recursivamente como:

• se $limInf(L)=limSup(L)$
  
  $$nRet(L)=limInf(L),$$
  
  

• caso contrário
  
  $$nRet(L)=\max _{1 \leq k \leq 7}\{ \max _{p_k\in P_{k(L)}}\{nRet(\ell _1(L,k,p_k))+nRet(\ell _2(L,k,p_k))\}\}.$$
  
  

A idéia básica é que se o valor de $nRet(L)=n$, então é possível empacotar n retângulos de dimensões $(l,w)$ em L. O algoritmo L consitem em, dado L, calcular a função $nRet(L)$. Para reduzir o custo do cálculo da função $nRet$, vamos reduzir o domínio dessa função.

Seja $Z^{l,w}$ a seqüência infinita $\{0=z_0<z_1<\ldots <z_p<\ldots \}$, de combinações lineares não-negativas de $l$'s e $w$'s. Definimos a grade de pontos de $(l,w)$ como o conjunto dos pontos $(z_i,z_j)$ com $z_i,z_j\in Z^{l,w}$.

Proposição 1   Um empacotamento ortogonal de $L(X,Y,x,y)$ por retângulos $(l,w)$ pode ser transformado em outro com o mesmo número de retângulos em que cada vértice de cada retângulo está num ponto da grade de $(l,w)$.

Prova Veja [26].

Com a proposição acima, todas as peças $L(X,Y,x,y)$ que aparecem no cálculo de $nRet$ podem ser trocadas por $L(z_I,z_J,z_i,z_j)$, onde $z_I\leq X\leq z_{I+1}$, $z_J\leq Y\leq z_{J+1}$, $z_i\leq x\leq z_{i+1}$ e $z_j\leq y\leq z_{j+1}$. Para simplificar a notação, denotamos $L(z_I,z_J,z_i,z_j)$ como $L(I,J,i,j)$.

Temos que ajustar a definições das funções $\ell _1(L,k,p_k)$ e $\ell _2(L,k,p_k)$, pois em $Z^{l,w}$ a diferença não é fechada. Portanto, a coordenada $z_r-z_s$ que aparece em $\ell _1(L,k,p_k)$ ou $\ell _2(L,k,p_k)$ deve ser trocada por:

$$z_{r\ominus s} = \max\{ z_h \mid z_h \leq z_r-z_s \}$$

Trocamos também algumas notações:

• $L=L(X,Y,x,y)$ por $L=L(I,J,i,j)$,
• $p_k=(x',y')$ por $p_k=(i',j'),\; k = 1,2,3,4,5$,
• $p_6=(x',x'',y')$ por $p_6=(i',i'',j')$,
• $p_7=(x',y',y'')$ por $p_7=(i',j',j'')$.

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 $L(I,J,i,j)$ degenerado não é explicitamente um retângulo, se ($I=i$ e $j<J$) ou ($J=j$ e $i<I$).

Durante a execução do algoritmo, podem aparecer quáduplas $(I,J,i,j)$ 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:

1. se $i=0$ então $(I,J,i,j)^N = (I,j,I,j)$,
2. se $j=0$ então $(I,J,i,j)^N = (i,J,i,J)$,
3. se $I=i$ ou $J=j$ então $(I,J,i,j)^N = (I,J,I,J)$,
4. se $I=i$ e $J=j$ e $I<J$ então $(I,J,i,j)^N = (J,I,j,i)$,
5. se $0<i<I$ e $0<j<J$ e $I<J$ então $(I,J,i,j)^N = (J,I,j,i)$,
6. se $0<i<I$ e $0<j<J$ e $I=J$ e $i<j$ então $(I,J,i,j)^N = (J,I,j,i)$,
7. caso contrário $(I,J,i,j)^N = (I,J,i,j)$.

Os itens $(\ref{item:deg1})-(\ref{item:deg3})$ são para eliminar L's degenerados que não são explicitamente retângulos. Os itens $(\ref{item:deitaR})-(\ref{item:deitaLQ})$ são para deitar as peças. Para ser mais claro, o item $(\ref{item:deitaR})$ serve para deitar retângulos e os itens $(\ref{item:deitaL})$ e $(\ref{item:deitaLQ})$ são para deitar L's.

A seguir definimos as funções $\ell _1^N(L,k,p_k)$ e $\ell _2^N(L,k,p_k)$ para que a partição de um retângulo ou de um L resulte em retângulos ou L's normalizados:

$$B_1: \ell _1^N( L,1,p_1 ) = L(( i, J\ominus j', i', J\ominus j )^N)\hspace{2.2cm}$$

$$\ell _2^N( L,1,p_1 ) = L(( I, j, I\ominus i', j')^N)\hspace{2.1cm}$$

$$B_2: \ell _1^N( L,2,p_2 ) = L(( i, J\ominus j, i\ominus i', J\ominus j' )^N)\hspace{1.6cm}$$

$$\ell _2^N( L,2,p_2 ) = L(( I, j', i', j )^N)\hspace{2.8cm}$$

$$B_3: \ell _1^N( L,3,p_3 ) = L(( I, J, i', j' )^N)\hspace{3.5cm}$$

$$\ell _2^N( L,3,p_3 ) = L(( I\ominus i', J\ominus j', i\ominus i', j\ominus j' )^N)$$

$$B_4: \ell _1^N( L,4,p_4 ) = L(( i', J, i, j' )^N)\hspace{3.6cm}$$

$$\ell _2^N( L,4,p_4 ) = L(( I\ominus i, j, I\ominus i', j\ominus j' )^N)\hspace{0.9cm}$$

$$B_5: \ell _1^N( L,5,p_5 ) = L(( i, J, i' , J\ominus j' )^N)\hspace{2.9cm}$$

$$\ell _2^N( L,5,p_5 ) = L(( I\ominus i', j, I\ominus i, j' )^N)\hspace{1.6cm}$$

$$B_6: \ell _1^N( L,6,p_6 ) = L(( i'', J, i', J\ominus j' )^N)\hspace{2.7cm}$$

$$\ell _2^N( L,6,p_6 ) = L(( I\ominus i', J, I\ominus i'', j')^N)\hspace{1.3cm}$$

$$B_7: \ell _1^N( L,7,p_7 ) = L(( I, J\ominus j', i', J\ominus j'' )^N)\hspace{2.0cm}$$

$$\ell _2^N( L,7,p_7 ) = L(( I, j'', I\ominus i', j' )^N)\hspace{2.0cm}$$

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 $limInf(L)=limSup(L)$ 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 $B_k$ (isto é, $\ell _1(L,k,p_k)$ e $\ell _2(L,k,p_k)$) para todos os pontos em $P_k$.

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 $R(x_1, y_1, x_2, y_2)$, onde $(x_1, y_1)$ é o vértice inferior esquerdo do retângulo e $(x_2, y_2)$ é 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.

Figure: Representação de um retângulo

Dado um $L(X,Y,x,y)$ na posição padrão e normalizado, queremos descobrir como essa peça estava antes. Denotamos por $T_k$, com $k\in \{1,...,8\}$, 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 ).

Figure: Posições que uma peça poderia estar.

Cada uma dessas tranformações $T_k$, com $k\in \{1,...,8\}$ é definida como:

$$T_1(x_0,y_0) = (x_0, Y-y_0)\hspace{0.8cm}$$

$$T_2(x_0,y_0) = (X-x_0, y_0)\hspace{0.8cm}$$

$$T_3(x_0,y_0) = (X-x_0, Y-y_0)$$

$$T_4(x_0,y_0) = (x_0, y_0)\hspace{1.6cm}$$

$$T_5(x_0,y_0) = (y_0, X-x_0)\hspace{0.8cm}$$

$$T_6(x_0,y_0) = (Y-y_0, x_0)\hspace{0.8cm}$$

$$T_7(x_0,y_0) = (Y-y_0, X-x_0)$$

$$T_8(x_0,y_0) = (y_0, x_0)\hspace{1.6cm}$$

Quando uma peça é dividida, ela gera duas novas peças, $L_1$ e $L_2$. 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 $B_1$, a peça $L_1$, que está na posição padrão e normalizada, pode usar a transformação $T_1$ ou $T_5$ (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.

Table: Tranformações para cada subdivisão.

Subdivisão	$L_1$	$L_2$
$B_1$	$T_1$ ou $T_5$	$T_2$ ou $T_6$
$B_2$	$T_3$ ou $T_7$	$T_4$ ou $T_8$
$B_3$	$T_4$	$T_8$
$B_4$	$T_4$ ou $T_8$	$T_3$ ou $T_7$
$B_5$	$T_1$ ou $T_5$	$T_2$ ou $T_6$
$B_6$	$T_1$ ou $T_5$	$T_2$ ou $T_6$
$B_7$	$T_1$ ou $T_5$	$T_2$ ou $T_6$

Em particular, se $L(X,Y,X,Y)=R(X,Y)$ então usamos as tranformações $T_4$ ou $T_8$.

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.