Какой элегантный алгоритм для встраивания прямоугольников разного размера в круг? - PullRequest
Новая
       1

Какой элегантный алгоритм для встраивания прямоугольников разного размера в круг?

5 голосов
/ 23 февраля 2011

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

NB. Круг не имеет фиксированного размера - это просто общая форма, которая мне нужна.

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

Они уже упорядочены по максимальному значению их ширины и высоты, сначала по величине.

В идеале - и я думаю, что это может быть гарантировано заказом - не было бы пробелов вообще.

Алгоритм, с которым я борюсь: 

for each rectangle:
    if first:
        place rectangle at origin
        add all edges to edge list
    else:
        for each edge in edge list:
            if edge is long enough to accomodate rectangle (length <= width or height depending on orientation):
                if rectangle placed on this edge does not collide with any other edges:
                    calculate edge score (distance of mid-point from origin)
        use edge with lowest edge score
        place rectangle on edge
        for each of this rectangles edges:
            if edge overlaps one already in the edge list:
                merge or remove edge
            else:
                add to edge list
        remove used edge from edge list
        add unused sections of this edge into edge list

Это хорошо работает для первых нескольких прямоугольников, но слияние ребер довольно волосатое, и мой нынешний метод выбора того, какой участок ребра использовать (один конец или другой) имеет тенденцию оставлять много пробелов.

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

Ответы [ 2 ]

2 голосов
/ 23 февраля 2011

Что вы имеете в виду "упорядочено по размеру" - длина или площадь?Я предполагаю, что это должно быть отсортировано по максимальной длине.

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

<Loop> Затем вы берете самый длинный из оставшихся прямоугольников и размещаете его на длинной стороне первого / самого длинного края стопки прямоугольников.Вероятно, вы разместите его не в середине края, а с одним углом второго на один угол первого прямоугольника.

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

Таким образом, вы получаете новое ребро, которое выравнивает угол, к которому был прикреплен прямоугольник, который теперь может быть самым длинным оставшимся ребром.</Loop>

Это то, что вы делаете?И в чем проблема?У вас есть изображение нежелательного результата?

Хорошо, увидев ваш пример, вот какой-то псевдопифон: 

class Point(object):
    x, y: Integer
class Rectangle(object):
"""Assuming that the orientation doesn't matter, length>=width"""
    length, width: Integer
class Edge(object):
    from, to: Point
    length: Integer
class Pile_Of_Rectangles(object):
    edges: list of Edges #clockwise
    def add_rectangle(r):
        search longest edge "e1"
        search the longer of the two adjacent edges "e2"
        attach r with its longer side to "e1" at the end, where it adjoins to "e2":
            adjust "e1" so that e1.length = e1.length - r.length
            insert the new edges with length r.width, r.length and r.width into self.edges
            connect the last edge with "e2"

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

0 голосов
/ 23 февраля 2011

Не могли бы вы рассказать подробнее о 1. довольно равномерно по центру? 2. какова цель? то есть вы хотите максимизировать количество подходящих прямоугольников, или вы знаете, что все они уместятся, и вы хотите минимизировать потери пространства?

Я не уверен, как ленивый человек соберется. Но если я захочу оптимизировать упаковку, я начну с углов, а затем подойду к центру.

...