3

ステージ上のランダムな位置に四角形を描いていますが、重ならないようにしています。そのため、長方形ごとに、それを配置するための空白の領域を見つける必要があります。

ランダムな位置を試してみることを考えました。空いているかどうかを確認します

private function containsRect(r:Rectangle):Boolean {
    var free:Boolean = true;
    for (var i:int = 0; i < numChildren; i++)
        free &&= getChildAt(i).getBounds(this).containsRect(r);
    return free;
}

false が返された場合は、別のランダムな位置で試行します。

問題は、空き領域がないと、ランダムな位置を永遠に試してしまうことです。

これに対するエレガントな解決策はありますか？

4

7 に答える 7

3

ステージの面積をSとします。描きたい最小の長方形の面積を A とします。N = S/A とする

考えられる決定論的アプローチの 1 つ:

空のステージに四角形を描画すると、次の四角形に収まる最大 4 つの領域にステージが分割されます。次の長方形を描くと、1 つまたは 2 つの領域が、長方形に収まる最大 4 つのサブ領域 (それぞれ) に分割されます。S がステージの領域である場合、N 個を超える領域を作成することはありません。 A は最小の長方形の面積です。地域のリストを保持し (ソートされていなくても問題ありません)、それぞれが 4 つのコーナー ポイントで表され、それぞれがその面積でラベル付けされ、面積ごとに重み付けされたリザーバー サンプリングを使用しますリザーバーのサイズが 1 の場合、最大で 1 回のリストのパスで、その面積に比例する確率で領域を選択します。次に、その領域のランダムな位置に長方形を配置します。(領域の左下部分からランダムなポイントを選択すると、そのポイントを左下隅として上または右の壁にぶつかることなく長方形を描くことができます。)

空白のステージから始めていない場合は、描画する最初のポイントを検索する前に、使用可能な領域のリストを O(N) で作成します (たとえば、空白のステージに既存のすべての長方形を任意の順序で再描画します)。新しい長方形。

注: リザーバーのサイズを k に変更して、次の k 個の四角形をすべて 1 ステップで選択できます。

注 2: 別の方法として、使用可能な領域をツリーに格納することもできます。各エッジの重みは、ステージの領域にわたるサブツリー内の領域の領域の合計に等しくなります。次に、O(logN) 内の領域を選択するために、ルート領域 / S の確率領域でルートを再帰的に選択するか、確率エッジの重み / S で各サブツリーを選択します。

    ランタイム: O(N)
    スペース: O(N)

考えられるランダム化されたアプローチの 1 つ:

ステージ上のポイントをランダムに選択します。ポイントを含む 1 つ以上の四角形 (左下隅にポイントを持つ四角形だけでなく) を描画できる場合は、ポイントを含むランダムに配置された四角形を返します。多少の微妙な工夫で偏りなく四角形を配置することは可能ですが、お任せします。

最悪の場合、四角形に丁度十分な大きさのスペースが 1 つあり、ステージの残りの部分は埋まっています。したがって、このアプローチは確率 > 1/N で成功するか、確率 < 1-1/N で失敗します。N 回繰り返します。ここで、確率 < (1-1/N)^N < 1/e で失敗します。失敗とは、長方形のためのスペースがあることを意味しますが、それが見つかりませんでした。成功とは、スペースが存在する場合にスペースを見つけたことを意味します。合理的な成功確率を達成するために、1/N の確率で失敗する場合は Nlog(N) 回、1/e^N の確率で失敗する場合は N² 回繰り返します。

要約: スペースが見つかるまでランダムなポイントを試し、NlogN (または N²) の試行後に停止します。この場合、スペースが存在しないと確信できます。

    実行時:成功する確率が高い場合はO(NlogN) 、成功する確率が非常に高い場合はO(N²)
    スペース: O(1)
于 2009-01-28T17:27:42.470 に答える
3

変換を使用して物事を単純化できます。LxH の長方形を配置する有効な場所を探している場合は、代わりに、前のすべての長方形を L 単位右に、H 単位下に成長させてから、それらのいずれとも交差しない単一の点を検索できます。 . この点は、新しい長方形を配置する有効な場所の右下隅になります。

次に、スキャン ライン スイープ アルゴリズムを適用して、四角形で覆われていない領域を見つけます。均一な分布が必要な場合は、自由領域分布によって重み付けされたランダムな y 座標 (下にスイープすると仮定) を選択する必要があります。次に、選択したスキャン ラインの開いているセグメントからランダムな x 座標を一様に選択します。

于 2009-01-28T13:37:08.177 に答える
1

これがどれほどエレガントかはわかりませんが、最大試行回数を設定できます。たぶん100？

確かに、まだ利用可能なスペースがあるかもしれませんが、「終了」イベントをトリガーすることはできます。「十分に近い」という理由だけで、トゥイーンライブラリが目的のポイントにオブジェクトをスナップするようなものです。

HTH

于 2009-01-28T11:56:07.803 に答える
1

十分なスペースがあるかどうかを判断するために実行できるチェックの 1 つは、現在の長方形のセットが占める面積をチェックすることです。残った領域の量が新しい長方形の領域よりも少ない場合は、すぐにあきらめて救済できます。あなたが入手できる情報や、長方形が規則的なパターンで配置されているかどうかはわかりませんが、そうであれば、チェックを変更して、明らかに十分なスペースがないかどうかを確認できるかもしれません.

これはあなたにとって最も適切な方法ではないかもしれませんが、私の頭に最初に浮かんだのはこれでした!

于 2009-01-28T12:16:20.103 に答える
0

これが私が使用するアルゴリズムです

  1. N 個のランダムな点を書き留めます。ここで、N は必要な長方形の数です。
  2. 各点 N で作成された四角形の寸法を、別の四角形に接触するまで繰り返し増やします。

長方形の最小許容サイズが必要な場合は、最初の点を配置​​する方法を制限できます。

すべてのスペースを長方形で覆いたい場合は、覆われていない領域がなくなるまで、残りの「空き」スペースにランダムなポイントを段階的に追加できます。

于 2009-01-28T18:27:16.687 に答える
0

長方形を描画する前に長方形の寸法を定義すると仮定すると、次のようなものがうまくいくと思います。

候補の四角形のステージ全体に可能な中心点のグリッドを確立します。したがって、6x4 の長方形の場合、最初のポイントは (3, 2) になり、次に (3 + 6 * x, 2 + 4 * y) になります。隣接する 4 点間に長方形を描くことができれば、可能なスペースが存在します。

for (x = 0, x < stage.size / rect.width - 1, x++)
    for (y = 0, y < stage.size / rect.height - 1, y++)
        if can_draw_rectangle_at([x,y], [x+rect.width, y+rect.height])
            return true;

これは、どこに描画できるかを示しているわけではありません (ただし、可能な描画領域のリストを作成することは可能である必要があります)。

于 2009-01-28T13:10:24.407 に答える
0

あなたが持っているものでこれを行う唯一の効率的な方法は、開いている場所の2Dブール配列を維持することだと思います. 描画位置がまだランダムに見えるように、十分なサイズの配列を用意してください。

新しい四角形を描画するときは、配列の対応する四角形の部分をゼロにします。その後、空き領域のチェックは一定の ^H^H^H^H^H^H^H 時間です。おっと、それはルックアップが O(nm) 時間であることを意味します。n は長さ、m は幅です。範囲ベースのソリューションが必要です。

Edit2:どうやら答えはここにありますが、私の意見では、特にジオメトリに熱心でない場合は、これを Actionscript に実装するのは少し難しいかもしれません。

于 2009-01-28T14:35:17.717 に答える