Colocación de formas 2D en un rectángulo de manera eficiente. ¿Cómo abordarlo?

Question

He estado buscando a lo largo y ancho de los siete internets, y han sido en vano. Lo más parecido a lo que necesito parece ser The cutting stock problem, solo en 2D (lo cual es decepcionante ya que Wikipedia no proporciona ninguna instrucción sobre cómo resolverlo). Otro problema similar sería UV unwrapping. Hay soluciones allí, pero solo aquellas que obtiene de complementos en varios software 3D.

Cortando la charla larga, lo que quiero es esto: dado un rectángulo de ancho y altura conocidos, tengo que averiguar cuántas formas (polígonos) de tamaños conocidos (que pueden rotarse a voluntad) puedo encajar dentro de ese rectángulo.

Por ejemplo, podría elegir una pieza en forma de T y en el mismo rectángulo pude empacar tanto de una manera eficiente, lo que resulta en 4 formas por rectángulo

así como embaldosado ellos basado en sus cuadros delimitadores, caso en el que sólo pude encajar 3

Pero, por supuesto, esto es sólo un ejemplo ... y no creo que sería mucho más útil para resolver este parti caso cular. Los únicos enfoques en los que puedo pensar en este momento son retroceder en su complejidad o resolver solo casos particulares de este problema. Entonces ... alguna idea?

Answer 1

¿Alguien listo para un juego de Tetris (un subconjunto de su problema)?

Esto se conoce como packing problem. Sin saber a qué tipo de formas te enfrentarás con anticipación, puede ser muy difícil, si no imposible, encontrar un algoritmo que te brinde la mejor respuesta. Lo más probable es que, a menos que sus polígonos sean polígonos "agradables" (círculos, cuadrados, triángulos equiláteros, etc.), probablemente tendrá que conformarse con una heurística que le proporcione la mejor solución aproximada la mayor parte del tiempo.

Una heurística general (aunque lejos de ser óptima dependiendo de la forma del polígono de entrada) sería simplificar el problema dibujando un rectángulo alrededor del polígono para que el rectángulo sea lo suficientemente grande como para cubrir el polígono. (A modo de ejemplo, en el siguiente diagrama se dibuja un rectángulo rojo alrededor de un polígono azul.)

Una vez hecho esto, entonces podemos tomar ese rectángulo y tratar de adaptarse a la mayor cantidad de ese rectángulo en el rectángulo grande como sea posible. Esto simplifica el problema en un problema de empaquetamiento rectangular que es más fácil de resolver y envuelve su cabeza. Un ejemplo de un algoritmo para esto es en el siguiente enlace:

An Effective Recursive Partitioning Approach for the Packing of Identical Rectangles in a Rectangle.

Ahora, obviamente, esta heurística no es óptima cuando el polígono en cuestión no está cerca de ser de la misma forma que un rectángulo, pero proporciona una base mínima para trabajar, especialmente si no tiene mucho conocimiento de qué su polígono se verá como (o hay una gran variación en cómo se verá el polígono).Utilizando este algoritmo, se llenaría un gran rectángulo de este modo:

aquí es la misma imagen sin los rectángulos intermedios:

Para el caso de éstos en forma de T polígonos, la heurística no es lo mejor que podría ser (de hecho, puede ser casi el peor de los escenarios para esta aproximación propuesta), pero funcionaría muy bien para otros tipos de polígonos.

Answer 2

considere lo que dijo la otra respuesta colocando las t en un cuadrado, pero en lugar de simplemente dejarlo como un cuadrado, configure las formas en una lista. A continuación, utilice True y False para completar la lista anidada como la forma, es decir [[True, True, True], [False, True, False]] para su forma de T. Luego usa una función para colocar las formas en la grilla. Para optimizar los resultados, cree un rastreador que prestará atención a la cantidad de falsos en una nueva forma que se superponen con trues que ya están en la grilla de formas anteriores. La función colocará la forma en el lugar con más solapamientos. Tendrá que haber modificaciones para crear optimizaciones cada vez más altas, pero esa es la premisa general que está buscando.