algorithm - problem - ¿Cómo se logra el empaquetamiento 2D bin programáticamente?
bin packing java (2)
Hay algunas preguntas similares en stackoverflow, pero ninguna de ellas proporciona una respuesta tangible que alguien sin una sólida comprensión de los algoritmos y los problemas de NP-NP puedan comprender.
¿Cómo se puede realizar el empaque de contenedores 2D 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 en el contenedor.
Todo lo que necesita está aquí: https://github.com/juj/RectangleBinPack
Hay un documento y una implementación decente de C ++.
Si necesita un pseudocódigo aún más simple, eche un vistazo a este sitio: http://www.blackpawn.com/texts/lightmaps/
El "paquete de guillotina" se llama embalaje de árbol allí.
Busqué en Google el "código de embalaje del contenedor" y este fue mi primer éxito: http://codeincomplete.com/posts/2011/5/7/bin_packing/
Aquí hay 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.