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

Question

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

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

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

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

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

Answer 1

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

• Сортировка вашей коллекции прямоугольников по х-положении

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

  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 2

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

Answer 3

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

Answer 4

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

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

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

Answer 5

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

Answer 6

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

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

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