Мозаика из прямоугольников

Question

У меня есть большое окно, в котором есть n маленьких окон. Задача разместить маленькие окна так, чтобы между ними не было пересечений, или сказать, что это невозможно сделать.

Все окна прямоугольные и имеют координаты всех вершин.

Я понимаю, как легко определить, пересекают ли один из прямоугольников с остальными. Достаточно посмотреть, включены ли координаты вершин в любой другой прямоугольник.

Но вот как найти свободную область, куда вы могли бы переместить этот прямоугольник?

В моем случае маленькие окна появляются в большом. И проблема выглядит так.

Answer 1

Это похоже на проблему Rectangle Packing .Существуют примеры и реализаций , которые могут помочь.

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

Зависит от того, как работает эта функция, я полагаю,Разрешено ли пользователю пересекать окна в первую очередь?

Я предполагаю, что все прямоугольники должны будут поместиться в более крупный (дисплей)

Я играл с прямоугольниками разных размеров на моем столе, и вот что-то, что приходит на ум:

1-й определите, достаточно ли у вас всего пространства: разбейте оставшееся пространство на прямоугольники и добавьте области прямоугольников, затем проверьте, больше ли области пробелов или равны областям пересечения,Если это так, продолжайте.

1. Переберите все прямоугольники и найдите пересечения.
2. Для каждого пересечения сохраните соответствующие прямоугольники.
3. Переберите все прямоугольники, которые имеют пересеченияи сохраните доступное пространство в
   оставшихся направлениях (например, влево, вверху слева, сверху и т. д.)
4. Для каждого прямоугольника с пересечениями добавьте горизонтальное левое пространство над пространством, чтобы проверить, больше ли оно, чемширина прямоугольника пересечения, затем сделайте то же самое с вертикальной слева над пространством.Этот шаг должен позволить определить, можно ли перемещать только прямоугольники с пересечениями, чтобы получить достаточно места для очистки пересечений.
5. Если вышеприведенное применимо, используйте оставшееся пространство, чтобы определить, сколько вам нужно переместить каждый прямоугольник.Выберите направление разделения (вертикальное или горизонтальное), в зависимости от того, какой оставшийся интервал больше (например, общий верх + низ против общего левого + правого).Затем переместите каждый прямоугольник в направлении разделения (например, если по горизонтали переместите прямоугольник с наименьшим горизонтальным пространством на эту величину, затем другой прямоугольник в направлении оставшегося пространства), и пересмотрите пересечение для этого случая.Если пересечений нет, ура ... в противном случае, сделайте то же самое с вертикальным пространством.
6. Если этот параметр 4 не применяется, это означает, что вы не можете слегка перемещать прямоугольники, используя пространство вокруг них, вам нужноиспользовать больше места.Включите ближайшее поле и его место, затем проверьте еще раз, достаточно ли дополнительного места.

Вот что я имею в виду, поделив оставшееся пространство на прямоугольники, чтобы найти область:

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

HTH

Answer 2

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