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

Question

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

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

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

Answer 1

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

Вот мой 2с:

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

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

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

Редактировать: На самом деле, большинство игровых движков, таких как Pygame и т. Д., Включают обнаружение столкновений прямоугольников, что является распространенной проблемой.

Answer 5

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

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