ドロネー三角形分割Delaunay triangulation 定義 : (一般の)三角形分割 2次元平面にN個の点群P={pi |pi ∊ R2}が与えられた時,Pの凸包の内部を,Pに属する点群を頂点とする三角形で分割した図形で,どの三角形も頂点以外にPに属する点を含まないもの. 定義 : ドロネー三角形分割 2次元平面にN個の点群P={pi |pi ∊ R2}の三角形分割の内,任意の三角形の外接円の内部にPに属する点を含まないもの.4点以上の点が同一円周上る場合,ある三角形の外接円上に,三角形を構成する頂点以外のPに属する点が乗る場合がある[1]. 制約なしドロネー分割---(逐次加点法) 既にドロネー三角形分割がなされている図形を仮定し,それに新たな点を追加する.この時,追加する点を含む三角形を分割し,ドロネー三角形分割の性質が保たれるようにEdge Flipを繰り返す. A1) 点