平面細分割 =============== .. highlight:: c .. index:: CvSubdiv2D .. _CvSubdiv2D: CvSubdiv2D ---------- `id=0.984935164344 Comments from the Wiki `__ .. ctype:: CvSubdiv2D 平面細分割． .. code-block:: c #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 次元の点集合によって細分割を表現しており，その点集合の点は互いに連結され，平面グラフを構成します．このグラフは，無限遠にある外部細分割点（通常は，凸包点）と接続する少数の辺をもち，その辺によって平面を小領域に分割していきます． すべての細分割に対して，その面と点（細分割頂点）の役割を入れ替えた双対細分割が存在します．つまり，双対細分割では，面は頂点として扱われ（以降は，仮想点と呼びます），元の細分割の頂点は面として扱われます．以下の図では，元の細分割が実線で，双対細分割が点線で表されています． .. image:: ../../pics/subdiv.png OpenCV では，ドロネーのアルゴリズムを用いて平面を三角形に細分化します．細分割は，確実にすべての細分点を含む仮想の三角形から開始される反復計算により行われます．この場合，双対細分割は入力 2 次元点集合に対するボロノイ図となります．この細分割は，平面の 3 次元区分変換やモーフィング，平面上の点の高速な位置同定，特殊なグラフ（NNGやRNG）の生成などに利用できます． .. index:: CvQuadEdge2D .. _CvQuadEdge2D: CvQuadEdge2D ------------ `id=0.722209466228 Comments from the Wiki `__ .. ctype:: CvQuadEdge2D 平面細分割の Quad-edge． .. code-block:: c /* 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 の反転）から成る平面細分割の基本要素です． .. image:: ../../pics/quadedge.png .. index:: CvSubdiv2DPoint .. _CvSubdiv2DPoint: CvSubdiv2DPoint --------------- `id=0.00194244771295 Comments from the Wiki `__ .. ctype:: CvSubdiv2DPoint 細分割または双対細分割における頂点． .. code-block:: c #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 この整数値は，平面細分割の各頂点に関する補助的なデータのインデックスを表すのに用いられます． .. index:: CalcSubdivVoronoi2D .. _CalcSubdivVoronoi2D: CalcSubdivVoronoi2D ------------------- `id=0.902764132675 Comments from the Wiki `__ .. cfunction:: void cvCalcSubdivVoronoi2D( CvSubdiv2D* subdiv ) ボロノイ図のセルの座標を求めます． :param subdiv: 既にすべての点を含む，ドロネー細分割． この関数は，仮想点の座標を計算します．元の細分割の頂点に対応するすべての仮想点は，（互いに接続され）その点におけるボロノイ図のセルの境界を形成します． .. index:: ClearSubdivVoronoi2D .. _ClearSubdivVoronoi2D: ClearSubdivVoronoi2D -------------------- `id=0.285559905663 Comments from the Wiki `__ .. cfunction:: void cvClearSubdivVoronoi2D( CvSubdiv2D* subdiv ) すべての仮想点を削除します． :param subdiv: ドロネー細分割． この関数は，すべての仮想点を削除します．前回の関数呼び出し後に，細分割が変更されていた場合に，関数 :ref:`CalcSubdivVoronoi2D` の内部で呼ばれます． .. index:: CreateSubdivDelaunay2D .. _CreateSubdivDelaunay2D: CreateSubdivDelaunay2D ---------------------- `id=0.322605415879 Comments from the Wiki `__ .. cfunction:: CvSubdiv2D* cvCreateSubdivDelaunay2D( CvRect rect, CvMemStorage* storage ) 空のドロネー三角形を作成します． :param rect: 細分割に追加されるすべての 2 次元点を含む矩形． :param storage: 細分割結果を保存するストレージ． この関数は，空のドロネー細分割を作成します．ここに 2 次元点を追加するには，関数 :ref:`SubdivDelaunay2DInsert` を利用します．追加されるすべての点は，引数で指定された矩形内に存在しなければならず，そうでない場合はランタイムエラーが発生します． 三角形分割の結果として，与えられた矩形を覆う 1 つの大きな三角形が作成されることに注意してください．したがって，この三角形の3つの頂点は ``rect`` の外側に存在します． .. index:: FindNearestPoint2D .. _FindNearestPoint2D: FindNearestPoint2D ------------------ `id=0.0971361904951 Comments from the Wiki `__ .. cfunction:: CvSubdiv2DPoint* cvFindNearestPoint2D( CvSubdiv2D* subdiv, CvPoint2D32f pt ) 与えられた点に最も近い細分割の頂点を求めます． :param subdiv: ドロネー細分割，あるいはその他の細分割． :param pt: 入力座標点． この関数は，入力点が細分割内のどこに位置するかを求める，もう1つの関数です．これは，入力点にもっとも近い細分割の頂点を見つけます．入力点を含む分割面は（関数 :ref:`Subdiv2DLocate` によって求められ）開始点として利用されますが，その分割面の頂点が最も近い頂点とは限りません．この関数は，見つかった細分割頂点へのポインタを返します． .. index:: Subdiv2DEdgeDst .. _Subdiv2DEdgeDst: Subdiv2DEdgeDst --------------- `id=0.802611288611 Comments from the Wiki `__ .. cfunction:: CvSubdiv2DPoint* cvSubdiv2DEdgeDst( CvSubdiv2DEdge edge ) 辺の終点を返します． :param edge: 細分割の辺（quad-edgeではありません）． この関数は，辺の終点を返します．入力辺が双対細分割のものであり，仮想点の座標がまだ計算されていない場合，戻り値であるポインタは NULL になる場合があります．この仮想点は，関数 :ref:`CalcSubdivVoronoi2D` を用いて計算することが可能です． .. index:: Subdiv2DGetEdge .. _Subdiv2DGetEdge: Subdiv2DGetEdge --------------- `id=0.0308662443865 Comments from the Wiki `__ .. cfunction:: CvSubdiv2DEdge cvSubdiv2DGetEdge( CvSubdiv2DEdge edge, CvNextEdgeType type ) 与えられた辺に関連する辺の1つを返します． :param edge: 細分割の辺（quad-edgeではありません）． :param 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`` ） .. image:: ../../pics/quadedge.png この関数は，入力辺に関連する辺の1つを返します． .. index:: Subdiv2DNextEdge .. _Subdiv2DNextEdge: Subdiv2DNextEdge ---------------- `id=0.52210011644 Comments from the Wiki `__ .. cfunction:: CvSubdiv2DEdge cvSubdiv2DNextEdge( CvSubdiv2DEdge edge ) 入力辺の始点からみて，入力辺の次にある辺を返します． :param edge: 細分割の辺（quad-edgeではありません）． .. image:: ../../pics/quadedge.png この関数は，入力辺の始点からみて，入力辺の次にある辺を返します：上図の ``e`` が入力辺だとすると， ``eOnext`` が返されます． .. index:: Subdiv2DLocate .. _Subdiv2DLocate: Subdiv2DLocate -------------- `id=0.81009466733 Comments from the Wiki `__ .. cfunction:: CvSubdiv2DPointLocation cvSubdiv2DLocate( CvSubdiv2D* subdiv, CvPoint2D32f pt, CvSubdiv2DEdge* edge, CvSubdiv2DPoint** vertex=NULL ) ドロネーの三角形内に存在する点の位置を返します． :param subdiv: ドロネー細分割，あるいはその他の細分割． :param pt: 位置を知りたい点． :param edge: 出力される辺．入力点は，この辺上または辺の右側に位置します． :param 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`` が返ります． .. index:: Subdiv2DRotateEdge .. _Subdiv2DRotateEdge: Subdiv2DRotateEdge ------------------ `id=0.40953649882 Comments from the Wiki `__ .. cfunction:: CvSubdiv2DEdge cvSubdiv2DRotateEdge( CvSubdiv2DEdge edge, int rotate ) 同じ quad-edge にある別の辺を返します． :param edge: 細分割の辺（quad-edgeではありません）． :param rotate: 同じquad-edgeにある辺の内，どの辺を返すかの指定．以下の中から1つが指定されます： * **0** 入力辺（下図で ``e`` を入力辺とした場合の ``e`` 自身）． * **1** 回転した辺（下図で ``e`` を入力辺とした場合の ``eRot`` ）． * **2** 反転した辺（下図で ``e`` を入力辺とした場合の ``e`` を反転した（緑で表現された）辺）． * **3** 回転した辺をさらに反転した辺（下図で ``e`` を入力辺とした場合の ``eRot`` を反転した（緑で表現された）辺）． .. image:: ../../pics/quadedge.png この関数は，入力辺と同じquad-edgeにある別の辺を返します． .. index:: SubdivDelaunay2DInsert .. _SubdivDelaunay2DInsert: SubdivDelaunay2DInsert ---------------------- `id=0.561129182934 Comments from the Wiki `__ .. cfunction:: CvSubdiv2DPoint* cvSubdivDelaunay2DInsert( CvSubdiv2D* subdiv, CvPoint2D32f pt) ドロネーの三角形に1つの点を追加します． :param subdiv: 関数 :ref:`CreateSubdivDelaunay2D` によって作成されたドロネー細分割． :param pt: 追加される座標点． この関数は，細分割結果に 1 つの点を追加し，細分割のトポロジーを適切に変更します．もし，既に同じ座標に点が存在していた場合は，点の新規追加は行われません．この関数は，メモリ確保した追加点へのポインタを返します． この段階では，仮想点座標の計算は行われません．