Rectángulos de embalaje para la representación compacta

Question

Estoy buscando punteros a la solución del siguiente problema: Tengo un conjunto de rectángulos, cuya altura es conocida y también las posiciones xy quiero empacarlas en la forma más compacta. Con un pequeño dibujo (donde todos los rectángulos son del mismo ancho, pero el ancho puede variar en la vida real), me gustaría, en lugar de.

-r1- 
    -r2-- 
    -r3-- 
     -r4- 
     -r5-- 

algo así como.

-r1- -r3-- 
    -r2-- -r4- 
     -r5-- 

Todas las pistas serán apreciadas. No necesariamente estoy buscando "la" mejor solución.

Answer 1

¿Algo como esto?

• Ordenar su colección de rectángulos por x-posición

• escribir un método que comprueba que rectángulos están presentes en un cierto intervalo del eje x

  Collection<Rectangle> overlaps (int startx, int endx, Collection<Rectangle> rects){ 
  ... 
  } 
  

• bucle sobre la colección de rectángulos

  Collection<Rectangle> toDraw; 
  Collection<Rectangle> drawn; 
  foreach (Rectangle r in toDraw){ 
  Collection<Rectangle> overlapping = overlaps (r.x, r.x+r.width, drawn); 
  int y = 0; 
  foreach(Rectangle overlapRect in overlapping){ 
  y += overlapRect.height; 
  } 
  drawRectangle(y, Rectangle); 
  drawn.add(r); 
  } 
  

Answer 2

Su problema es una variante más simple, pero es posible que obtenga algunos consejos sobre la heurística desarrollada para el problema del "binpacking". Se ha escrito mucho sobre esto, pero this page es un buen comienzo.

Answer 3

Ponga un juego tipo tetris en su sitio web. Genere los bloques que caen y el tamaño del área de juego según sus parámetros. Los puntos de premio a los jugadores se basan en la compacidad (menos espacio libre = más puntos) de su diseño. Haga que los visitantes de su sitio web realicen el trabajo por usted.

Answer 4

¿Los rectángulos son todos de la misma altura? Si lo son, y el problema es en qué fila colocar cada rectángulo, entonces el problema se reduce a una serie de restricciones sobre todos los pares de rectángulos (X, Y) de la forma "rectángulo X no puede estar en la misma fila que rectángulo Y "cuando el rectángulo X se superpone en la dirección x con el rectángulo Y.

Un algoritmo 'codicioso' para esto ordena los rectángulos de izquierda a derecha, luego asigna cada rectángulo a la fila más baja en la que encaja. Debido a que los rectángulos se están procesando de izquierda a derecha, solo hay que preocuparse de si el borde izquierdo del rectángulo actual se superpondrá con otros rectángulos, lo que simplifica un poco el algoritmo de detección de superposición.

No puedo probar que esto ofrezca la solución óptima, pero por otro lado tampoco puedo pensar en ningún contraejemplo. ¿Nadie?

Answer 5

Topcoder tuvo un concurso para resolver la versión 3D de este problema. El ganador discutió su enfoque here, podría ser una lectura interesante para usted.

Answer 6

Había trabajado en un problema como este antes. La imagen más intuitiva es probablemente una donde los rectángulos grandes están en la parte inferior, y los más pequeños están en la parte superior, como colocarlos en un contenedor y sacudirlos para que los más pesados ​​caigan al fondo. Entonces, para lograr esto, primero clasifique su matriz en orden de área decreciente (o ancho) - primero procesaremos los elementos grandes y construiremos la imagen.

Ahora el problema es asignar coordenadas y a un conjunto de rectángulos cuyas coordenadas x se dan, si te entiendo correctamente.

Itere sobre su matriz de rectángulos. Para cada rectángulo, inicialice la coordenada y del rectángulo a 0. Luego realice un ciclo aumentando la coordenada y de este rectángulo hasta que no se intersecte con ninguno de los rectángulos colocados previamente (debe hacer un seguimiento de los rectángulos que se han colocado previamente). Comprométete con la coordenada y que acabas de encontrar, y continúa procesando el siguiente rectángulo.