点群を三角形群にする方法

points-to-triangles.png

たくさんの点データから三角形群を作って、面を作るにはどうしたらよいのか?という話。
ここでいう、点とは(x,y,z)の座標の値を持ったものの羅列データのこと。
まとめ動画です。

ソースコード(git)

アルゴリズム

  1. すべての点を包括する大きな三角形で初期化する
  2. 最初の一点、なるべく真ん中で1回分割する
  3. 一つの三角形を分割したら、3つの子三角形ができると思う。それについて各々以下のような作業をする
  4. その三角形を外接円に他の点が入っていないかどうか確認する
  5. もし、他の点が外接円に入っていたら、その点で三角形を再分割する(参照:円の中に点があるかどうかの判定する方法)
  6. この作業を再帰的に繰り返す

参考文献

閲覧にはIEがおすすめ!
http://wonderfl.net/c/t0iX wonderFl buld online
http://goanna.cs.rmit.edu.au/~gl/research/comp_geom/delaunay/delaunay.html ←これはワンステップずつ見れて最高。
http://www.cse.unsw.edu.au/~lambert/java/3d/delaunay.html

参考にした本

コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用


delaunay

サポートサイト Wikidot.com delaunay