6

最大 3 つの領域を持つ再描画領域を実装しようとしていますが、一連の四角形から最適な領域のセットを見つける効率的な方法が思いつきません。

したがって、一連の長方形があり、最小面積を生成する最大 3 つの境界長方形を計算する必要があります。 境界四角形

黒い四角形は一連の四角形で、赤い四角形は最小の領域を生成する境界ボックス (最大 3 つ) です。境界ボックスの最適な組み合わせを考え出す必要があります。

4

4 に答える 4

1

ほとんどの3つの長方形と同様に、すべてが常にxy軸上に配置および整列され、オーバーラップはありませんか？運が良ければ、そのような長方形のセットが3つあり、作業でそれらを列挙するのは非常に簡単です。視覚的に表示するのに十分な数の黒い長方形を扱っていることを考えると、それらすべてを列挙し、最適なものを選択することは、十分に速いはずです。O(n2)O(n3)

最初に、2境界の長方形の場合について考えてみましょう。これは、より単純だからです。画像をx軸に投影するのは簡単です。また、画像をy軸に投影するのも簡単です。これらの2つの投影の少なくとも1つには、重なりのない目に見えるギャップがあります。したがって、最初にすべての黒い長方形をx軸の線分に投影し、ギャップを探し、ギャップごとに取得したバウンディングボックスのペアを再構築することにより、2つの長方形に分割する可能な方法を列挙できます。次に、y軸を使用して手順を繰り返します。そして、それらすべてを取得します。

これで、3つの境界の長方形の場合も同様になります。xy軸に沿って方向付けられた3つの重なり合わない長方形が与えられた場合、x投影またはy投影のいずれかに目に見えるギャップが必要であることがわかります。したがって、以前と同じ手順を実行できますが、バウンディングボックスのペアを作成するだけでなく、同じアルゴリズムを使用して1つのバウンディングボックスを作成し、もう1つをさらに2つに分割する方法を試します。

（ちなみに、3が欲しかったのは幸運です。このアプローチは、4つの境界の長方形の場合に分類されます。そのため、x投影もy投影も目に見えるギャップがないように、4つの境界長方形を持つことができます。 。）

では、n個の黒い長方形を取得し、それらを1つの軸（たとえばx軸）に投影して、境界の長方形のセットを探すにはどうすればよいでしょうか。それらを並べ替え、最大の重複間隔を作成し、ギャップを見つけるだけです。このような：

function find_right_boundaries_of_x_gaps (rectangles) {
  var ordered_rect = rectangles.sort(function (r1, r2) { return r1.x1 <=> r2.x2 });
  var gaps = [];
  var max_right = ordered_rect[0].x2;
  for (var i = 0; i < ordered_rect.length; i++) {
    if (max_right < ordered_rect[i].x1) {
      gaps.push(max_right);
    }
    if (max_right < ordered_rect[i].x2) {
      max_right = ordered_rect[i].x2;
    }
  }
  return gaps;
}

ギャップがあれば、両側にある2つの長方形のバウンディングボックスを簡単に把握できます。（順序付けられた長方形がある場合は、さらに簡単です。）

これらのピースを使用すると、コードを記述できるようになります。残念ながら、単純なアプローチでは、反復的なコードを大量に作成するか、大量のデータ構造を構築する必要があるかを選択できます。ただし、クロージャに慣れている場合は、2つのまったく異なる方法で両方の問題に対処できます。

1つ目は、呼び出されたときに、必要なさまざまなデータ構造を反復処理するクロージャーを作成することです。インスピレーションについては、 http：//perl.plover.com/Stream/stream.htmlを参照してください。ここでの考え方は、長方形のセットを取り、バウンディングボックスのペアのストリームを返す関数を記述し、次に、長方形のセットを取り、バウンディングボックスのペアのストリームを取得し、トリプレットのストリームを返す別の関数を作成することです。バウンディングボックスの。次に、そのストリームを取得して最適なストリームを見つけるフィルターを用意します。

もう1つは裏返しです。可能性を反復処理できる関数を返すのではなく、関数を渡し、可能性を反復処理し、可能性ごとに関数を呼び出します。（上記の関数はさらに反復を行う可能性があります。）Rubyでブロックにさらされている場合、このアプローチは非常に理にかなっている可能性があります。

クロージャに慣れていない場合は、最後の数段落を無視することをお勧めします。

于 2011-02-20T13:42:36.127 に答える
1

これはかなり単純な例です。アイデアは、 MSTのようにバウンディング ボックスを「成長」させることです。この問題は MST に似ていると思いますが、最大 3 つのばらばらなツリーがあり、複雑さが大幅に増加します。

このアルゴリズムは、約 (n choose 3)*(3*n) ステップ、つまり O(n^4) かかります。

  1. 長方形に番号を付けます。
  2. 3 つの長方形の任意の組み合わせを選択します。各組み合わせについて:
    1. 3 つの初期バウンディング ボックスを幅/高さに設定します。
    2. 残りの各長方形について:
      1. 3つすべてについて、バウンディングボックスに追加された場合にバウンディングボックスが増加する領域を見つけます。
      2. サイズの増加を最小限に抑えてボックスに追加します（そのバウンディングボックスのサイズを変更します）。

最初は、これは最適ではないように思われるかもしれません。ステップ 2.2 で残りの長方形を追加する順序が、取得するバウンディング ボックスのサイズに影響します。より良い構成をキャッチします。

于 2011-02-20T07:35:36.223 に答える
0

「muが短すぎる」という前回のコメントに同意します。問題を解決する1つのアルゴリズムは、「黒い」長方形の各ペア間の距離の水平成分と垂直成分の乗算に基づいて、既存のすべての「黒い」長方形を1つから3つの幾何学的クラスターに分割できます（これにより、仮想の領域が得られます）各ペアの間に形成された「赤い」長方形）、次に、結果の各クラスターを「赤い」長方形でバインドします。

問題のそのコンポーネントを解決するために選択した幾何学的クラスタリングアルゴリズムに関係なく（これについては以下で詳しく説明します）、「直線」または各ペア間のユークリッド距離を使用して「黒」の長方形をクラスターに分割しないことが重要です。問題は境界（「赤」）の長方形の面積を減らすことであるため、パラメータ。前の段落で述べたように、境界となる「赤」の長方形がカバーする可能性のある領域を考慮するために、「黒」の長方形の各ペア間の距離の水平成分と垂直成分を乗算する必要があります。

文献には、時間と空間の複雑さのトレードオフが異なる多くの幾何学的クラスタリングアルゴリズムがあります。このGoogle検索から始めて、それらに精通することをお勧めします。あるいは、この問題は、遺伝的またはシミュレーテッドアニーリングアルゴリズムを使用することにより、クラスタリングアルゴリズムを使用せずに解決できます。この場合、さまざまな組み合わせの総面積と可能な境界の「赤い」長方形の数が試行され、順番に測定されます。最適なソリューションを作成します。

必要な説明をお気軽にお願いし、プロジェクトを頑張ってください！

于 2011-02-20T08:44:48.040 に答える
0

一意の最小外接四角形はありませんか? すべての長方形の中で最大および最小の x 座標と y 座標を取得し、それらの仕様から長方形を作成するだけです。

于 2011-02-20T04:00:52.433 に答える