平面細分割

CvSubdiv2D

CvSubdiv2D

平面細分割．

#define CV_SUBDIV2D_FIELDS()    \
    CV_GRAPH_FIELDS()           \
    int  quad_edges;            \
    int  is_geometry_valid;     \
    CvSubdiv2DEdge recent_edge; \
    CvPoint2D32f  topleft;      \
    CvPoint2D32f  bottomright;

typedef struct CvSubdiv2D
{
    CV_SUBDIV2D_FIELDS()
}
CvSubdiv2D;

平面細分割とは，重複しない小領域（細分割面）で全平面を細分化することです．上記の構造体は2次元の点集合によって細分割を表現しており，その点集合の点は互いに連結され，平面グラフを構成します．このグラフは，無限遠にある外部細分割点（通常は，凸包点）と接続する少数の辺をもち，その辺によって平面を小領域に分割していきます．

全ての細分割に対して，その面と点（細分割頂点）の役割を入れ替えた双対細分割が存在します．つまり，双対細分割では，面は頂点として扱われ（以下では，仮想点と呼ぶ），元の再分割の頂点は面として扱われます．以下の図では，元の細分割が実線で，双対細分割が点線で表されています．

OpenCVでは，ドロネーのアルゴリズムを用いて平面を三角形に細分化します．細分割は，確実に全ての細分点を含む仮想の三角形から開始される反復計算により行われます．この場合，双対細分割は入力2次元点集合に対するボロノイ図となります．この細分割は，平面の3次元区分変換やモーフィング，平面上の点の高速な位置同定，特殊なグラフ（NNGやRNG）の生成などに利用できます．

CvQuadEdge2D

CvQuadEdge2D

平面細分割の Quad-edge．

/* 4 辺の内の 1 つ．下位 2 ビットはインデックス（ 0...3 ）で
   上位ビットは4辺へのポインタ */
typedef long CvSubdiv2DEdge;

/* Quad-edge 構造体フィールド */
#define CV_QUADEDGE2D_FIELDS()     \
    int flags;                     \
    struct CvSubdiv2DPoint* pt[4]; \
    CvSubdiv2DEdge  next[4];

typedef struct CvQuadEdge2D
{
    CV_QUADEDGE2D_FIELDS()
}
CvQuadEdge2D;

Quad-edgeは，4辺（e，eRot，eの反転，eRotの反転）から成る平面細分割の基本要素です．

CvSubdiv2DPoint

CvSubdiv2DPoint

細分割または双対細分割における頂点．

#define CV_SUBDIV2D_POINT_FIELDS()\
    int            flags;      \
    CvSubdiv2DEdge first;      \
    CvPoint2D32f   pt;         \
    int id;

#define CV_SUBDIV2D_VIRTUAL_POINT_FLAG (1 << 30)

typedef struct CvSubdiv2DPoint
{
    CV_SUBDIV2D_POINT_FIELDS()
}
CvSubdiv2DPoint;

• id

  この整数値は，平面細分割の各頂点に関する補助的なデータのインデックスを表すのに用いられます

cv::CalcSubdivVoronoi2D

void cvCalcSubdivVoronoi2D(CvSubdiv2D* subdiv)

ボロノイ図のセルの座標を求めます．

Parameter:subdiv – 既にすべての点を含む，ドロネー細分割

この関数は，仮想点の座標を計算します．元の細分割の頂点に対応する全ての仮想点は，（互いに接続され）その点におけるボロノイ図のセルの境界を形成します．

cv::ClearSubdivVoronoi2D

void cvClearSubdivVoronoi2D(CvSubdiv2D* subdiv)

全ての仮想点を削除します．

Parameter:subdiv – ドロネー細分割

この関数は，全ての仮想点を削除します．前回の関数呼び出し後に，再分割が変更されていた場合に，関数 CalcSubdivVoronoi2D の内部で呼ばれます．

cv::CreateSubdivDelaunay2D

CvSubdiv2D* cvCreateSubdivDelaunay2D(CvRect rect, CvMemStorage* storage)

空のドロネー三角形を作成します．

パラメタ:

• rect – 細分割に追加される全ての2次元点を含む矩形
• storage – 細分割結果を保存するストレージ

この関数は，空のドロネー細分割を作成します．ここに2次元点を追加するには，関数 SubdivDelaunay2DInsert を利用します．追加される全ての点は，引数で指定された矩形内に存在しなければならず，そうでない場合はランタイムエラーが発生します．

三角形分割の結果として，与えられた矩形を覆う1つの大きな三角形が作成されることに注意してください．したがって，この三角形の3つの頂点は rect の外側に存在します．

cv::FindNearestPoint2D

CvSubdiv2DPoint* cvFindNearestPoint2D(CvSubdiv2D* subdiv, CvPoint2D32f pt)

与えられた点に最も近い細分割の頂点を求めます．

パラメタ:

• subdiv – ドロネー再分割，あるいはその他の細分割
• pt – 入力座標点

この関数は，入力点が再分割内のどこに位置するかを求める，もう一つの関数です．これは，入力点にもっとも近い再分割の頂点を見つけます．入力点を含む分割面は（関数 Subdiv2DLocate によって求められ）開始点として利用されますが，その分割面の頂点が最も近い頂点とは限りません．この関数は，見つかった再分割頂点へのポインタを返します．

cv::Subdiv2DEdgeDst

CvSubdiv2DPoint* cvSubdiv2DEdgeDst(CvSubdiv2DEdge edge)

辺の終点を返します．

Parameter:edge – 再分割の辺（quad-edgeではありません）

この関数は，辺の終点を返します．入力辺が双対細分割のものであり，仮想点の座標がまだ計算されていない場合，戻り値であるポインタはNULLになる場合があります．この仮想点は，関数 CalcSubdivVoronoi2D を用いて計算することが可能です．

cv::Subdiv2DGetEdge

CvSubdiv2DEdge cvSubdiv2DGetEdge(CvSubdiv2DEdge edge, CvNextEdgeType type)

与えられた辺に関連する辺の1つを返します．

パラメタ:

• edge – 再分割の辺（quad-edgeではありません）
• type –

  関連する辺の内，どの辺を返すかの指定．以下から1つ：

  • CV_NEXT_AROUND_ORG 入力辺の始点周りの辺を見た場合の，入力辺の次にある辺（下図で e を入力辺とした場合の eOnext ）
  • CV_NEXT_AROUND_DST 入力辺の終点周りの辺を見た場合の，入力辺の次にある辺（下図で e を入力辺とした場合の eDnext ）
  • CV_PREV_AROUND_ORG 入力辺の始点周りの辺を見た場合の，入力辺の前にある辺（下図で e を入力辺とした場合の eRnext ）
  • CV_PREV_AROUND_DST 入力辺の終点周りの辺を見た場合の，入力辺の前にある辺（下図で e を入力辺とした場合の eLnext ）
  • CV_NEXT_AROUND_LEFT 左の面周りの辺を見た場合の，入力辺の次にある辺（下図で e を入力辺とした場合の eLnext ）
  • CV_NEXT_AROUND_RIGHT 右の面周りの辺を見た場合の，入力辺の次にある辺（下図で e を入力辺とした場合の eRnext ）
  • CV_PREV_AROUND_LEFT 左の面周りの辺を見た場合の，入力辺の前にある辺（下図で e を入力辺とした場合の eOnext ）
  • CV_PREV_AROUND_RIGHT 右の面周りの辺を見た場合の，入力辺の前にある辺（下図で e を入力辺とした場合の eDnext ）

この関数は，入力辺に関連する辺の1つを返します．

cv::Subdiv2DNextEdge

CvSubdiv2DEdge cvSubdiv2DNextEdge(CvSubdiv2DEdge edge)

Returns next edge around the edge origin

Parameter:edge – 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)

cv::Subdiv2DLocate

CvSubdiv2DPointLocation cvSubdiv2DLocate(CvSubdiv2D* subdiv, CvPoint2D32f pt, CvSubdiv2DEdge* edge, CvSubdiv2DPoint** vertex=NULL)

ドロネーの三角形内に存在する点の位置を返します．

パラメタ:

• subdiv – ドロネー再分割，あるいはその他の細分割
• pt – 位置を知りたい点
• edge – 出力される辺．入力点は，この辺上または辺の右側に位置します
• vertex – オプション．入力点と同じ場所にある頂点へのダブルポインタ

この関数は，入力点が再分割においてどこに位置するかを求めます．ここでは，5つのケースが考えられます：

• 入力点は，分割面内に位置します．この関数は， CV_PTLOC_INSIDE を返し， *edge はその分割面の辺の1つになります．
• 入力点は，分割辺上に位置します．この関数は， CV_PTLOC_ON_EDGE を返し， *edge はその辺になります．
• 入力点は，再分割頂点の1つと同じ座標に位置します．この関数は， CV_PTLOC_VERTEX を返し， *vertex はその頂点へのポインタになります．
• 入力点は，再分割の参照矩形の外側に位置します．この関数は， CV_PTLOC_OUTSIDE_RECT を返し，ポインタには何も入りません．
• 引数のいずれかが無効．ランタイムエラーが起こるか，エラーハンドリングモードが silent あるいは parent である場合は， CV_PTLOC_ERROR が返ります．

cv::Subdiv2DRotateEdge

CvSubdiv2DEdge cvSubdiv2DRotateEdge(CvSubdiv2DEdge edge, int rotate)

同じ quad-edge にある別の辺を返します．

パラメタ:

• edge – 再分割の辺（quad-edgeではありません）
• rotate –

  同じquad-edgeにある辺の内，どの辺を返すかの指定．以下から1つ：

  • 0 入力辺（下図で e を入力辺とした場合の e 自身）
  • 1 回転した辺（下図で e を入力辺とした場合の eRot ）
  • 2 反転した辺（下図で e を入力辺とした場合の e を反転した（緑で表現された）辺）
  • 3 回転した辺をさらに反転した辺（下図で e を入力辺とした場合の eRot を反転した（緑で表現された）辺）

この関数は，入力辺と同じquad-edgeにある別の辺を返します．

cv::SubdivDelaunay2DInsert

CvSubdiv2DPoint* cvSubdivDelaunay2DInsert(CvSubdiv2D* subdiv, CvPoint2D32f pt)

ドロネーの三角形に1つの点を追加します．

パラメタ:

• subdiv – 関数 CreateSubdivDelaunay2D によって作成されたドロネー細分割
• pt – 追加される座標点

この関数は，再分割結果に1つの点を追加し，再分割のトポロジーを適切に変更します．もし，既に同じ座標に点が存在していた場合は，点の新規追加は行われません．この関数は，メモリ確保した追加点へのポインタを返します． この段階では，仮想点座標の計算は行われません．