- 同じサイズの A、B、C、D の 4 つのセルに分割された、軸に沿った正方形が与えられます。
- 点 s1 から点 s2 に向かう線分があるとします。
トラバーサル順序でソートされたセグメント (存在する場合) によってトラバースされたセルを見つける最速の方法は何ですか?
上記の例では、正しい結果は次のとおりです。
- セグメント 1 : [D]
- セグメント 2 : [A, B]
- セグメント 3 : [C、D、B]
- セグメント 4 : []
- セグメント 5 : [C]
2 に答える
5
AmanatidesとWooによる「レイトレーシングのための高速ボクセルトラバーサルアルゴリズム」を試すことができます。
これは大きなグリッドを処理することを目的としていますが、この原則はアプリケーションにも役立ちます。
于 2012-12-04T13:38:51.697 に答える
3
以下は、単純な線の交差式のみを使用して実行できます。
グリッドが 6 つの線分 (水平方向に 3 つ、垂直方向に 3 つ) で構成されていることを確認します。これらのセグメントのそれぞれを無限に拡張する場合 (始点または終点のない線にする)、2D 空間を 16 の領域に分割したことになります。
領域の 4x4 配列を定義します。そのような領域ごとに、どの線 (存在する場合) が北側、東側などで区切られているかを格納します。これがトラバーサル データ構造になります。
ここで、u から始まり v で終わる特定のクエリ セグメント S によってトラバースされるセルを見つけるために、このトラバーサル データ構造を使用して u から v までライン ウォークを実行し、現在いるエリアとそのエリアを追跡します。そのエリアを出る場所。
u が位置する領域として Au を、v が位置する領域として Av を決定します。領域の軸に沿った性質のため、領域ごとに 4 回を超える比較は必要ありません (x 座標で 2 回、y 座標で 2 回)。
また、現在の位置を p、現在のエリアを A と定義します。最初は、これらはそれぞれ u と Au です。最初に、S が横断する領域として A を報告します。セグメント * (p, v] と A の 4 つの辺のそれぞれにある区切り線との間の最初の交点を決定します。そのような交点 q が見つかった場合、 q を含む側は、どの隣接領域が新しい A になるかを決定します - その場合、新しい p は交点 q になります. この新しい A と p を使用して、この手順を繰り返します.
交点が見つからない場合、p はv と同じエリアで、ウォークは完了です。
* (p, v] 意味: p を除くが v を含む、p と v の間のセグメント。
于 2012-12-04T21:07:57.213 に答える