5

直方体のリストがあります。これは、軸に平行なエッジを持つ、左下と右前の角の座標によって定義されています。座標はdouble値です。これらの直方体は密集しており、1つまたは複数の他の直方体と重なるか、または他の直方体を完全に含みます。

与えられたすべての直方体に含まれる総体積を計算する必要があります。重複する領域（複数回でも）は、正確に1回カウントする必要があります。

たとえば、ボリューム：

  1. （（0,0,0）（3,3,3））
  2. （（0,1,0）（2,2,4））
  3. （（1,0,1）（2,5,2））
  4. （（6,6,6）（8,8,8））

総量は27+1 + 2 + 8 = 38です。これを行う簡単な方法はありますか（O（n ^ 3）時間以上ですか？）？

4

4 に答える 4

3

これは、平面スイープアルゴリズムを使用して効率的に解決できます。これは、重なり合う長方形の総面積を見つけるためにここで提案されているラインスイープアルゴリズムの単純な拡張です。

直方体ごとに、イベントキューの左右のx座標を追加し、キューを並べ替えます。次に、直方体を介してyz平面（一定のx値を持つ）をスイープし、イベントキュー内の任意の2つの連続するイベント間のボリュームを記録します。これを行うには、任意の段階で平面と交差する長方形のリストを維持します。

飛行機を掃引すると、次の2種類のイベントが発生します。

（1）掃引平面と交差し始める新しい直方体の始まりがわかります。この場合、新しい長方形が平面と交差し、スイープ平面と交差する長方形の領域を更新します。

（2）平面と交差していた既存の直方体の端。この場合、現在平面と交差している長方形のリストから対応する長方形を削除し、結果の長方形の新しい領域を更新する必要があります。

任意の2つの連続するイベントqiとqi + 1の間の直方体の体積は、 2つのイベント間の水平距離にqiでスイープラインと交差する長方形の面積を掛けたものに等しくなります。

長方形の面積を計算するためのO（nlogn）アルゴリズムをサブルーチンとして使用することにより、直方体の総体積を計算するためのO（n 2 logn）アルゴリズムを取得できます。ただし、（どの段階でも長方形を追加または削除するだけなので）より効率的な長方形を維持するためのより良い方法があるかもしれません。

于 2012-10-07T16:48:37.247 に答える
3

それぞれが処理されるときに、交差しない直方体のコレクションを維持するのはどうですか？

このコレクションは空で始まります。

最初の直方体がコレクションに追加されます。これが唯一の要素であるため、他のものと交差しないことが保証されます。

2番目以降の直方体は、コレクション内の要素に対してチェックされます。新しい直方体Nごとに、すでにコレクションに含まれている要素Eごとに：

  • NがEに完全に含まれている場合は、 Nを破棄し、次の新しい直方体で処理を再開します。
  • Nに完全にEが含まれている場合は、コレクションからEを削除し、コレクション内の他の要素に対してNのテストを続行します。
  • NがEと交差する場合は、 Nを最大5つ（以下のコメントを参照）の小さな直方体に分割し（交差する方法によって異なります）、交差しないボリュームを表し、コレクション内の他の要素に対してこれらの小さな直方体のテストを続行します。

Nから生成された1つまたは複数の直方体（以前の直方体のいずれにも含まれていなかったNによって提供されたボリュームを表す）を使用して、交差しない要素に対するテストが終了したら、それらすべてをコレクションとプロセスに追加します。次の直方体。

すべての直方体が処理されると、合計ボリュームは、構築された交差しない直方体のコレクション内のボリュームの合計になります。

于 2012-10-07T17:30:03.960 に答える
0

最近同じ問題が発生し、次のアプローチを実装してn次元で機能するのが簡単であることがわかりました。

最初にグリッドを作成し、次にグリッド内の各セルが直方体と重なっているかどうかを確認します。重なり合う直方体の体積は、1つまたは複数の直方体に含まれるセルの体積の合計です。

  • 各次元の最小/最大値で直方体を説明します。
  • 次元ごとに、各直方体の最小値/最大値を配列に格納します。この配列を並べ替えて、重複を削除します。
  • これで、非等距離グリッドのグリッドポイントができました。グリッドの各セルは、完全に1つ以上の直方体の内側にあるかどうかのいずれかです。
  • グリッドセルを反復処理し、1つまたは複数の直方体と重なるセルの体積をカウントします。

デカルト積を使用すると、すべてのグリッドセルを取得できます。

于 2019-02-16T11:33:46.773 に答える
0

@ccssmnnによって提案されたセルラーアプローチを試しました。それは機能しましたが、遅すぎました。問題は、「各次元について、配列内の各直方体の最小値/最大値を格納する」ために使用される配列のサイズです。はO(n)、であるため、セルの数（したがって、実行時間）はn^d、たとえばn^33次元の場合です。

次に、@ krjampaniが提案したように、ネストされたスイープラインアルゴリズムを試しました。はるかに高速ですが、それでも遅すぎます。複雑さはn^2*log^3(n)。

だから今、私は何か頼りがあるかどうか疑問に思っています。interval treesまたはの使用について言及しているいくつかの投稿を読みましたaugmented interval trees。このアプローチの方が複雑である可能性がありn*log^3(n)ますか？

また、私はこの場合の増強値が何であるかについて頭を悩ませようとしていますか？ポイントクエリまたは範囲クエリの場合、直方体をそれら(xlo,ylo,zlo)で並べ替え、各サブツリーを拡張値として使用max(xhi,yhi,zhi)することはできますが、これを拡張して直方体とそのボリュームの結合を追跡する方法がわかりません。

于 2019-10-31T15:55:57.750 に答える