algorithm - パネルにランダムな重なり合わない長方形を配置します

Question

サイズXxYのパネルがあります。このパネルに、ランダムなサイズの最大N個の長方形を配置したいのですが、どの長方形も重ならないようにします。これらの長方形のX、Y位置を知る必要があります。

アルゴリズム、誰か？

編集：N個の長方形はすべて最初からわかっており、任意の順序で選択できます。それは手順を変更しますか？

Answer 1

これは、座標が 0,0、サイズ (x, y) の単一の長方形から始まる「自由な」長方形のセットによってモデル化できます。四角形をもう 1 つ追加する必要があるたびに、残りの「空いている」四角形の 1 つを選択し、新しい四角形を生成し (左上の座標とサイズで完全に含まれるようにします)、その四角形とその他の重なっている部分を分割します。子が残りの空き領域を表現するような、「無料」の四角形。これにより、0 から 4 個の新しい四角形が生成されます (新しい四角形が古い自由な四角形のサイズとまったく同じ場合は 0、真ん中にある場合は 4 など)。時間の経過とともに空き領域がどんどん小さくなっていくため、作成する長方形も同様に小さくなります。

わかりました、非常に手の込んだ説明ではありません。ホワイトボードに示す方が簡単です。しかし、このモデルは、新しく切り取って貼り付けた GUI コンポーネントの開始位置を見つけるために使用したものです。画面の利用可能なチャンクを追跡し、(たとえば) そのような領域の左または最上部を選択するのは簡単です。

Answer 2

2D パッキング アルゴリズムに関するまともな記事は次のとおりです: http://www.devx.com/dotnet/Article/36005

通常、適切な結果を得るには、ヒューリスティックを使用する何らかのアルゴリズムが必要です。単純な (しかし最適ではない) ソリューションは、最初に適合するアルゴリズムになります。

Answer 3

このRectanglePackingアルゴリズムを、C＃ソースファイルとして利用可能なアプリケーションの1つで使用しました。

アルゴリズムはパネルのサイズで初期化され、次にすべての長方形を反復処理してそれらの位置を取得します。パッカーによっては、長方形の順序が結果に影響を与える場合があります。

Answer 4

StaxMans の提案を使用することをお勧めします。

これが私の2cです：

たくさんの長方形をランダムに追加します (互いに重なり合います)。重なっている長方形を削除します。

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

特定の四角形に接するすべての四角形を見つけるには、四分木または x1,y1 x2,y2 値に基づく不等式を使用できます。

編集: 実際、pygame などのほとんどのゲーム エンジンには、一般的な問題である四角形の衝突検出が含まれています。

Answer 5

または、既に追加されている四角形のリストを維持し、そのリストに基づいて新しい四角形を配置する場所を割り出すアルゴリズムを作成します。長方形に関する情報を保持する基本的な Rectangle クラスを作成できます。

カスタム アルゴリズムを作成するのはそれほど難しいことではありません。