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

Question

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

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, мы st удовлетворяют глобальному ограничению , и пусть некоторое окно перекрывается.

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

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

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

Answer 1

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

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