Prostokąty pakowania dla reprezentacji kompaktowej

Question

Poszukuję wskaźników do rozwiązania następującego problemu: Mam zestaw prostokątów, których wysokość jest znana, a także pozycje x, i chcę je spakować w bardziej zwartej formie. Z małym rysunkiem (gdzie wszystkie prostokąty mają tę samą szerokość, ale ich szerokość może różnić się w rzeczywistości), chciałbym zamiast tego.

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

coś jak.

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

Wszystkie wskazówki zostaną docenione. Niekoniecznie szukam "najlepszego" rozwiązania.

Answer 1

Coś takiego?

• Sortuj Twój zbiór prostokątów X-pozycji

• napisać metodę, która sprawdza, które prostokąty są obecne w pewnym odstępie osi x

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

• pętla nad kolekcją prostokąty

  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

Twój problem jest prostszym wariantem, ale możesz uzyskać wskazówki na temat heurystyki opracowanej dla problemu "binpackingu". Wiele na ten temat napisano, ale dobry początek to this page.

Answer 3

Umieść na swojej stronie podobną do tetris grę. Wygeneruj bloki, które spadną, i rozmiar obszaru gry na podstawie parametrów. Punkty przyznawane są graczom w oparciu o zwartość (mniej wolnego miejsca = więcej punktów) ich projektu. Poproś odwiedzających witrynę, aby wykonali pracę za Ciebie.

Answer 4

Czy prostokąty mają tę samą wysokość? Jeśli tak, a problem polega tylko na tym, który rząd wstawiać do każdego prostokąta, problem sprowadza się do szeregu ograniczeń dotyczących wszystkich par prostokątów (X, Y) w postaci "prostokąt X nie może być w tym samym wierszu co prostokąt Y ", gdy prostokąt X zachodzi w kierunku x z prostokątem Y.

" Chciwy "algorytm do sortowania prostokątów od lewej do prawej, a następnie przypisuje każdy prostokąt z kolei do wiersza o najniższym numerze, w którym pasuje. Ponieważ prostokąty są przetwarzane od lewej do prawej, należy się tylko obawiać, czy lewy brzeg bieżącego prostokąta pokryje się z pozostałymi prostokątami, co upraszcza nieco algorytm wykrywania nakładki.

Nie mogę udowodnić, że daje to optymalne rozwiązanie, ale z drugiej strony nie można wymyślić żadnych kontrprzykładów. Ktoś?

Answer 5

Topcoder miał konkurs na rozwiązanie wersji 3D tego problemu. Zwycięzca omówił jego podejście: here, może to być dla ciebie interesująca lektura.

Answer 6

Już wcześniej pracowałem nad takim problemem. Najbardziej intuicyjny obraz to prawdopodobnie taki, w którym duże prostokąty znajdują się na dole, a mniejsze są na górze, trochę jak umieszczanie ich w pojemniku i potrząsanie tak, aby ciężkie spadały na dno. Aby to osiągnąć, najpierw posortuj swoją tablicę według malejącej powierzchni (lub szerokości) - najpierw przetworzymy duże elementy i zintegrujemy obraz.

Teraz problem polega na przypisaniu współrzędnych y do zestawu prostokątów, dla których podane są współrzędne x, jeśli dobrze cię rozumiem.

Powtórz swoje szeregi prostokątów. Dla każdego prostokąta zainicjuj współrzędną y prostokąta na 0. Następnie wykonaj pętlę, zwiększając współrzędną y tego prostokąta, aż nie skrzyżuje się z żadnym z wcześniej umieszczonych prostokątów (musisz śledzić, które prostokąty zostały wcześniej umieszczone). Zatwierdź znalezioną współrzędną y i kontynuuj przetwarzanie następnego prostokąta.