2016/06/20

三角形分割






デモを見る(github.io)

適当にでっち上げた三角形分割と要素技術です。

以下の手順で分割しています。

  1. 凸包を計算。
  2. 凸包の一番上にある点と、凸包の全ての辺との間で三角形を作る。
  3. 凸包内の点を順次追加していく。点が内側にある三角形を見つけたらそれを分割する。
点が三角形の内側にあるかどうかの判定にblackpawnさんのアルゴリズムを利用しました。