Я хотел бы написать простую программу, которая принимает набор окон (ширина + высота) и разрешение экрана и выводит расположение этих окон на экране таким образом, чтобы окна занимали больше всего места. Поэтому можно изменить размер окна, сохраняя при этом output size >= initial size
и соотношение сторон. Поэтому для окна я бы хотел, чтобы алгоритм возвращал кортеж .( х , у , ш я д T ч , ч е я г ч т )
Я считаю, что это может быть вариация 2D рюкзака. Я пытался просмотреть результаты в Интернете, но в большинстве случаев они имели большой опыт (и не имели реализации), из-за чего мне было трудно следить.
Меня меньше интересует самый быстрый алгоритм, но больше что-то практичное для моих конкретных нужд.
algorithms
computational-geometry
packing
user-interface
daniel.jackson
источник
источник
Ответы:
Хотя ваш вопрос не говорит об этом, я предполагаю, что вы не хотите, чтобы окна перекрывались.
Одним из подходов к этой проблеме является использование решателя ограничений, такого как Choco . Один просто записывает ограничения, кодирующие вашу проблему, настраивает решатель так, чтобы он действовал разумно, и затем запускает его. Это означает, что все ваши мысли будут потрачены на поиск хорошего способа кодирования проблемы, а не на разработку алгоритма, а также на программирование и настройку. Вот частичный ответ, чтобы вы начали.
Предположим, что размер экрана равен .xmax×ymax
Для каждого окна, , у вас будет набор переменных и ограниченийx i , y i , h i , w iWi xi,yi,hi,wi
Теперь вам нужно позаботиться о перекрытии окон. Для каждой пары окон, , где , вы будете генерировать ограничения, подобные следующим, которые фиксируют, что ни один угол появляется внутри . Для сгенерируйте ограничение: i ≠ j W j W i ( x , y ) ∈ { ( x j , y j ) , ( x jWi,Wj i≠j Wj Wi (x,y)∈{(xj,yj),(xj+wj,yj),(xj,yj+hj),(xj+wj,yj+hj)}
Указанные выше ограничения описывают только неперекрывающиеся окна, которые не растекаются по сторонам экрана, удовлетворяют некоторым ограничениям минимального размера и сохраняют соотношение сторон.
Чтобы получить хорошее соответствие, вам нужно указать метрику, которая отражает, что значит быть хорошим макетом. Одна из возможностей - предположить, что вы хотите, чтобы окна были примерно одинаковыми по размеру и / или что вы хотите минимизировать «пустое пространство». Я не думаю, что это может быть указано с помощью Choco, но это может быть возможно с другим решением ограничений (кто-то еще может помочь здесь).
Choco позволяет максимально увеличить целевую функцию, указанную в качестве одной переменной. Основываясь на этой идее, вы можете максимизировать следующее:
написав ограничение и сказав Choco, чтобы максимизировать .c o s tcost=∑i(hi+wi) cost
источник
Я начал писать прототип для решения «грубой силы», которое, надеюсь, можно будет оптимизировать до такой степени, что оно будет практичным.
Сначала несколько определений: пусть будет множеством всех окон. Каждое окно состоит из для координат x, y, а также ширины и высоты. Окно инициализируется с минимальной шириной и высотой.W w xw,yw,ww,hw
Вводом алгоритма является экран , который имеет ширину и высоту, а также список окон.S
Это работает примерно так:
Есть несколько вещей, которые должны быть улучшены:
S.coordinates()
сейчас очень медленно Он перебирает все точкиS.width x S.height
и проверяет, находится ли каждый из них в одном из окон S.S.put()
проверяет, перекрывается ли его параметр с остальными окнами S, выполняя тест, упомянутый в ответе Дэйва. Может быть, это можно улучшить с помощью интервальных деревьев ?S.score()
в настоящее время возвращает который является просто областью всех окон. Нужно учитывать другие переменные, чтобы получить лучшие макеты.Вышеупомянутая функция должна попробовать все перестановки чтобы получить наилучший возможный результат.W
В настоящее время я пытаюсь выяснить подходящую структуру данных для представления экрана и его окон, он должен поддерживать эти запросы:
источник