5

おそらく最大のものを中心にして、大まかに円に合わせる必要がある可変サイズの長方形がたくさんあります。

注意。円は固定サイズではありません - それは私が求めている全体的な形です.

これは、怠惰な人間のパックを想像する方法に似ています (ピースが配置されると、それは残ります)。

それらは、幅と高さの最大値から順に並べられています。

理想的には、これは注文によって保証できると思いますが、ギャップはまったくありません。

私が苦労しているアルゴリズムは次のとおりです。

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

これは最初のいくつかの長方形では問題なく機能しますが、エッジのマージはかなり複雑で、使用するエッジのセクション (一方の端または他方の端) を選択する現在の方法では、多くのギャップが残る傾向があります。

最終的にはこの方法がかなり満足のいくものになると思いますが、もっと洗練された (グラフ?) アルゴリズムが欠けているように感じます。

4

2 に答える 2

2

「サイズ順」とは、長さですか、それとも面積ですか? 最大長でソートする必要があると思います。

「長方形のスペースがある原点に最も近いエッジを見つける」にはどうすればよいですか? 私がタスクを理解している限り、長辺の長さで並べ替えられた長方形があります。最も長いものを原点に配置します。

<Loop> 次に、残りの長方形の中で最も長いものを取り、最初のものの長辺/長方形の山の最長の端に配置します。おそらく、エッジの中央ではなく、最初の長方形の 1 つの角に 2 番目の角を配置します。

原則として、残りの最も長いエッジの西端または北端を常に使用することをお勧めします (好みに応じて)。常にエッジの長いコーナーを選択する方がよい場合もあります。

そのため、長方形が取り付けられた角をまっすぐにする新しいエッジが得られます。これは、残っている最長のエッジになる可能性があります。 </Loop>

それはあなたがすることですか？そして、何が問題だと思われますか？望ましくない結果の写真はありますか?

わかりました、ここであなたの例を見た後、いくつかの擬似python：

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"

それが私の推論をより透明にすることを願っています。このアプローチでは、多かれ少なかれ凸形状が生成されると思われるため、ギャップや衝突は発生しません (不明)。

于 2011-02-23T06:54:14.207 に答える
0

1. 中心付近でかなり均等に、さらに詳しく説明していただけますか? 2.目標は何ですか？つまり、収まる長方形の数を最大化したいですか、それともすべてが収まることが分かっていて、スペースの無駄を最小限に抑えたいですか?

怠惰な人間がどのように荷造りするかはわかりません。しかし、パッキングを最適化したい場合は、隅から始めて中央に移動します.

于 2011-02-23T06:30:05.297 に答える