¿Cómo se logra el empaquetamiento 2D bin programáticamente?

Question

Hay algunas preguntas similares en stackoverflow, pero ninguna de ellas proporciona una respuesta tangible que alguien sin una sólida comprensión de los problemas y algoritmos NP-hard pueda comprender.

¿Cómo se realiza el embalaje bidimensional de objetos rectangulares? En mi caso, estoy tratando de ensamblar varias imágenes en una sola imagen, para usar como una hoja de sprites, usando la menor cantidad de espacio. Cada imagen posiblemente tiene límites muy diferentes, pero no hay límites establecidos para el contenedor.

Esperaba que alguien con una comprensión de los algoritmos de empaquetado de bandejas pudiera explicar cómo esto se puede lograr mediante programación, en lugar de proporcionar una descripción general del método de empaquetado de la papelera.

Answer 1

I Googled "bin packing code" y esto fue mi primer éxito: http://codeincomplete.com/posts/2011/5/7/bin_packing/

He aquí un resumen: construir un árbol binario. Cada rama en el árbol contiene un sprite. Cada nodo de hoja representa el espacio disponible. Inicialmente, el árbol tiene solo el nodo raíz, que representa todo el espacio disponible. Para agregar un objeto al árbol, busque en el árbol un nodo desocupado (hoja) lo suficientemente grande como para contener el elemento. Convierte ese nodo de una hoja en una rama configurando al sprite como el ocupante del nodo y dándole al nodo dos hijos. Un niño representa el espacio restante a la derecha del sprite; el otro representa el espacio restante debajo del sprite y el primer hijo.

El artículo que he vinculado anteriormente explica esto mucho más completamente, con diagramas y código JavaScript. También explica cómo hacer crecer dinámicamente la hoja de sprites en lugar de elegir un tamaño fijo por adelantado.

Answer 2

Todo lo que necesita es aquí: https://github.com/juj/RectangleBinPack

Hay un papel y una aplicación decente C++.

Si necesita un pseudo-código aún más simple, echar un vistazo a este sitio: http://www.blackpawn.com/texts/lightmaps/

El "paquete de guillotina" se llama un envase a base de árbol de allí.