昔，モデルビューアのまねごとみたいなソフトを作ったときについでにつくった
のを思い出してつくってみた．
アルゴリズムは，以下の流れ．
１．もっとも原点から遠い頂点を探す．
２．その頂点の両隣の頂点からなる三角形の外積ベクトルの方向を保存する．
３．その頂点と，その両隣の頂点からなる三角形の内部に他の頂点があるかを調べる．
４．もし内部に頂点がなければ，その頂点とその両隣の頂点からなる三角形を分割要素
　　として，その頂点を削除し，１に戻る．
５．頂点が内部にある場合は，隣の頂点に移動する
６．移動先の頂点と，その両隣の頂点からなる三角形の外積ベクトルの方向を計算し，
　　２．で求めた外積ベクトルと同じ方向かをチェック．
７．もし同じ方向であれば，その頂点と，その両隣の頂点からなる三角形の内部に他
　　の頂点があるかを調べる．内部になければ，その頂点とその両隣の頂点からなる
　　三角形を分割要素として，その頂点を削除し，１に戻る．
８．もし異なる方向であれば，あるいは内部に他の頂点がある場合は，５．に戻る．

Screenshot_2.png

これで，任意の非凸多角形を三角形に分割できる．
多角形の中でも原点からもっとも遠い距離にある頂点は，凸角を構成するという性質を利用している．
※これを3次元に展開するとどうなるだろうか・・．
本ソースコードを使用したことによる如何なる損害も製作者は責任を負いません．
http://code.google.com/p/sonson-code/source/browse/#svn/trunk/src/polygon