image - img - src html
Embalaje de datos de imagen rectangulares en una textura cuadrada (4)
Tengo N elementos de datos de imágenes en 2D que serán rectangulares y quiero empacarlos en una sola potencia de 2 texturas de la manera más eficiente posible.
Una simple implementación no eficiente e ingenua de un algoritmo para empaquetar estas recetas sería fácil de mejorar, pero estoy seguro de que la gente ha creado algoritmos para hacerlo de la manera más eficiente posible. He encontrado varias referencias al empaque de lightmap que es similar a lo que estoy buscando, pero los algoritmos para lightmapping tienden a tener en cuenta imágenes no rectangulares que realmente complican las cosas más de lo que necesito que sean.
¿Alguien tiene pistas? ¿Nombres de algoritmos o autores de papel que debería buscar en Google?
Gracias.
Algoritmo de empaquetado muy bueno y simple se puede encontrar aquí: http://www.blackpawn.com/texts/lightmaps/
Su implementación solo requiere 200 líneas de C ++, no más (supongo que ya tiene las rutinas de manipulación de mapas de bits).
Para la teoría detrás hay una introducción de Jukka Jylänki (busque las "Mil maneras de empacar el contenedor").
El autor del artículo proporciona la biblioteca de C ++ que está realmente hinchada desde mi punto de vista, pero por otro lado tiene muchas opciones y está muy bien documentada.
He necesitado hacer esto mismo que describes.
Este es el código Python que utilicé, es una receta en el Python Cookbook:
Receta 442299: empaqueta múltiples imágenes de diferentes tamaños en una sola imagen
Su problema en 1D se llama Bin Packing. Tal vez ese sea un buen comienzo para su búsqueda.
Tenga en cuenta que el problema que desea resolver es realmente difícil (es NP-difícil). Por lo tanto, no debe buscar la solución óptima, sino algún algoritmo heurístico inteligente.
Creo que la programación dinámica de abajo hacia arriba es posible para el empaque de bandejas 1D, pero no para el caso 2D.
Podría pensar en simplificar su problema resolviendo solo el problema 1D, haciendo restricciones como cortar las texturas en varias divisiones (de tamaño variable) en 1 dimensión.
Otra posibilidad es ejecutar una optimización meta-heurística, como Algoritmos Evolutivos o Optimización de Enjambre de Partículas.
Tuve un problema similar pero estaba empacando cuadrados. Pruebe esto: http://www.mrashid.info/blog/stacking-squares-problem.php
El código de C ++ no es muy elegante, pero al menos se obtiene la idea básica de cómo abordar este problema.