algorithm - Embalaje de rectángulos para una representación compacta

packing rectangles

Question

Estoy buscando punteros a la solución del siguiente problema: tengo un conjunto de rectángulos, cuya altura es conocida y también posiciones en x, y quiero empacarlos 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 como.

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

Todos los consejos serán apreciados. No necesariamente estoy buscando "la" mejor solución.

Answer 1

¿Los rectángulos tienen 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 el algoritmo de detección de superposición.

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

Answer 2

Pon un juego tipo tetris en tu 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 3

Su problema es una variante más simple, pero puede obtener algunos consejos sobre la heurística desarrollada para el problema del "binpacking". Se ha escrito mucho sobre esto, pero esta página es un buen comienzo.

Answer 4

Topcoder tuvo una competencia para resolver la versión 3D de este problema. El ganador discutió su enfoque aquí , podría ser una lectura interesante para ti.

Answer 5

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 desde cero.

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

Itera 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.

Answer 6

¿Algo como esto?

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

• escribe un método que verifica qué rectángulos están presentes en un cierto intervalo del eje x

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

• recorrer 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);
  }