1

ここでのすべての値は、最大 2 桁の浮動小数点数を持つ実数です。

による長方形の領域があると100.0し75.0ます。

次に、一連の長方形が与えられます。これらの長方形が結合して領域全体をカバーしているかどうかを確認するにはどうすればよいですか?

私たちが持っている場合

(0,0,50,75)

領域の半分しかカバーしていないため、明らかにこれは起こりません。私たちが持っている場合

(0,0,50,75)
(50,0,50,75)

両方の長方形が効果的に全体をカバーするため、これは機能し(100,75)ます。

私は何を試しましたか

ブール値の多次元配列を作成しようとしました (うまくいきませんでした):

bool area[10000][7500];

これらは、浮動小数点を処理する必要がないように、100 を掛けた領域の寸法です。次に、各長方形を反復処理し (それらの値も 100 倍します)、それらの「ピクセル」ごとに、ブール値をtrue.

最終的に、領域内のすべてのブール値が であるかどうかを確認しますtrue。

これは非常に愚かであることが判明しました。これを行うためのより良い方法を見つけるのを手伝ってもらえますか?

4

3 に答える 3

4

次のような戦略がうまくいくと思います。

  1. あなたの領域の外に完全にある長方形を捨ててください
  2. 1 つの軸を基準にして、リスト内の長方形の端に沿って領域を小さな長方形に分割します
  3. ステップ 2 で作成された領域長方形のリストを、カバー リスト内の長方形のエッジに沿って、他の軸に対して分割します。
  4. これで、2 つの長方形のリストができました。カバー リストには、各領域の長方形を完全にカバーする 1 つが必要です。
于 2013-04-23T23:17:24.417 に答える
2

（通常の）浮動小数点の丸めの問題が原因で、「ビットマップ」の試みが失敗したと思います。残念ながら、それについてできることはほとんどありません。

適切なアルゴリズムについては、減算手法を使用してアプローチします。

  • 最初の長方形のセットを R としましょう。
  • 領域全体をカバーする単一の四角形を最初に含む四角形 S の 2 番目のセットを初期化します。
  • R の各四角形について:
    • S の各長方形について:
      • 2 つの R 長方形と S 長方形が交差する場合、S 長方形を、S 長方形から離れた交差しない部分をカバーする必要な数の長方形 (私が間違っていなければ 0 から 4) に置き換えます。
      • 追加したばかりの新しい S 四角形 (現在の R 四角形と交差しないことは既にわかっています) について何も計算しないように注意しながら、S の繰り返しを続けます。
    • 次のいずれかになるまで、今度は新しい S 四角形を考慮して、R の反復を続けます。
      • S には四角形が残っていません。この場合、R 四角形は領域全体をカバーします。
      • または、すべての R 四角形を反復処理しても、まだ S 個の四角形が残っている場合、R 四角形は領域全体をカバーしていません。

複雑さに関しては、@ 500-Internal-Server-Error や @Tommy のソリューションと比べてどうなのかはわかりませんが、少なくとも、読んだときには思いつかなかった何かを思いつくことができました最初にあなたの質問 - 私は通常、空間的なものはあまり得意ではありません。:)

于 2013-04-23T23:36:14.633 に答える
1

概念的に 500 - 内部サーバー エラーに非常に似たアプローチは、最終ステップで暗示された O(n^2) 検索を回避します。

  1. カバー セットからすべての長方形の垂直境界のリストを作成します。
  2. n 個の境界を作成すると仮定すると、ソースの四角形で考慮すべき n+1 個の垂直ストリップがあります。
  3. ストリップごとに、オーバーラップするすべての長方形のリストを取得します (逆方向に検索するのではなく、長方形からビンにプッシュすることで O(n) 時間でこれを行うことができます)。
  4. リストを左から右に並べ替えます (つまり、O(n log n))。
  5. 並べ替えられたリストを調べて、1 つのスパンが終了し、少し後になるまで他に何も開始されないギャップを見つけようとします (別の O(n) タスク)。

適切なギャップが見つかった場合、オリジナルはカバーされません。そうでない場合は、そうです。ちなみに、これは基本的にスパンバッファリングの仕組みです。

于 2013-04-23T23:27:43.783 に答える