Loading article…
計算幾何学において、多面体と直線の交差を計算する問題は、 コンピュータグラフィックス、最適化、さらには一部のモンテカルロ法において重要な応用がある。これは、直線クリッピング問題の3次元バージョンとして考えることができる。[1]
多面体が有限個の半空間の交差として与えられた場合、半空間を 3 つの部分集合に分割することができます。つまり、直線の 1 つの無限端のみを含む部分集合、もう 1 つの端を含む部分集合、および両端を含む部分集合です。両端を含む半空間は、与えられた直線に平行でなければならず、解には寄与しません。他の 2 つの部分集合 (空でない場合) はそれぞれ、交差に単一の端点を寄与します。交差は、直線を各半平面境界面と交差させ、部分集合内の半空間に含まれる直線の端に最も近い交点を選択することで見つけることができます。この方法は、サイラス-ベック アルゴリズムの変形であり、入力多面体の面の数に比例した時間がかかります。あるいは、与えられた多面体の多角形の面のそれぞれに対して直線をテストすることで、直線が貫通する面が見つかったときに検索を早期に停止することができます。[1]
一つの多面体が多数の線と交差する場合、多面体を階層的なデータ構造に前処理して、各クエリ線との交差をクエリごとに対数時間で決定することが可能です。[2]
参考文献
- ^ ab Kolingerová, Ivana (1994)、「3D ラインクリッピングアルゴリズム - 比較研究」、The Visual Computer、11 (2): 96–104、doi :10.1007/BF01889980。
- ^ Dobkin, David P. ; Kirkpatrick, David G. (1983)、「多面体交差の高速検出」、理論計算機科学、27 (3): 241–253、doi : 10.1016/0304-3975(82)90120-7、MR 0731064。
外部リンク
- 疑似コードによる凸包と直線の交差