Как разработать алгоритм размещения (изменяемого размера) окон на экране, чтобы покрыть как можно больше места?

20

Я хотел бы написать простую программу, которая принимает набор окон (ширина + высота) и разрешение экрана и выводит расположение этих окон на экране таким образом, чтобы окна занимали больше всего места. Поэтому можно изменить размер окна, сохраняя при этом output size >= initial sizeи соотношение сторон. Поэтому для окна я бы хотел, чтобы алгоритм возвращал кортеж .( х , у , ш я д T ч , ч е я г ч т )i(x,y,width,height)

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

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

daniel.jackson
источник
1
Если вы изменяете размер окна, вы не «поддерживаете его первоначальный размер», я полагаю, просто его соотношение сторон.
Эмре
1
Вы можете изменить размер одного окна, чтобы покрыть экран, в чем проблема?
2
Я второй комментарий Саида. Вам нужны дополнительные ограничения, такие как минимальные размеры, с целью минимизации суммы изменений, если вы хотите исключить тривиальные решения. Замечание: математики, кажется, называют тесселяции проблем с черепицей .
Рафаэль
1
Может быть, лучше сказать, вы хотите максимизировать минимальную видимую область окна и минимизировать максимальную видимую область окна, но конфликты разрешены или нет? Пожалуйста, отредактируйте свой вопрос, чтобы он не содержал ошибок, подумать о текущей постановке проблемы нелегко.
2
@ daniel.jackson: Он предлагает вам стремиться к созвездию, где наименьшее окно максимально велико, т.е. у вас нет действительно маленьких окон. Математически можно сказать, что вы максимизируете с W набором окон. WminwWsize(w)W
Рафаэль

Ответы:

9

Хотя ваш вопрос не говорит об этом, я предполагаю, что вы не хотите, чтобы окна перекрывались.

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

Предположим, что размер экрана равен .xmax×ymax

Для каждого окна, , у вас будет набор переменных и ограниченийx i , y i , h i , w iWixi,yi,hi,wi

  • xi,yi,hi,wi0
  • xi+wixmax
  • yi+hiymax
  • Возможно также некоторые ограничения на минимальный размер окон, например, и так далее.hi100
  • Аспектные ограничения: Если соотношение сторон 3: 4, ограничение может быть примерно таким: , где - это небольшой ненулевой термин ошибки, который допускает несовершенные размеры окна, так как в противном случае вы бы чрезмерно ограничить проблему.epsi ;4hiϵ3wi4hi+ϵϵ

Теперь вам нужно позаботиться о перекрытии окон. Для каждой пары окон, , где , вы будете генерировать ограничения, подобные следующим, которые фиксируют, что ни один угол появляется внутри . Для сгенерируйте ограничение: i j W j W i ( x , y ) { ( x j , y j ) , ( x jWi,WjijWjWi(x,y){(xj,yj),(xj+wj,yj),(xj,yj+hj),(xj+wj,yj+hj)}

  • ¬(xixxi+wjyiyyi+hj) .

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

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

Choco позволяет максимально увеличить целевую функцию, указанную в качестве одной переменной. Основываясь на этой идее, вы можете максимизировать следующее:

  • i(hi+wi)

написав ограничение и сказав Choco, чтобы максимизировать .c o s tcost=i(hi+wi)cost

Дэйв Кларк
источник
Это выглядит многообещающе, и я определенно поиграю с Чоко, чтобы увидеть, как это работает и как быстро.
daniel.jackson
Но почему фраза это что вообще? Я думаю, что вы можете сформулировать ограничения как линейные неравенства, что означает, что у вас есть ванильная линейная программа.
Суреш
@Suresh: не стесняйтесь разрабатывать. Я не сразу вижу, как.
Дейв Кларк,
1

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

Сначала несколько определений: пусть будет множеством всех окон. Каждое окно состоит из для координат x, y, а также ширины и высоты. Окно инициализируется с минимальной шириной и высотой.Wwxw,yw,ww,hw

Вводом алгоритма является экран , который имеет ширину и высоту, а также список окон.S

Это работает примерно так:

void fit(W, S, i, n, result)
    if i == n
        if S.score() < result.score()
            result = S
        return

    w = W[i]
    foreach x, y in S.coordinates()
        set w position to (x, y)
        while S.put(w) # check that w doesn't overlap with S's other windows and add it
            fit(W, S, i+1, n, result)
            S.windows.pop()
            w.grow()
        w.restoresize()

Есть несколько вещей, которые должны быть улучшены:

  • S.coordinates()сейчас очень медленно Он перебирает все точки S.width x S.heightи проверяет, находится ли каждый из них в одном из окон S.

  • S.put()проверяет, перекрывается ли его параметр с остальными окнами S, выполняя тест, упомянутый в ответе Дэйва. Может быть, это можно улучшить с помощью интервальных деревьев ?

  • S.score()в настоящее время возвращает который является просто областью всех окон. Нужно учитывать другие переменные, чтобы получить лучшие макеты.wS.windows(hwww)

  • Вышеупомянутая функция должна попробовать все перестановки чтобы получить наилучший возможный результат.W

В настоящее время я пытаюсь выяснить подходящую структуру данных для представления экрана и его окон, он должен поддерживать эти запросы:

  • вернуть список координат, где данное окно может быть расположено без наложения на другие
  • вставить окно в позиции x, y (уже проверено, что оно не перекрывается)
  • вернуть все окна
оборота Даниэль Джексон
источник