多角形の三角形分割
多角形の三角形分割（たかっけいのさんかっけいぶんかつ）は計算幾何学の分野で用いられる、（単連結な）多角形の領域Pの三角形の集合への分割である[1]。つまり、和集合がPである互いに重なり合わない三角形の集合の発見法である。
三角形分割は平面直線グラフの特殊な場合としてみなせる。穴のない図形の頂点のみを用いた三角形分割は、外平面的グラフである。
追加点を用いない多角形の三角形分割
多角形の三角形分割アルゴリズムは多数提案されている。
特別な場合
ある頂点から伸びる全ての対角線により凸多角形は扇形分割され、これは三角形分割であるため、線形時間で三角形分割が可能である。
レオンハルト・オイラーによって、凸n角形の三角形分割の組合せの数は、交差しない対角線の数であり、(n − 2)番目のカタラン数、つまり[2]。
アラン=フルニエとD.Y. Montunoによって、単調多角形は、線形時間で三角形分割可能であることが示された[3]。Godfried Toussaintのアルゴリズムによっても線形時間で三角形分割可能である[4]。
耳刈り取り法
単調多角形を三角形分割する手法はtwo ears theoremに基づくものである。この定理は、4本以上の辺を持つ穴のない単純多角形は少なくとも2つの「耳（2辺が多角形の辺であり、残り1辺が多角形の内部に存在する三角形）」を持つという定理である[5]。このアルゴリズムはこの「耳」を見つけ、その三角形を多角形から順に取り除くことで三角形分割を行う。
このアルゴリズムは実装が容易であるが他のアルゴリズムより遅く、穴を持たない多角形でしか動作しない。凸である頂点と凹である頂点を別のリストとして持つ実装の時間計算量はO(n2)である。この方法は耳刈り取り法もしくは耳取り除き法として知られるアルゴリズムで、Hossam ElGindy、Hazel Everett、Godfried Toussaintにより発見された[6]。
単調多角形による三角形分割
単純多角形の場合は以下のように単調多角形に分割できる。
各点について、隣り合う点が掃引線の同じ側にあるか、つまり「水平線や鉛直線を引いた場合に同じ側にあるかどうか」を確認する。もし同じ側にあれば掃引線を延長し、多角形と交差した点の辺の端点の内「違う側」の点間の線分で分割する。この処理を繰り返す。
（水平な）掃引線を下へと動かす場合に、両方の頂点が掃引線の上側にあり、下の図形が分割される場合がある。この場合、これから探索する図形が分割され、三角形分割のためにはそれぞれの図形に対して上記の処理を繰り返す必要がある。
このアルゴリズムを用いることで、単純多角形の三角形分割は
- 多角形の三角形分割のページへのリンク
