制約付きドロネー三角形分割

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