modules/legacy/doc/planar_subdivisions.rst

   1 Planar Subdivisions (C API)
   2 ============================
   3
   4 .. highlight:: c
   5
   6 CvSubdiv2D
   7 ----------
   8
   9 .. ocv:struct:: CvSubdiv2D
  10
  11 Planar subdivision.
  12
  13 ::
  14
  15     #define CV_SUBDIV2D_FIELDS()    \
  16         CV_GRAPH_FIELDS()           \
  17         int  quad_edges;            \
  18         int  is_geometry_valid;     \
  19         CvSubdiv2DEdge recent_edge; \
  20         CvPoint2D32f  topleft;      \
  21         CvPoint2D32f  bottomright;
  22
  23     typedef struct CvSubdiv2D
  24     {
  25         CV_SUBDIV2D_FIELDS()
  26     }
  27     CvSubdiv2D;
  28
  29 ..
  30
  31 Planar subdivision is the subdivision of a plane into a set of
  32 non-overlapped regions (facets) that cover the whole plane. The above
  33 structure describes a subdivision built on a 2D point set, where the points
  34 are linked together and form a planar graph, which, together with a few
  35 edges connecting the exterior subdivision points (namely, convex hull points)
  36 with infinity, subdivides a plane into facets by its edges.
  37
  38 For every subdivision, there is a dual subdivision in which facets and
  39 points (subdivision vertices) swap their roles. This means that a facet is
  40 treated as a vertex (called a virtual point below) of the dual subdivision and
  41 the original subdivision vertices become facets. In the figure below, the
  42 original subdivision is marked with solid lines and dual subdivision -
  43 with dotted lines.
  44
  45 .. image:: pics/subdiv.png
  46
  47 OpenCV subdivides a plane into triangles using the Delaunay's
  48 algorithm. Subdivision is built iteratively starting from a dummy
  49 triangle that includes all the subdivision points for sure. In this
  50 case, the dual subdivision is a Voronoi diagram of the input 2D point set. The
  51 subdivisions can be used for the 3D piece-wise transformation of a plane,
  52 morphing, fast location of points on the plane, building special graphs
  53 (such as NNG,RNG), and so forth.
  54
  55 CvQuadEdge2D
  56 ------------
  57
  58 .. ocv:struct:: CvQuadEdge2D
  59
  60 Quad-edge of a planar subdivision.
  61
  62 ::
  63
  64     /* one of edges within quad-edge, lower 2 bits is index (0..3)
  65        and upper bits are quad-edge pointer */
  66     typedef long CvSubdiv2DEdge;
  67
  68     /* quad-edge structure fields */
  69     #define CV_QUADEDGE2D_FIELDS()     \
  70         int flags;                     \
  71         struct CvSubdiv2DPoint* pt[4]; \
  72         CvSubdiv2DEdge  next[4];
  73
  74     typedef struct CvQuadEdge2D
  75     {
  76         CV_QUADEDGE2D_FIELDS()
  77     }
  78     CvQuadEdge2D;
  79
  80 ..
  81
  82 Quad-edge is a basic element of a subdivision containing four edges (e, eRot, reversed e, and reversed eRot):
  83
  84 .. image:: pics/quadedge.png
  85
  86 CvSubdiv2DPoint
  87 ---------------
  88
  89 .. ocv:struct:: CvSubdiv2DPoint
  90
  91 Point of an original or dual subdivision.
  92
  93 ::
  94
  95     #define CV_SUBDIV2D_POINT_FIELDS()\
  96         int            flags;      \
  97         CvSubdiv2DEdge first;      \
  98         CvPoint2D32f   pt;         \
  99         int id;
 100
 101     #define CV_SUBDIV2D_VIRTUAL_POINT_FLAG (1 << 30)
 102
 103     typedef struct CvSubdiv2DPoint
 104     {
 105         CV_SUBDIV2D_POINT_FIELDS()
 106     }
 107     CvSubdiv2DPoint;
 108
 109 ..
 110
 111 * id
 112     This integer can be used to index auxiliary data associated with each vertex of the planar subdivision.
 113
 114 CalcSubdivVoronoi2D
 115 -------------------
 116 Calculates the coordinates of the Voronoi diagram cells.
 117
 118 .. ocv:cfunction:: void cvCalcSubdivVoronoi2D(  CvSubdiv2D* subdiv )
 119
 120     :param subdiv: Delaunay subdivision, in which all the points are already added.
 121
 122 The function calculates the coordinates
 123 of virtual points. All virtual points corresponding to a vertex of the
 124 original subdivision form (when connected together) a boundary of the Voronoi
 125 cell at that point.
 126
 127 ClearSubdivVoronoi2D
 128 --------------------
 129 Removes all virtual points.
 130
 131 .. ocv:cfunction:: void cvClearSubdivVoronoi2D( CvSubdiv2D* subdiv )
 132
 133     :param subdiv: Delaunay subdivision.
 134
 135 The function removes all of the virtual points. It
 136 is called internally in
 137 :ocv:cfunc:`CalcSubdivVoronoi2D`
 138 if the subdivision
 139 was modified after the previous call to the function.
 140
 141 CreateSubdivDelaunay2D
 142 ----------------------
 143 Creates an empty Delaunay triangulation.
 144
 145 .. ocv:cfunction:: CvSubdiv2D* cvCreateSubdivDelaunay2D(  CvRect rect, CvMemStorage* storage )
 146
 147     :param rect: Rectangle that includes all of the 2D points that are to be added to the subdivision.
 148
 149     :param storage: Container for the subdivision.
 150
 151 The function creates an empty Delaunay
 152 subdivision where 2D points can be added using the function
 153 :ocv:cfunc:`SubdivDelaunay2DInsert`
 154 . All of the points to be added must be within
 155 the specified rectangle, otherwise a runtime error is raised.
 156
 157 Note that the triangulation is a single large triangle that covers the given rectangle.  Hence the three vertices of this triangle are outside the rectangle
 158 ``rect``
 159 .
 160
 161 FindNearestPoint2D
 162 ------------------
 163 Finds the subdivision vertex closest to the given point.
 164
 165 .. ocv:cfunction:: CvSubdiv2DPoint* cvFindNearestPoint2D(  CvSubdiv2D* subdiv, CvPoint2D32f pt )
 166
 167     :param subdiv: Delaunay or another subdivision.
 168
 169     :param pt: Input point.
 170
 171 The function is another function that
 172 locates the input point within the subdivision. It finds the subdivision vertex that
 173 is the closest to the input point. It is not necessarily one of vertices
 174 of the facet containing the input point, though the facet (located using
 175 :ocv:cfunc:`Subdiv2DLocate`
 176 ) is used as a starting
 177 point. The function returns a pointer to the found subdivision vertex.
 178
 179 Subdiv2DEdgeDst
 180 ---------------
 181 Returns the edge destination.
 182
 183 .. ocv:cfunction:: CvSubdiv2DPoint* cvSubdiv2DEdgeDst(  CvSubdiv2DEdge edge )
 184
 185     :param edge: Subdivision edge (not a quad-edge).
 186
 187 The function returns the edge destination. The
 188 returned pointer may be NULL if the edge is from a dual subdivision and
 189 the virtual point coordinates are not calculated yet. The virtual points
 190 can be calculated using the function
 191 :ocv:cfunc:`CalcSubdivVoronoi2D`.
 192
 193 Subdiv2DGetEdge
 194 ---------------
 195 Returns one of the edges related to the given edge.
 196
 197 .. ocv:cfunction:: CvSubdiv2DEdge  cvSubdiv2DGetEdge( CvSubdiv2DEdge edge, CvNextEdgeType type )
 198
 199     :param edge: Subdivision edge (not a quad-edge).
 200
 201     :param type: Parameter specifying which of the related edges to return. The following values are possible:
 202
 203         * **CV_NEXT_AROUND_ORG** next around the edge origin ( ``eOnext``  on the picture below if  ``e``  is the input edge)
 204
 205         * **CV_NEXT_AROUND_DST** next around the edge vertex ( ``eDnext`` )
 206
 207         * **CV_PREV_AROUND_ORG** previous around the edge origin (reversed  ``eRnext`` )
 208
 209         * **CV_PREV_AROUND_DST** previous around the edge destination (reversed  ``eLnext`` )
 210
 211         * **CV_NEXT_AROUND_LEFT** next around the left facet ( ``eLnext`` )
 212
 213         * **CV_NEXT_AROUND_RIGHT** next around the right facet ( ``eRnext`` )
 214
 215         * **CV_PREV_AROUND_LEFT** previous around the left facet (reversed  ``eOnext`` )
 216
 217         * **CV_PREV_AROUND_RIGHT** previous around the right facet (reversed  ``eDnext`` )
 218
 219 .. image:: pics/quadedge.png
 220
 221 The function returns one of the edges related to the input edge.
 222
 223 Subdiv2DNextEdge
 224 ----------------
 225 Returns next edge around the edge origin.
 226
 227 .. ocv:cfunction:: CvSubdiv2DEdge  cvSubdiv2DNextEdge( CvSubdiv2DEdge edge )
 228
 229     :param edge: Subdivision edge (not a quad-edge).
 230
 231 The function returns the next edge around the edge origin:
 232 ``eOnext``
 233 on the picture above if
 234 ``e``
 235 is the input edge).
 236
 237 Subdiv2DLocate
 238 --------------
 239 Returns the location of a point within a Delaunay triangulation.
 240
 241 .. ocv:cfunction:: CvSubdiv2DPointLocation  cvSubdiv2DLocate(  CvSubdiv2D* subdiv, CvPoint2D32f pt, CvSubdiv2DEdge* edge, CvSubdiv2DPoint** vertex=NULL )
 242
 243     :param subdiv: Delaunay or another subdivision.
 244
 245     :param pt: Point to locate.
 246
 247     :param edge: Output edge that the point belongs to or is located to the right of it.
 248
 249     :param vertex: Optional output vertex double pointer the input point coincides with.
 250
 251 The function locates the input point within the subdivision. There are five cases:
 252
 253 *
 254     The point falls into some facet. The function returns
 255     ``CV_PTLOC_INSIDE``
 256     and
 257     ``*edge``
 258     will contain one of edges of the facet.
 259
 260 *
 261     The point falls onto the edge. The function returns
 262     ``CV_PTLOC_ON_EDGE``
 263     and
 264     ``*edge``
 265     will contain this edge.
 266
 267 *
 268     The point coincides with one of the subdivision vertices. The function returns
 269     ``CV_PTLOC_VERTEX``
 270     and
 271     ``*vertex``
 272     will contain a pointer to the vertex.
 273
 274 *
 275     The point is outside the subdivision reference rectangle. The function returns
 276     ``CV_PTLOC_OUTSIDE_RECT``
 277     and no pointers are filled.
 278
 279 *
 280     One of input arguments is invalid. A runtime error is raised or, if silent or "parent" error processing mode is selected,
 281     ``CV_PTLOC_ERROR``
 282     is returnd.
 283
 284 Subdiv2DRotateEdge
 285 ------------------
 286 Returns another edge of the same quad-edge.
 287
 288 .. ocv:cfunction:: CvSubdiv2DEdge  cvSubdiv2DRotateEdge(  CvSubdiv2DEdge edge, int rotate )
 289
 290     :param edge: Subdivision edge (not a quad-edge).
 291
 292     :param rotate: Parameter specifying which of the edges of the same quad-edge as the input one to return. The following values are possible:
 293
 294             * **0** the input edge ( ``e``  on the picture below if  ``e``  is the input edge)
 295
 296             * **1** the rotated edge ( ``eRot`` )
 297
 298             * **2** the reversed edge (reversed  ``e``  (in green))
 299
 300             * **3** the reversed rotated edge (reversed  ``eRot``  (in green))
 301
 302 The function returns one of the edges of the same quad-edge as the input edge.
 303
 304 SubdivDelaunay2DInsert
 305 ----------------------
 306 Inserts a single point into a Delaunay triangulation.
 307
 308 .. ocv:cfunction:: CvSubdiv2DPoint*  cvSubdivDelaunay2DInsert(  CvSubdiv2D* subdiv, CvPoint2D32f pt)
 309
 310     :param subdiv: Delaunay subdivision created by the function  :ocv:cfunc:`CreateSubdivDelaunay2D`.
 311
 312     :param pt: Inserted point.
 313
 314 The function inserts a single point into a subdivision and modifies the subdivision topology appropriately. If a point with the same coordinates exists already, no new point is added. The function returns a pointer to the allocated point. No virtual point coordinates are calculated at this stage.