Me preguntaba si alguien sabe de algún algoritmo adecuado para encajar N número de rectángulos de tamaño desconocido en el rectángulo que contenga más pequeño posible.Encajando rectángulos de manera óptima
Por óptimo quiero decir con la reducción de la cantidad de espacio en blanco que queda en el rectángulo que contiene resultante.
Me gustaría usar esto para generar sprites css a partir de una serie de imágenes. respuesta
Muchas gracias,
Ian
A través packing images into square texture y Simon 's llegué a este enlace http://code.activestate.com/recipes/442299/
no el registro de la receta, pero parece que para permitir el uso de contenedores no cuadrados .
Creo que lo que describes es una variante del problema del "embalaje bidimensional". La única diferencia es que tienes los artículos y estás tratando de encontrar el rectángulo más pequeño.
This artículo de la encuesta es un buen comienzo.
Es un enlace inactivo ahora. –
La única manera de garantizar y una solución óptima es aplicar la fuerza bruta. Esto rápidamente se vuelve inmanejable para las computadoras personales cuando tiene varios rectángulos y permite la posibilidad de rotación.
Wikipedia tiene un buen artículo sobre los problemas de acumulación http://en.wikipedia.org/wiki/Packing_problem
Aquí es una buena descripción de un algoritmo rápido de embalaje - http://www.codeproject.com/KB/web-image/rectanglepacker.aspx
¿Por qué la forma que contiene también tiene que ser cuadrado? ¿Por qué no puede ser rectangular pero no cuadrado? –
Buen punto. Quise decir rectángulo. Voy a editar – madcapnmckay
http://www.google.com/search?q=rectangle+packing+algorithm – Dan