成果物
www.youtube.com
今回は、Quickhullというアルゴリズムを使って、Convex hullの計算の計算を行ってみました。全く同じコードで複数の次元のConvex hullを求めることができるのが特徴です。動画にはありませんが4Dにも対応させています。なぜ4Dが必要かというと、3DのDelaunay Tetrahedralizationで4DのConvex hullを使うからです。Array Sortの設定ミスで丸一日潰れました。
仕組み
2D
まず、最も端にある点から3つを選びます。頂点を結び三角形を作ります。
辺を一つ選び(ここではAB)、最も遠い点(Furthest)を選びます。そして、最も遠い点を法線と同じ側に持つ面をタグ付けします。（法線は重心から外側を向いています）この場合ABとBCがタグ付けされます。タグ付けされた面を削除し、最も遠い点を繋ぐように辺を繋ぎなおしていけば、Convex hullができ上がっていくということがなんとなくわかったでしょうか…
3D
三角形を四面体に置き換え、辺を面に置き換え、点を辺に置き換えいくと、そのまま3Dにも、適応させることができます。実際のコードでは、次元と辺の数の関係を利用し数学的に処理を行っています。
ソールコードにしっかりコメントを書き込んでいるので、ぜひ、動かしながら仕組みをチェックしてみてください。
Quickhullについて解説している他のサイトも合わせてご覧ください。
white-rabbit.jp
コード
ステップ実行のQuickhullStepと、実用向きのQuickhullを追加しています。
github.com
今回は、こちらのUnityのVoronoi生成のプログラムに本当に助けられています。ぜひご覧ください
github.com
