第 4 章 使用する LS 18
5.3 Convexhull
次に、Convexhullの実装についてを述べる。本研究では、３次元空間上における
Con-vexhullを表現する要素として、
• 頂点
• 辺
• 面(ファセット)
を規定する。これらはそれぞれ、リストで管理する。3次元空間上におけるConvexhullを 作成するアルゴリズム[6]を参考に、3次元空間上における点集合を入力とし、その点集 合に対するConvexhullを作成するjavaプログラムの作成を行った。3次元空間上におけ るConvexhullを作成するアルゴリズムをAlgorithm 1に示す。また、上記に述べた頂点、
辺、面のデータ構造としては、Apache Commons Mathライブラリ[10]を使用し表現し た。最終的に、計算が行われ全ての点、辺、ファセットが入ったConvexhullが出力され るが、出力されたConvexhullを可視化するために、Convexhullを.plyファイルに書き落 とす機能もつけ、Convexhullの可視化についても実装を行った。本研究では作成した.ply ファイルの可視化ツールとして、Meshlab[11]を用いた。
5.3.1 Convexhull 同士の和集合
統合処理で２つのConvexhullの共通部分を算出するために、２つのConvexhullの共通 部分を算出して１つのConvexhullを導出するプログラムの実装を行った。5.3節で実装
したConvexhullを作成するjavaプログラムは、頂点の集合を入力すればそれらに対する
Convexhullを作成してくれるため、共通部分のConvexhullの作成にはこのプログラムを
∩
Algorithm 1Calculate Convexhull(3D) Require: 3次元空間におけるn点の集合P Ensure: PのConvexhull:CH(P)
1: ４面体を構成するPの４点p1, p2, p3, p4を求める。
2: C ←CH(p1, p2, p3, p4)
3: 残りの点のランダムな順列p5, p6, ..., pnを求める。
4: 全ての可視点対(pt,f)を求めて衝突グラフgを初期化する。ただし、fはCのファセッ ト(面）であり、t >4である。
5: for r ←5 to n do
6: {(*prをCに挿入する:*)}
7: if Fconf lict(pr)は空でない{(∗すなわち、prはCの外にある∗)} then
8: Fconf lict(pr)のファセットを全てCから削除する
9: prから見える領域の境界を順に辿り(その領域はFconf lict(pr)のファセットから構 成されている)地平面の辺のリストLを順に作る
10: for すべてのe∈L do
11: 三角形のファセットfを作ることによりeをprにつなぐ
12: if fがeに沿った近傍のファセットと同一平面にある then
13: fとf’を1つのファセットに統合する。ただし、その衝突リストはf’のもの と同じである。
14: else
15: {(*fの衝突リストを定める:*)}
16: gにfに対する節点を作る。
17: f1とf2を元のConvexhullでeに接していたファセットとする。
18: P(e)←Pconf lict(f1)∪Pconf lict(f2)
19: for 全ての点p∈P(e)do
20: fがpから見えるなら、(p,f)をgに加える。
21: end for
22: end if
23: end for
24: prに対応する節点とFconf lict(pr)のファセットに対応する接点をそれらに接続す る枝とともにgから削除する。
25: end if
26: end for
27: return C
のConvexhullと捉えた時、このConvexhullの頂点はAの頂点のうちBの内部にあるも の、Aの辺とBのファセットの交点、同様にBの頂点のうちAの内部にあるもの、Bの 辺とAのファセットの交点で構成される。なので、２つのConvexhullを入力とし、これ らの頂点を計算し出力した後、この頂点を入力とし5.3節で作成したjavaプログラムで計 算を行わせれば、２つのConvexhull A,Bにおける共通部分(A∩B)をのConvexhullが導 出される。2つのConvexhull A,Bにおいて、和集合をとったConvexhullを図5.1に示す。
図 5.1: Convexhullの和集合を取った様子
5.3.2 Convexhull 同士の差集合
同様に統合処理で２つのConvexhullの差集合を算出する必要がある。これにおいても 5.3節で実装したjavaプログラムを用いて行う。２つのConvexhullをA,Bにおいて、Aか らBの部分を引いた(A\B)Convexhullの頂点は、Aの頂点のうちBの内部にないもの、
Aの辺とBのファセットの交点、Bの頂点のうちAの内部にあるもの、Bの辺とAのファ セットの交点で構成される。そのため同様に２つのConvexhullを入力とし、これらの頂 点を計算し出力した後、この頂点を入力とし5.3節で作成したjavaプログラムで計算を行 わせれば、２つのConvexhull A,Bにおける差集合(A\B)のConvexhullが導出される。
2つのConvexhull A,Bにおいて、差集合をとったConvexhullを図5.2に示す。図5.2は、
集合を取ったConvexhull (A\B)(黄色のConvexhull)を示している。ただし、差集合にお いては凹面を持つものも存在するが、差集合の立体を構成する頂点を与えてConvexhull を計算した場合、Convexhullの定義上、凹面の部分が埋め合わされて凸面となった立体 となるため、差集合のConvexhullにおいては、厳密な差集合を作成できるとは限らない 場合も存在する。
図 5.2: Convexhullの差集合を取った様子