「3次元凸包」の編集履歴（バックアップ）一覧はこちら
「3次元凸包」(2012/10/24 (水) 09:39:14) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
**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)それぞれ$$T$$と$$U$$について、再帰的に凸法を作ります。
3)それらを統合します。
さて、1)2)のプロセスはいいでしょう。問題は3)のプロセス－つまり、分割した凸包をどうくっつけて凸包にするか－です。
**3次元凸包の統合
#image(http://www58.atwiki.jp/dooooornob/?cmd=upload&act=open&page=3%E6%AC%A1%E5%85%83%E5%87%B8%E5%8C%85&file=3Ddro.png)
用語の定義をしましょう。図を見てもらうと棒人間が立っています。この人が色々な頂点から向こう側の3次元凸包を観察してみることができる三角形を灰色に塗りました。
言い換えれば、反対側の凸包からみて「オモテ側」の三角形ですね。
このオモテとウラの境目（図で赤い点線にしたところです。）を&bold(){シルエットサイクル}と呼ぶことにします。
これら2つの三次元凸包を統合したくば、「片方の凸包のシルエットサイクルに属す頂点」と「もう片方の凸包のシルエットサイクルに属す辺」で三角形をつくります。
こいつを接着剤代わりにして２つの凸包を繋ぐのです。この三角形を&bold(){橋渡し三角形}と言います。
ということで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)それぞれ$$T$$と$$U$$について、再帰的に凸法を作ります。
3)それらを統合します。
さて、1)2)のプロセスはいいでしょう。問題は3)のプロセス－つまり、分割した凸包をどうくっつけて凸包にするか－です。
**3次元凸包の統合
#image(http://www58.atwiki.jp/dooooornob/?cmd=upload&act=open&page=3%E6%AC%A1%E5%85%83%E5%87%B8%E5%8C%85&file=3Ddro.png)
用語の定義をしましょう。図を見てもらうと棒人間が立っています。この人が色々な頂点から向こう側の3次元凸包を観察してみることができる三角形を灰色に塗りました。
言い換えれば、反対側の凸包からみて「オモテ側」の三角形ですね。
このオモテとウラの境目（図で赤い点線にしたところです。）を&bold(){シルエットサイクル}と呼ぶことにします。
これら2つの三次元凸包を統合したくば、「片方の凸包のシルエットサイクルに属す頂点」と「もう片方の凸包のシルエットサイクルに属す辺」で三角形をつくります。
こいつを接着剤代わりにして２つの凸包を繋ぐのです。この三角形を&bold(){橋渡し三角形}と言います。
ということで3次元凸包は結局橋渡し三角形を見つける問題に帰着されるわけです。
#javascript(){{
<!-- admax -->
<script type="text/javascript" src="http://adm.shinobi.jp/s/2378325e5782e4336b0932b16cb17597"></script>
<!-- admax -->
}}
