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

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

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

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

5 12
algorithm random puzzle

5 ответов:

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

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

15

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

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

5

Я использовал этоталгоритм упаковки прямоугольников в одном из своих приложений, доступных в виде исходных файлов C#.

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

3

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

Вот мой 2c:

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

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

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

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

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

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

-4