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

Question

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

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

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

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

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

Answer 1

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

Answer 2

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

Answer 3

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

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

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

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

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

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

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

Answer 6

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