Алгоритм компоновки прямоугольных окон в 2D-дисплее

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

  1. Все окна, подлежащие компоновке, можно увидеть в виде небольших прямоугольников.
  2. Все окна должны быть расположены в прямоугольном 2D-дисплее, ширина и высота которого заданы.
  3. Есть несколько десятков окон для макета. Каждое окно имеет начальную позицию (x,y) и размер (ширина, высота).
  4. Алгоритм компоновки попытается разделить окна, чтобы избежать перекрытия окон, чтобы пользователю было легче видеть все окна.

  5. Глобальное ограничение (max_x_offset, max_y_offset) задается так, чтобы перемещенная новая позиция каждого окна (new_x, new_y) удовлетворяла ограничению:

    abs(new_x - x) <= max_x_offset and abs(new_y - y) <= max_y_offset

  6. Глобальное ограничение является жестким ограничением, что означает, что если такой макет не может удовлетворить как 4, так и 5, мы должны удовлетворить глобальное ограничение и позволить некоторым окнам перекрываться.

  7. Алгоритм может не дать наилучших возможных результатов, но он должен работать быстро. Мы собираемся использовать этот алгоритм в приложении для рендеринга в реальном времени.

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

Обновление: Да, я понимаю, что это проблема с двумерным рюкзаком, и это NP-трудно. Мне нужен быстрый алгоритм для получения достаточно хорошего результата.


user-interface rendering algorithm real-time
person Long Cheng    schedule 19.01.2010    source источник
comment
Это разновидность задачи о рюкзаке en.wikipedia.org/wiki/Knapsack_problem.   -  person cletus    schedule 19.01.2010

Ответы (1)


arrow_upward
2
arrow_downward

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

Конечно, это не всегда найдет решение, если оно существует. Но я думаю, что в целом это очень сложно или даже невозможно сделать эффективно.

person Thomas    schedule 19.01.2010
comment
Хорошая точка зрения. Некоторое время назад я проверил boost 1.41 и обнаружил, что в нем есть такой алгоритм fruchterman_reingold_force_directed_layout. Но я все еще пытаюсь понять, как я могу поместить ограничение смещения позиции в алгоритм. Есть идеи? - person Long Cheng; 19.01.2010
comment
Я не знаю этого алгоритма, извините. - person Thomas; 19.01.2010