平面細分割.
平面細分割とは,重複しない小領域(細分割面)で全平面を細分化することです.上記の構造体は2次元の点集合によって細分割を表現しており,その点集合の点は互いに連結され,平面グラフを構成します.このグラフは,無限遠にある外部細分割点(通常は,凸包点)と接続する少数の辺をもち,その辺によって平面を小領域に分割していきます.
全ての細分割に対して,その面と点(細分割頂点)の役割を入れ替えた双対細分割が存在します.つまり,双対細分割では,面は頂点として扱われ(以下では,仮想点と呼ぶ),元の再分割の頂点は面として扱われます.以下の図では,元の細分割が実線で,双対細分割が点線で表されています.
OpenCVでは,ドロネーのアルゴリズムを用いて平面を三角形に細分化します.細分割は,確実に全ての細分点を含む仮想の三角形から開始される反復計算により行われます.この場合,双対細分割は入力2次元点集合に対するボロノイ図となります.この細分割は,平面の3次元区分変換やモーフィング,平面上の点の高速な位置同定,特殊なグラフ(NNGやRNG)の生成などに利用できます.
細分割または双対細分割における頂点.
- first¶
- 接続される CvSubdiv2DEdge
- pt¶
- 位置, CvPoint2D32f
ボロノイ図のセルの座標を求めます.
Parameter: | subdiv (CvSubdiv2D) – 既にすべての点を含む,ドロネー細分割 |
---|
この関数は,仮想点の座標を計算します.元の細分割の頂点に対応する全ての仮想点は,(互いに接続され)その点におけるボロノイ図のセルの境界を形成します.
全ての仮想点を削除します.
Parameter: | subdiv (CvSubdiv2D) – ドロネー細分割 |
---|
この関数は,全ての仮想点を削除します.前回の関数呼び出し後に,再分割が変更されていた場合に,関数 CalcSubdivVoronoi2D の内部で呼ばれます.
空のドロネー三角形を作成します.
パラメタ: |
|
---|
この関数は,空のドロネー細分割を作成します.ここに2次元点を追加するには,関数 SubdivDelaunay2DInsert を利用します.追加される全ての点は,引数で指定された矩形内に存在しなければならず,そうでない場合はランタイムエラーが発生します.
三角形分割の結果として,与えられた矩形を覆う1つの大きな三角形が作成されることに注意してください.したがって,この三角形の3つの頂点は rect の外側に存在します.
与えられた点に最も近い細分割の頂点を求めます.
パラメタ: |
|
---|
この関数は,入力点が再分割内のどこに位置するかを求める,もう一つの関数です.これは,入力点にもっとも近い再分割の頂点を見つけます.入力点を含む分割面は(関数 Subdiv2DLocate によって求められ)開始点として利用されますが,その分割面の頂点が最も近い頂点とは限りません.この関数は,見つかった再分割頂点へのポインタを返します.
辺の終点を返します.
Parameter: | edge (CvSubdiv2DEdge) – 再分割の辺(quad-edgeではありません) |
---|
この関数は,辺の終点を返します.入力辺が双対細分割のものであり,仮想点の座標がまだ計算されていない場合,戻り値であるポインタはNULLになる場合があります.この仮想点は,関数 CalcSubdivVoronoi2D を用いて計算することが可能です.
与えられた辺に関連する辺の1つを返します.
パラメタ: |
|
---|
この関数は,入力辺に関連する辺の1つを返します.
Returns next edge around the edge origin
Parameter: | edge (CvSubdiv2DEdge) – Subdivision edge (not a quad-edge) |
---|
The function returns the next edge around the edge origin: eOnext on the picture above if e is the input edge)
ドロネーの三角形内に存在する点の位置を返します.
パラメタ: |
|
---|
この関数は,入力点が再分割においてどこに位置するかを求めます.ここでは,5つのケースが考えられます:
同じ quad-edge にある別の辺を返します.
パラメタ: |
|
---|
この関数は,入力辺と同じquad-edgeにある別の辺を返します.
ドロネーの三角形に1つの点を追加します.
パラメタ: |
|
---|
この関数は,再分割結果に1つの点を追加し,再分割のトポロジーを適切に変更します.もし,既に同じ座標に点が存在していた場合は,点の新規追加は行われません.この関数は,メモリ確保した追加点へのポインタを返します. この段階では,仮想点座標の計算は行われません.