三角形分割

tessellation.png

デローニー三角形分割のウェブアプレットのあるサイト

閲覧には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

三角形分割に関する書籍


http://i-health.u-aizu.ac.jp/CompuGeo/ 会津大学の計算機科学の授業の資料。↓の本が参考にしてあってわかりやすい。
なかったら2008年のところを見るべし
コンピュータジオメトリ計算幾何学 アルゴリズムと応用を読む
論文Improving worst case optimal Delauney Triangulation algorithmの解読Delauney Triangulation Web applet のページの人の論文

三角形分割に必要な幾何演算

外接円の求め方 
この点は円の中にあるかどうか?
放物線の描き方
二つの放物線の交点の軌跡
三角形と直線の交差判定
三角形と三角形の交差判定

三角形分割とは

有限要素法1

色々な2次元メッシュ生成法

格子パターンマッピング 再帰的分割 外枠からの要素構成 格子点を優先した手法(デローニー三角メッシュ生成法Delaunay triangulation)
局部的に要素の大きさを制限することが難しい。 局部的に要素の大きさを制限することが難しい。 領域中心付近で歪みが生じやすい。(外側から作るんなら、地形の生成に向いてるかな?) 凹部や穴をもつ多角形のメッシュ生成が容易である.また,要素の大きさの制御性や,要素の歪みについては,要素頂点の生成手法に大きく依存する.
凹部や穴を含む多角形での自動化が難しい。 凹部や穴を含む多角形での自動化が難しい。 ボロノイ領域とか使うらしい。与えられた頂点要素に対して最も歪みの少ないメッシュを作成することが出来る。
pm.png r.png a.png k.pngdelainay.png

点の数に対して出来る三角形の個数

点の数nとして、
kを外側に位置している点の個数とすると

2n-2-k

個の三角形が結果として出来ます。
つまり、内側に点が無かった場合

n-2個の三角形です。※凸包に限る


computational-geometry

サポートサイト Wikidot.com computational-geometry