У меня есть панель размера X по Y. Я хочу разместить до N прямоугольников, размер которых случайным образом, на этой панели, но я не хочу, чтобы их перекрывали. Мне нужно знать положения X, Y для этих прямоугольников.
Алгоритм, кто-нибудь?
Изменить. Все N прямоугольников известны в самом начале и могут быть выбраны в любом порядке. Изменит ли это процедуру?
Вы можете моделировать это с помощью набора "свободных" прямоугольников, начиная с одиночного с координатами 0,0, размера (x, y). Каждый раз, когда вам нужно добавить еще один прямоугольник, выберите один из оставшихся "свободных" прямоугольников, создайте новый прямоугольник (с левой и левой координатами и размером, чтобы он был полностью сложен), и разделите этот прямоугольник так же, как и любые другие перекрывающиеся "свободный" прямоугольник, так что дети выражают оставшееся свободное пространство. Это приведет к от 0 до 4 новых прямоугольников (0, если новый прямоугольник был точно размером с старый свободный прямоугольник, 4, если он посередине и т.д.). Со временем вы получите все меньше и меньше свободных площадей, поэтому прямоугольники, которые вы создаете, также будут меньше.
Хорошо, не очень подробное объяснение, его легче показать на доске. Но модель - это та, которую я использовал для поиска исходного местоположения для недавно вставленных компонентов gui; легко отслеживать доступные фрагменты экрана и выбирать (например) левую или верхнюю такую область.
Вот достойная статья по алгоритмам 2d упаковки: http://www.devx.com/dotnet/Article/36005
Обычно вам нужен какой-то алгоритм, использующий эвристику для достижения достойных результатов. Простым (но неоптимальным) решением будет первый алгоритм подгонки.
Я использовал этот Rectangle Packing algorithm в одном из моих приложений, доступном как исходные файлы С#.
Алгоритм инициализируется размером панели, затем вы перебираете все прямоугольники и получаете свою позицию. Порядок прямоугольников может влиять на результат, в зависимости от упаковщика.
Я бы посоветовал вам использовать предложение StaxMans.
Вот мой 2c:
Добавить много прямоугольников случайным образом (перекрывая друг друга). удалить перекрывающиеся прямоугольники:
for rectangle in list of rectangles:
if rectangle not deleted:
delete all rectangles touching rectangle.
чтобы найти все прямоугольники, которые касаются определенного прямоугольника, вы можете использовать квадратное дерево или неравенства на основе значений x1, y1 x2, y2.
Изменить: на самом деле, большинство игровых движков, таких как pygame и т.д., включают обнаружение конфликтов прямоугольников, что является общей проблемой.
Или сохраните список уже добавленных прямоугольников и создайте алгоритм, который определяет, где разместить новый прямоугольник на основе этого списка. Вы можете создать базовый класс Rectangle для хранения информации о ваших прямоугольниках.
Не так сложно создать собственный алгоритм.