Algoritmo para el posicionamiento de rectángulos de varios tamaños en un rectángulo más grande

Question

Estoy trabajando en la herramienta de fusión de texturas más pequeños en uno más grande para el uso en aplicaciones de Android.

Tengo $n$ rectángulos de determinado tamaño $(w_k, h_k)$, donde $k=1,\ldots,n$ y necesito para posicionarlos dentro de rectángulo principal de tamaño $2^l \times 2^m$, donde $l, m \leq 9$ tan ninguna superposición ocurre y $2^l \times 2^m$ tienen un mínimo valor posible. El resultado debe ser $(x_k, y_k)$, una posición de cada uno de los rectángulos base de $n$ o la información que esa posición es imposible.

Answer 1

Supongo que este debe de ser exactamente lo que usted necesita. Básicamente se trata de una aplicación del enfoque presentado en este documento por Richard E. Korf. Para citar la introducción:

Dado un conjunto de rectángulos con fijo orientaciones, queremos encontrar un adjuntando rectángulo de área mínima que contiene todos ellos, sin solapamiento. Muchos sencilla la programación de tareas inspirado por este tipo NP-completo el problema. Utilizamos un momento branch-and-bound algoritmo para resolver el problema de forma óptima.

Answer 2

Parece que tenemos un número (voy a utilizar $k$) de idéntica $w \times h$ rectángulos para caber dentro de una más grande $2^n \times 2^m$ rectángulos, y con restricciones a en $n$$m$.

Por $2^n$, podemos encajar $\lfloor 2^n / w \rfloor$ rectángulos horizontalmente proporcionado $w \le 2^n$. Así que necesitamos al menos $ \lceil k / \lfloor 2^n / w \rfloor \rceil$ filas de rectángulos y para una altura vertical de al menos $ h \lceil k / \lfloor 2^n / w \rfloor \rceil$; si este es menor o igual a$2^m$, entonces hay una solución y el valor mínimo de $m$$ \lceil \log_2 \left( h \lceil k / \lfloor 2^n / w \rfloor \rceil \right) \rceil$. El área de la maestría rectángulo es, a continuación,$2^{n+ \lceil \log_2 \left( h \lceil k / \lfloor 2^n / w \rfloor \rceil \right) \rceil}$. Es probablemente vale la pena probar esto de los diez(?) los posibles valores de $n$ a ver en que se produce la maestra mínima rectángulo.

Como para las coordenadas (suponiendo que estos son una de las esquinas y $(0,0)$ es una posibilidad), esta será una cuestión de estilo. Una forma sería la de utilizar $(iw,jh)$ para nonengative enteros $i$ $j$ mientras $(i+1)w -1 \le 2^n$$(j+1)h -1 \le 2^m$.