3次元凸包

3次元凸包

S={P_1, P_2,\cdots, P_n}という点が3次元空間に点在しているとします。
またP_iの座標は(x_i, y_i, z_i)という風に指定します。
ここで、「Sの凸包C(S)を求めよう」というのが今回の主題です。

点の数が多い-つまりnの数が多い-ことを想定して、分割統治法による解法を試みます。
1)Sをx座標の大きいTとx座標の小さいUに分割します。
2)それぞれTUについて、再帰的に凸法を作ります。
3)それらを統合します。

さて、1)2)のプロセスはいいでしょう。問題は3)のプロセス-つまり、分割した凸包をどうくっつけて凸包にするか-です。

3次元凸包の統合

用語の定義をしましょう。図を見てもらうと棒人間が立っています。この人が色々な頂点から向こう側の3次元凸包を観察してみることができる三角形を灰色に塗りました。
言い換えれば、反対側の凸包からみて「オモテ側」の三角形ですね。
このオモテとウラの境目(図で赤い点線にしたところです。)をシルエットサイクルと呼ぶことにします。

これら2つの三次元凸包を統合したくば、「片方の凸包のシルエットサイクルに属す頂点」と「もう片方の凸包のシルエットサイクルに属す辺」で三角形をつくります。
こいつを接着剤代わりにして2つの凸包を繋ぐのです。この三角形を橋渡し三角形と言います。
ということで3次元凸包は結局橋渡し三角形を見つける問題に帰着されるわけです。

javascript plugin Error : このプラグインで利用できない命令または文字列が入っています。
最終更新:2012年10月24日 09:39
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。
添付ファイル