Поместите случайные неперекрывающиеся прямоугольники на панели

У меня есть панель размера X по Y. Я хочу разместить до N прямоугольников, размер которых случайным образом, на этой панели, но я не хочу, чтобы их перекрывали. Мне нужно знать положения X, Y для этих прямоугольников.

Алгоритм, кто-нибудь?

Изменить. Все N прямоугольников известны в самом начале и могут быть выбраны в любом порядке. Изменит ли это процедуру?

Ответы

Ответ 1

Вы можете моделировать это с помощью набора "свободных" прямоугольников, начиная с одиночного с координатами 0,0, размера (x, y). Каждый раз, когда вам нужно добавить еще один прямоугольник, выберите один из оставшихся "свободных" прямоугольников, создайте новый прямоугольник (с левой и левой координатами и размером, чтобы он был полностью сложен), и разделите этот прямоугольник так же, как и любые другие перекрывающиеся "свободный" прямоугольник, так что дети выражают оставшееся свободное пространство. Это приведет к от 0 до 4 новых прямоугольников (0, если новый прямоугольник был точно размером с старый свободный прямоугольник, 4, если он посередине и т.д.). Со временем вы получите все меньше и меньше свободных площадей, поэтому прямоугольники, которые вы создаете, также будут меньше.

Хорошо, не очень подробное объяснение, его легче показать на доске. Но модель - это та, которую я использовал для поиска исходного местоположения для недавно вставленных компонентов gui; легко отслеживать доступные фрагменты экрана и выбирать (например) левую или верхнюю такую ​​область.

Ответ 2

Вот достойная статья по алгоритмам 2d упаковки: http://www.devx.com/dotnet/Article/36005

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

Ответ 3

Я использовал этот Rectangle Packing algorithm в одном из моих приложений, доступном как исходные файлы С#.

Алгоритм инициализируется размером панели, затем вы перебираете все прямоугольники и получаете свою позицию. Порядок прямоугольников может влиять на результат, в зависимости от упаковщика.

Ответ 4

Я бы посоветовал вам использовать предложение StaxMans.

Вот мой 2c:

Добавить много прямоугольников случайным образом (перекрывая друг друга). удалить перекрывающиеся прямоугольники:

for rectangle in list of rectangles:
    if rectangle not deleted:
        delete all rectangles touching rectangle.

чтобы найти все прямоугольники, которые касаются определенного прямоугольника, вы можете использовать квадратное дерево или неравенства на основе значений x1, y1 x2, y2.

Изменить: на самом деле, большинство игровых движков, таких как pygame и т.д., включают обнаружение конфликтов прямоугольников, что является общей проблемой.

Ответ 5

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

Не так сложно создать собственный алгоритм.