ドロネーの三角形分割

ドロネーの三角形分割は、いかなる三角形の外接円も他の点を内包しない性質を持つ分割の仕方である.この図はドロネー図とも呼ぶ. ドロネー図の三角形の特徴 ・どの隣接する三角形を統合してもその外周は凸包となる. ・三角形の3つの角度の最小値が最大になるような分割を行う.(あまりに高さのない細い三角形を防ぐ) ・ポアソン過程によってばらまかれている点では平均6つの三角形に一つの点は隣接する. ・ドロネー図の三角形の中心を結ぶとボロノイ図

ドロネー図では、二つの隣接した下のような三角形を見たときに、共通の辺に接していないαとγの角度の合計は180度より小さくなることが知られています. このとき、辺を直行する方向に結び直すとドロネー図の三角形の条件を満たすようになります. この操作をFlip処理と言います.

Flipによるドロネー三角形分割は非常に単純になっています. 1. まず適当に三角形分割を行う. 2. 以下の図の要領でドロネーの三角形の条件(外接円に他の点を含まない)を守っていない三角形に対して、上記Flip処理を行う. 時間計算量としては点の数をnとして、O(n^2)となってしまいます.

与えられた点群を二つに分割していき、二点ずつ統合していく方法による分割統治法のドロネー三角形分割. O(n log(n))の時間計算量になり早いことが知られる.