Упаковочные прямоугольники для компактного представления

Question

Я ищу указатели для решения следующей проблемы: у меня есть набор прямоугольников, высота которых также известна, а также x-позиций, и я хочу упаковать их в более компактную форму. С небольшим рисунком (где все прямоугольники имеют одинаковую ширину, но ширина может варьироваться в реальной жизни), я бы хотел вместо.

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

что-то вроде.

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

Все советы будут оценены. Я не обязательно ищу "лучшее" решение.

Answer 1

Ваша проблема - более простой вариант, но вы можете получить несколько советов, читающих об эвристике, разработанной для проблемы "binpacking". Об этом много написано, но эта страница - хорошее начало.

Answer 2

У Topcoder был конкурс для решения 3D-версии этой проблемы. Победитель обсудил свой подход здесь, это может быть интересным для вас.

Answer 3

Все ли прямоугольники одинаковой высоты? Если они есть, и проблема состоит только в том, в какую строку помещать каждый прямоугольник, то проблема сводится к серии ограничений по всем парам прямоугольников (X,Y) формы "прямоугольник X не может находиться в той же строке, что и прямоугольник Y", когда прямоугольник X перекрывается в направлении х с прямоугольником Y.

"Жадный" алгоритм для этого сортирует прямоугольники слева направо, а затем назначает каждый прямоугольник по очереди строке с наименьшим номером, в которую он помещается. Поскольку прямоугольники обрабатываются слева направо, нужно только беспокоиться о том, будет ли левый край текущего прямоугольника перекрывать какие-либо другие прямоугольники, что несколько упрощает алгоритм обнаружения перекрытия.

Я не могу доказать, что это дает оптимальное решение, но, с другой стороны, не может придумать и никаких контрпримеров наугад. Кто-нибудь?

Answer 4

Что-то вроде этого?

• Сортировать вашу коллекцию прямоугольников по X-позиции

• написать метод, который проверяет, какие прямоугольники присутствуют на определенном интервале оси X

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

• перебрать коллекцию прямоугольников

  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 5

Поместите тетрис-подобную игру на свой сайт. Генерируйте падающие блоки и размер игровой площадки на основе ваших параметров. Награда очков игрокам основана на компактности (меньше свободного места = больше очков) их дизайна. Получите посетителей вашего сайта, чтобы выполнить работу за вас.

Answer 6

Я работал над такой проблемой раньше. Наиболее интуитивно понятная картина, вероятно, та, где большие прямоугольники находятся снизу, а более мелкие - сверху, что-то вроде складывания их в контейнер и встряхивания, так что тяжелые падают на дно. Поэтому для этого сначала отсортируйте массив в порядке уменьшения площади (или ширины) - сначала мы обработаем большие элементы и создадим изображение с нуля.

Теперь проблема состоит в том, чтобы назначить y-координаты набору прямоугольников, чьи x-координаты даны, если я вас правильно понимаю.

Итерируйте по вашему массиву прямоугольников. Для каждого прямоугольника инициализируйте y-координату прямоугольника равным 0. Затем зацикливайте, увеличивая y-координату этого прямоугольника, пока он не пересекается ни с одним из ранее размещенных прямоугольников (вам необходимо отслеживать, какие прямоугольники были ранее размещены). Подтвердите координату y, которую вы только что нашли, и продолжите обработку следующего прямоугольника.