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

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

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

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

Answer 1

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

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