Organizar de manera esquemática objetos UI rectangulares de forma abstracta, sin huecos

Question

Dada una colección de, digamos, 50 imágenes con diversos anchos y alturas, ¿cómo se podría organizar programáticamente de una manera interesante * abstracta? (Ver imagen abajo)

• Por interesante que quiero decir, sin huecos grandes, y no fácilmente filas o columnas (espacio negativo se forma una gran cantidad de intersecciones de t) distinguibles.

Por mi caso específico, todas las imágenes tienen una dimensión conjunto max de 150 píxeles, lo que podría significar la altura o anchura es de un máximo de 150 píxeles (podría ser 150 píxeles por 450 píxeles, o 378px por 150 píxeles).

Esto parece que podría ser un desafío de programación clásico, pero me estoy encontrando el tema difícil de Google ...

EDIT: Se ha cambiado la imagen para mostrar que no hay ninguna restricción sobre cómo debe ser la disposición general (no tiene que caber dentro de un área configurada)

Answer 1

Tu problema es NP-Hard.

This thread muestra que incluso con un tipo de rectángulos nxm, es NP-difícil de encontrar si hay una solución, por lo que su problema más generalizado es, por supuesto, NP-duro, así [El único tipo de rectángulo es una caso particular de este problema]

usted podría intentar una solución backtracking si usted está después de la solución, o una aproximación heurística como genetic algorithms o hill climbing, que será más rápido optimizado - pero se suele encontrar un resultado no óptimo.

Answer 2

Si no se opone a plugin de jQuery, se puede comprobar esto - http://masonry.desandro.com/

Answer 3

he construido algo similar a esto (aunque probablemente no es la solución más sofisticada). Mi enfoque era usar un quadtree para organizar los rectángulos que había colocado en el lienzo. Entonces, básicamente, di la vuelta al punto central en espiral, tratando de colocar nuevos rectángulos y usando el quadtree para detectar colisiones. Si detecté una colisión, movería el rectángulo que estaba tratando de colocar al borde del rectángulo con el que colisionó más alejado del centro y repetiré el proceso de comprobación de colisión.

De nuevo, probablemente no es el método más sofisticado, y tiende a dejar algunas lagunas más grandes entre los rectángulos (los bordes entre ellos no son uniformes), pero a mi gusto dio buenos resultados.