パネル上に重複しない矩形をランダムに配置する

Question

私はサイズXのパネルをYで作っています。このパネルにランダムにサイズが決められたN個の矩形を配置したいと思いますが、 。私はこれらの矩形のX、Yの位置を知る必要があります。

アルゴリズム、誰ですか？

：N個の矩形はすべて最初から分かっており、任意の順序で選択できます。それは手技を変えますか？

Answer 1

これは、座標が0,0、size（x、y）の単一のものから始まる一連の「フリー」四角形でモデル化できます。もう1つの矩形を追加する必要があるたびに、残っている「空いている」矩形の1つを選択し、新しい矩形（左上の座標とサイズを完全に含むように）を生成し、子どもが自由な空き領域を表現するように「空き」の四角形を作成します。これにより、0〜4の新しい矩形が作成されます（新しい矩形が正確に古い空き矩形のサイズだった場合は0、それが中間にある場合は4など）。時間の経過とともに、より小さい空き領域がますます小さくなるため、作成する長方形も小さくなります。

[OK]を、非常に精巧な説明ではなく、ホワイトボードに表示する方が簡単です。しかし、このモデルは、新しくカットされたGUIコンポーネントの開始位置を見つけるために使ったモデルです。画面の利用可能なチャンクを追跡し、そのような領域の左または最上部を（たとえば）選択するのは簡単です。ここで

Answer 2

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

あなたは、一般的にまともな結果を達成するために、ヒューリスティックを使用して、アルゴリズムのいくつかの並べ替えをお勧めします。単純な（ただし最適ではない）ソリューションが最初のフィットアルゴリズムになります。

Answer 3

すでに追加されている長方形のリストを維持し、そのリストに基づいて新しい矩形をどこに配置するかを決定するアルゴリズムを作成します。基本的なRectangleクラスを作成して、長方形に関する情報を保持することができます。

カスタムアルゴリズムを作成する必要はありません。

Answer 4

私はこのアプリケーションをC＃ソースファイルとして提供しています。このアプリケーションはRectangle Packing algorithmです。

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

Answer 5

StaxMansの提案をお勧めします。

は、長方形の全体の多くをランダム（重なり合う）を追加します：

は、ここに私の2Cです。長方形の重複削除 ：

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

は、特定の長方形に触れるすべての矩形を見つけるために、あなたはX1、Y1のX2、Y2の値に基づいて、クワッドツリーや不平等を使用することができます。

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