Modelos Contínuos

Antes de mostrar os modelos, vamos definir o que são sentinelas, pois em alguns métodos são necessários o uso deles.

Um conjunto de sentinelas é um conjunto mínimo de pontos de um retângulo, tal que se dois retângulos $R_1$ e $R_2$ se intersectam, então ocorre pelo menos uma das seguintes situações:

• pelo menos um sentinela do retângulo $R_1$ está no interior do retângulo $R_2$,
• pelo menos um sentinela do retângulo $R_2$ está no interior do retângulo $R_1$.

A Figura é um exemplo de um conjunto de sentinelas de um retângulo.

Figure: Conjunto de sentinelas de um retângulo

Agora que já definimos o que são sentinelas, vamos mostrar os modelos contínuos.

Método do Vetor

Esse método usa sentinelas. Para verificar se ocorre intersecção entre dois retângulos $R_1$ e $R_2$, devemos verificar para todos os sentinelas do retângulo $R_1$, se existe ao menos um deles no interior do retângulo $R_2$ e verificar para todos os sentinelas do retângulo $R_2$, se existe ao menos um deles no interior do retângulo $R_1$.

Para aplicar o método devemos, antes de verificar se um sentinela de um retângulo está no interior do outro retângulo, levar o retângulo para a origem. Seja $(r_x, r_y)$ a coordenada do vértice inferior esquerdo do retângulo e $(s_x, s_y)$ a coordenada do sentinela. Para levar o retângulo para a origem é só subtrair sua coordenada pelo vetor $(r_x, r_y)$. Também devemos subtrair a coordenada do sentinela por esse vetor. Note que a coordenada do retângulo, depois de subtraído pelo vetor, será sempre $(0,0)$ (origem), portanto não é necessário subtrair o vetor da coordenada do retângulo, apenas será necessária subtrair o vetor da coordenada do sentinela, assim a nova coordenada do sentinela será $(s_x-r_x,s_y-r_y)$.

Figure: Método do vetor

Após feito isso, podemos considerar que o retângulo, de dimensão $(l,w)$, tem dois vetores $u$ e $v$, onde $u=(d_x,0)$ e $v=(0,d_y)$, e se o retângulo $R_1$ está deitado então $d_x=l$ e $d_y=w$, e se o retângulo $R_1$ está em pé então $d_x=w$ e $d_y=l$ (como mostra a Figura ). Assim a nova coordenada $p=(p_x, p_y)$ do sentinela pode ser representada através da seguinte equação linear:

$$p = \alpha \times u + \beta \times v,$$

onde $\alpha , \beta \in I\!\!R$.

Se $0 < \alpha < 1$ e $0 < \beta < 1$ então o sentinela está no interior do retângulo. Portanto os retângulos se intersectam.

Resolvendo a equação temos que:

$$\alpha = \frac{p_x}{d_x} = \frac{s_x-r_x}{d_x}$$

$$\beta = \frac{p_y}{d_y} = \frac{s_y-r_y}{d_y}$$

A função contínua e diferenciável que mede a superposição entre os retângulos e seu gradiente para esse método são:

$$\begin{array}{rcll} f(r) & = &\displaystyle\sum_{i=1}^{nRet... ...(0, 1 - \frac{s_{y}^{jk} - r_{y}^{i}}{d_{y}^{i}})^2 \end{array}$$

$$\begin{eqnarray*} \nabla f(r) & = & \left( \begin{array}{c} \displaystyle\sum... ...-\alpha)^2}{d_y^i}\\ \vdots\\ \vdots\\ \end{array} \right) \end{eqnarray*}$$

onde $r = (r_x^1, r_y^1, r_x^2, r_y^2, \ldots , r_x^n, r_y^n)$ e $r_x^i$ é a coordenada inferior esquerda $x$ do retângulo $i$ e $r_y^i$ é a coordenada inferior esquerda $y$ do retângulo $i$. $s_{x}^{jk}$ é a coordenada $x$ do sentinela $k$ do retângulo $j$ e $s_{y}^{jk}$ é a coordenada $y$ do sentinela $k$ do retângulo $j$. E $nRet$ é o número de retângulos e $nSent$ é o número de sentinelas.

Essa função vale zero se não existe superposição entre os retângulos e qualquer valor positivo se existe superposição entre os retângulos.

Método das Restrições

Esse método usa sentinelas. Para verificar se ocorre intersecção entre dois retângulos $R_1$ e $R_2$, devemos verificar para todos os sentinelas do retângulo $R_1$, se existe ao menos um deles no interior do retângulo $R_2$ e verificar para todos os sentinelas do retângulo $R_2$, se existe ao menos um deles no interior do retângulo $R_1$.

Figure: Método das restrições

Podemos considerar que os lados do retângulo $R_1$, de dimensão $(l,w)$, são quatro restrições lineares (como mostra a Figura ). Sejam $(s_x, s_y)$ a coordenada de um sentinela do retângulo $R_2$ e $d_x$ e $d_y$ as dimensões do retângulo $R_1$, onde se o retângulo está deitado então $d_x=l$ e $d_y=w$, e se o retângulo está em pé então $d_x=w$ e $d_y=l$.

Assim se:

$$r_x < s_x < r_x + d_x$$

$$e$$

$$r_y < s_y < r_y + d_y$$

então o sentinela está no interior do retângulo. Portanto os retângulos se intersectam.

A função contínua e diferenciável que mede a superposição entre os retângulos e seu gradiente para esse método são:

$$f(r)=\displaystyle\sum_{i=1}^{nRet} \displaystyle\sum_{j=1, ... ...i} )^2 \times \max ( 0, r_{y}^{i} + d_{y}^{i} - s_{y}^{jk} )^2$$

$$\nabla f(r) = \left( \begin{array}{cl} \displaystyle\sum_{... ... - s_{x}^{jk})^2)\\ \vdots\\ \vdots\\ \end{array}\right)$$

onde $r = (r_x^1, r_y^1, r_x^2, r_y^2, \ldots , r_x^n, r_y^n)$ e $r_x^i$ é a coordenada inferior esquerda $x$ do retângulo $i$ e $r_y^i$ é a coordenada inferior esquerda $y$ do retângulo $i$. $s_{x}^{jk}$ é a coordenada $x$ do sentinela $k$ do retângulo $j$ e $s_{y}^{jk}$ é a coordenada $y$ do sentinela $k$ do retângulo $j$. E $nRet$ é o número de retângulos e $nSent$ é o número de sentinelas.

Essa função vale zero se não existe superposição entre os retângulos e qualquer valor positivo se existe superposição entre os retângulos.

Método da Distância do Centros

Esse método NÃO usa sentinelas.

Considere dois retângulos $R_1$ e $R_2$ de dimensões $(l,w)$, onde as coordenadas do centro do retângulo são $(r_x^1, r_y^1)$ e $(r_x^2, r_y^2)$ respectivamente. Sejam $d_x^1$ e $d_y^1$ as dimensões do retângulo $R_1$ e $d_x^2$ e $d_y^2$ as dimensões do retângulo $R_2$, onde se o retângulo está deitado então $d_x=l$ e $d_y=w$, e se o retângulo está em pé então $d_x=w$ e $d_y=l$ (Veja Figura ).

Figure: Método da distância dos centros

Assim se:

$$\vert r_x^1 - r_x^2 \vert < d_x^1 + d_x^2$$

$$e$$

$$\vert r_y^1 - r_y^2 \vert < d_y^1 + d_y^2$$

então os retângulos se intersectam. Caso contrário, os retângulos não se intersectam.

A função contínua e diferenciável que mede a superposição entre os retângulos e seu gradiente para esse método são:

$$f(r)=\displaystyle\sum_{i=1}^{nRet} \displaystyle\sum_{j=i+1... ...\frac{d_y^i}{2} + \frac{d_y^j}{2} )^2 - ( r_y^i - r_y^j )^2 )^2$$

$$\nabla f(r) = \left( \begin{array}{c} \displaystyle\sum_{i=... ...2) (r_y^i-r_y^j)\\ \vdots\\ \vdots\\ \end{array} \right)$$

onde $r = (r_x^1, r_y^1, r_x^2, r_y^2, \ldots , r_x^n, r_y^n)$ e $r_x^i$ é a coordenada $x$ do centro do retângulo $i$ e $r_y^i$ é a coordenada $y$ do dentro do retângulo $i$. E $nRet$ é o número de retângulos.

Essa função vale zero se não existe superposição entre os retângulos e qualquer valor positivo se existe superposição entre os retângulos.

Método da Circunferência

Esse método serve para gerar uma configuração inicial dos retângulos para os outros métodos. Pegamos algumas circunferências que cobre quase todo o retângulo, como mostra a Figura . Esse método é citado em [7] para o empacotamento de cilindros.

Figure: O retângulo coberto parciamente por circunferêcias para gerar configurações iniciais.

Para gerar essa configuração inicial, devemos verificar para todas as circunferências de um retângulo se não existe intersecção com as outras circunferências dos outros retângulos.

Considere duas circunferências $C_1$ e $C_2$, onde as coordenadas do centro são $(c_x^1, c_y^1)$ e $(r_x^2, r_y^2)$ e os raios são $R^1$ e $R^2$, respectivamente. (Veja Figura )

Figure: Método da circunferência

Assim se:

$$( r_x^1 - r_x^2 )^2 + ( r_y^1 - r_y^2 )^2 < (R^1 + R^2)^2$$

então os retângulos se intesectam.

A função contínua e diferenciável que mede a superposição entre os retângulos e seu gradiente para esse método são:

$$f(r)=\displaystyle\sum_{i=1}^{nRet} \displaystyle\sum_{j=1}^... ...2 - ( c_x^{ij} - c_x^{km} )^2 - ( c_y^{ij} - c_y^{km} )^2 )^2$$

$$\nabla f(r) = \left( \begin{array}{c} \displaystyle\sum_{i=... ...^{ij} - c_y^{km})\\ \vdots\\ \vdots\\ \end{array} \right)$$

onde $r = (r_x^1, r_y^1, r_x^2, r_y^2, \ldots , r_x^n, r_y^n)$ e $r_x^i$ é a coordenada $x$ do centro do retângulo $i$ e $r_y^i$ é a coordenada $y$ do centro do retângulo $i$. $c_{x}^{ij}$ é a coordenada $x$ do centro da circunferência $j$ do retângulo $i$ e $c_{y}^{km}$ é a coordenada $y$ do centro da circunferência $m$ do retângulo $k$. $R^{ij}$ é o raio da circunferência $j$ do retângulo $i$ e $R^{km}$ é o raio da circunferência $m$ do retângulo $k$. E $nRet$ é o número de retângulos e $nCir$ é o número de circunferências que cobrem o retângulo.

Essa função vale zero se não existe superposição entre as circunferências dos retângulos e qualquer valor positivo se existe superposição entre as circunferências e portanto os retângulos se intersectam.