凹型ポリゴンの三角形分割

小ネタです。

OpenGL では描くのは三角形ベース（モノによっては四角形も使用できる）です。

もしある平面が全体に凸型なのであれば、以下のような組み合わせで頂点を結び、三角形を描いていけば面を埋めることができます。
{0, 1, 2}
{0, 2, 3}
{0, 3, 4}
{0, 1, 5}
・・・

※平面の頂点の番号が0, 1, 2, 3,,,,, と並んでいて、平面に穴が無いことが条件。

しかし凹型の場合は一筋縄ではいきません。で、調べてみると、
http://www.gamedev.net/topic/483457-dividing-concave-polygon-into-convex-ones/
の Dave さんの返答がドンピシャ。

この情報を元にたどり着いたのが以下の2つのページ。
http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Partition_2/Chapter_main.html
http://www.bringyou.to/compgeom/

1つめのリンクはソースを読めばわかると思います。が、自分は2つめでアルゴリズムに納得できたので1つめはよくは見ていません。

さて2つめのリンクの「Hertel-Mehlhorn Algorithm」が肝です。ほぼ直訳ですが、和訳してみましょう。

========================================
(1) 三角形を作っていく。
(2) inessential である辺を除去する。
(3) 以上を繰り返す。

対角線の削除が凹型の面を作るかどうかは
「in constant timeで対角線を囲む辺と弦（？chords）によって」
locallyに行わうことができる。

もしある頂点において内側の角度が180度以上なら、そのポリゴンにおいてその頂点はreflexである。

reflexな頂点を作らない対角線は除去して良い。

対角線dによってつくられる凸型ポリゴンの領域について、
もし対角線dの除去によって「頂点vにおいて凹む領域になる」のなら
対角線dを頂点vに対して "essential" であるという。

dがessentialであるのなら、明らかにそれは頂点vにつながっているはず。
でもって、vはreflex（つまり凹む箇所）あるに違いない。

その対角線がどちらの頂点についても essential でないのなら、"inessential" であるとする。
========================================

書きながら結構書き直しました。図が欲しいヨ！（といいつつ時間が無いので自分も割愛。）

こっからはなんとなくの理解を書いてみます。もしかしたら間違っているかもしれません。

(1) 頂点を結んで三角形を1つ作ってみる。これは端っこからでいいんじゃないかな？原文では任意の箇所となっていたように思います。

(2) その三角形の一辺について
「その辺を除去したら今作った三角形が凹型になってしまう」
のならそこに線をひく。（元の図形の縁については考える必要なし。）

(3) 除去しても凹型にならないならそこには線は引かない。

(4) 以上を繰り返す。

こうするといくつか線を引いた結果、凸型の部屋だけになります。なるはず。

ちなみに穴のあるタイプについても解決できるかについては考えていません。四角形の中に四角形の穴ならできそうですね。蛇腹の中に蛇腹なんかはどうでしょうね。ここらは宿題ということで。

凸型の部屋だけになったら、あとはそれぞれの部屋を三角形に分割していけばいいんですね。なるほど〜。実装についてはリンクを見て下さいね（下の方にソースがあります）。意外と長い。。。

さらに細かい情報が欲しい方は
Approximate convex decomposition of polygons Lien
で検索すると幸せになれます。英語が大丈夫な人限定ですが。