Как растягивать прямоугольники до полного замощения области?

Question

[makaleks]

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

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

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

Иллюстрация:


Так что спрашиваю сообщество, а что у нас есть из релевантных алгоритмов. Разумеется, с гуглом я не справился ещё до старта проекта.

Спасибо

Comments

[Akina]

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

Насчёт того, не приведёт ли повторное применение алгоритма к циклу, ничего не скажу...

Answer 1

[Wataru]

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

Пусть у прямоугольников будут степени свободы - верх,лево,низ,право. Изначально все прямоугольники раздуваются во все 4 стороны.

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

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

Найдите минимальное время для всех пар. "Отмотайте" это время вперед - раздуйте все прямоугольники на это количество пикселей по всем активным степеням свободы. У двух пересекающихся отберите свободу раздуваться в направлениях, где они коснулись. Если они коснулись по углу, то у вас это будет событие: или они встретились по горизонтали, или по вертикали. Именно эти степени свободы и отбираете.

Повторяйте пока есть хоть одна степень свободы где-то.

Ну и еще надо учитывать пересечения с гарницей поля - точно так же. Считаете время до столкновения.

Может быть так, что пройдет время 0, если куча прямоугольников коснутся в одно и то же время. Это нормально, вы не перематывая время в обработке этого события дезактивируете какие-то степени свободы у каких-то прямоугольников.

Можно просто после каждого столкновения снова искать минимум по всем парам прямоугольников. Можно это соптимизировать знатно через приоритетную очередь, но вряд ли у вас там тысячи прямоугольников и вам это надо делать.

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

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

Правда у этого метода есть проблема Например, вот такая картинка:

AA.B
...B
C...
C.DD

Тут прямоугольники можно чуть чуть раздуть до упирания, но при определенных пропорциях в центре останется пустое место, при чем все 4 окна будут сцеплены между собой. Не уменьшая изначальные окна его никак не убрать.