詳解 OpenCV 3 ―コンピュータビジョンライブラリを使った画像処理・認識

付録A平面分割

A.1　ドロネー三角形分割、ボロノイ分割

ドロネー（Delaunay）三角形分割法は、1934年に発明されたもので、空間内の点を連結して三角形のグループにし、その三角形のすべての角の最小角度が最大になるようにする技術です［Delaunay34］。これは、ドロネー三角形分割法が点を三角形分割するときに、細長い三角形ができないようにしているということです。三角形分割の要点を理解するために図A-1を見てください。これにより与えられた任意の三角形の頂点に接する任意の円の内部には、その他の頂点が含まれないようにして三角形分割が行われています。これは、外接円特性と呼ばれています（図のパネルc）。

図A-1　ドロネー三角形分割法。（a）点の集合。（b）点の集合のドロネー三角形分割。外側を囲む三角形の頂点につながる線を持つ。（c）外接円特性を示す円の例

計算効率のために、ドロネーアルゴリズムは、かなり離れた外側に三角形を作り、そこからアルゴリズムを始めます。図A-1（b）はこの架空の外側の三角形を、その頂点に向かう点線で表しています。図A-1（c）は外接円特性の例を示しています。円のうちの1つは、実データの外側の2つの点と、架空の外側の三角形の頂点の1つに外接しています（右下の隅にある円弧）です。

今日、ドロネー三角形分割を計算するアルゴリズムはたくさんあります。そのいくつかは非常に効率的ですが、内部の詳細は難解です。比較的簡単なアルゴリズムの要点は次のとおりです。