opencv/doc/cv_planar_subdivisions.tex

   1 \section{Planar Subdivisions}
   2
   3 \ifCPy
   4
   5 \cvclass{CvSubdiv2D}\label{CvSubdiv2D}
   6
   7 Planar subdivision.
   8
   9 \ifC
  10 \begin{lstlisting}
  11 #define CV_SUBDIV2D_FIELDS()    \
  12     CV_GRAPH_FIELDS()           \
  13     int  quad_edges;            \
  14     int  is_geometry_valid;     \
  15     CvSubdiv2DEdge recent_edge; \
  16     CvPoint2D32f  topleft;      \
  17     CvPoint2D32f  bottomright;
  18
  19 typedef struct CvSubdiv2D
  20 {
  21     CV_SUBDIV2D_FIELDS()
  22 }
  23 CvSubdiv2D;
  24 \end{lstlisting}
  25 \else
  26 \begin{description}
  27 \cvarg{edges}{A \cross{CvSet} of \cross{CvSubdiv2DEdge}}
  28 \end{description}
  29 \fi
  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 exists a dual subdivision in which facets and
  39 points (subdivision vertices) swap their roles, that is, 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. On the picture below
  42 original subdivision is marked with solid lines and dual subdivision
  43 with dotted lines.
  44
  45 \includegraphics[width=0.5\textwidth]{pics/subdiv.png}
  46
  47 OpenCV subdivides a plane into triangles using 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 \ifC
  56 \cvclass{CvQuadEdge2D}\label{CvQuadEdge2D}
  57
  58 Quad-edge of planar subdivision.
  59
  60 \begin{lstlisting}
  61 /* one of edges within quad-edge, lower 2 bits is index (0..3)
  62    and upper bits are quad-edge pointer */
  63 typedef long CvSubdiv2DEdge;
  64
  65 /* quad-edge structure fields */
  66 #define CV_QUADEDGE2D_FIELDS()     \
  67     int flags;                     \
  68     struct CvSubdiv2DPoint* pt[4]; \
  69     CvSubdiv2DEdge  next[4];
  70
  71 typedef struct CvQuadEdge2D
  72 {
  73     CV_QUADEDGE2D_FIELDS()
  74 }
  75 CvQuadEdge2D;
  76
  77 \end{lstlisting}
  78
  79 Quad-edge is a basic element of subdivision containing four edges (e, eRot, reversed e and reversed eRot):
  80
  81 \includegraphics[width=0.5\textwidth]{pics/quadedge.png}
  82 \fi
  83
  84 \cvclass{CvSubdiv2DPoint}\label{CvSubdiv2DPoint}
  85
  86 \ifC
  87 Point of original or dual subdivision.
  88
  89 \begin{lstlisting}
  90 #define CV_SUBDIV2D_POINT_FIELDS()\
  91     int            flags;      \
  92     CvSubdiv2DEdge first;      \
  93     CvPoint2D32f   pt;         \
  94     int id;
  95
  96 #define CV_SUBDIV2D_VIRTUAL_POINT_FLAG (1 << 30)
  97
  98 typedef struct CvSubdiv2DPoint
  99 {
 100     CV_SUBDIV2D_POINT_FIELDS()
 101 }
 102 CvSubdiv2DPoint;
 103 \end{lstlisting}
 104
 105 \begin{itemize}
 106 \item[id] This integer can be used to index auxillary data associated with each vertex of the planar subdivision
 107 \end{itemize}
 108 \else
 109 Point of original or dual subdivision.
 110
 111 \begin{description}
 112 \cvarg{first}{A connected \cross{CvSubdiv2DEdge}}
 113 \cvarg{pt}{Position, as a \cross{CvPoint2D32f}}
 114 \end{description}
 115
 116 \fi
 117
 118 \cvCPyFunc{CalcSubdivVoronoi2D}
 119 Calculates the coordinates of Voronoi diagram cells.
 120
 121 \cvdefC{
 122 void cvCalcSubdivVoronoi2D( \par CvSubdiv2D* subdiv );
 123 }
 124 \cvdefPy{CalcSubdivVoronoi2D(subdiv)-> None}
 125
 126 \begin{description}
 127 \cvarg{subdiv}{Delaunay subdivision, in which all the points are already added}
 128 \end{description}
 129
 130 The function calculates the coordinates
 131 of virtual points. All virtual points corresponding to some vertex of the
 132 original subdivision form (when connected together) a boundary of the Voronoi
 133 cell at that point.
 134
 135 \cvCPyFunc{ClearSubdivVoronoi2D}
 136 Removes all virtual points.
 137
 138 \cvdefC{
 139 void cvClearSubdivVoronoi2D( CvSubdiv2D* subdiv );
 140 }\cvdefPy{ClearSubdivVoronoi2D(subdiv)-> None}
 141
 142 \begin{description}
 143 \cvarg{subdiv}{Delaunay subdivision}
 144 \end{description}
 145
 146 The function removes all of the virtual points. It
 147 is called internally in \cvCPyCross{CalcSubdivVoronoi2D} if the subdivision
 148 was modified after previous call to the function.
 149
 150
 151 \cvCPyFunc{CreateSubdivDelaunay2D}
 152 Creates an empty Delaunay triangulation.
 153
 154 \cvdefC{
 155 CvSubdiv2D* cvCreateSubdivDelaunay2D( \par CvRect rect,\par CvMemStorage* storage );
 156 }\cvdefPy{CreateSubdivDelaunay2D(rect,storage)-> delaunay\_triangulation}
 157
 158 \begin{description}
 159 \cvarg{rect}{Rectangle that includes all of the 2d points that are to be added to the subdivision}
 160 \cvarg{storage}{Container for subdivision}
 161 \end{description}
 162
 163 The function creates an empty Delaunay
 164 subdivision, where 2d points can be added using the function
 165 \cvCPyCross{SubdivDelaunay2DInsert}. All of the points to be added must be within
 166 the specified rectangle, otherwise a runtime error will be raised.
 167
 168 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 \texttt{rect}.
 169
 170 \cvCPyFunc{FindNearestPoint2D}
 171 Finds the closest subdivision vertex to the given point.
 172
 173 \cvdefC{
 174 CvSubdiv2DPoint* cvFindNearestPoint2D( \par CvSubdiv2D* subdiv,\par CvPoint2D32f pt );
 175 }\cvdefPy{FindNearestPoint2D(subdiv,pt)-> point}
 176
 177 \begin{description}
 178 \cvarg{subdiv}{Delaunay or another subdivision}
 179 \cvarg{pt}{Input point}
 180 \end{description}
 181
 182 The function is another function that
 183 locates the input point within the subdivision. It finds the subdivision vertex that
 184 is the closest to the input point. It is not necessarily one of vertices
 185 of the facet containing the input point, though the facet (located using
 186 \cvCPyCross{Subdiv2DLocate}) is used as a starting
 187 point. The function returns a pointer to the found subdivision vertex.
 188
 189 \cvCPyFunc{Subdiv2DEdgeDst}
 190 Returns the edge destination.
 191
 192 \cvdefC{
 193 CvSubdiv2DPoint* cvSubdiv2DEdgeDst( \par CvSubdiv2DEdge edge );
 194 }
 195 \cvdefPy{Subdiv2DEdgeDst(edge)-> point}
 196
 197 \begin{description}
 198 \cvarg{edge}{Subdivision edge (not a quad-edge)}
 199 \end{description}
 200
 201 The function returns the edge destination. The
 202 returned pointer may be NULL if the edge is from dual subdivision and
 203 the virtual point coordinates are not calculated yet. The virtual points
 204 can be calculated using the function \cvCPyCross{CalcSubdivVoronoi2D}.
 205
 206 \cvCPyFunc{Subdiv2DGetEdge}
 207 Returns one of the edges related to the given edge.
 208
 209 \cvdefC{
 210 CvSubdiv2DEdge  cvSubdiv2DGetEdge( CvSubdiv2DEdge edge, CvNextEdgeType type );
 211
 212
 213 }\cvdefPy{Subdiv2DGetEdge(edge,type)-> CvSubdiv2DEdge}
 214
 215 \begin{description}
 216 \cvarg{edge}{Subdivision edge (not a quad-edge)}
 217 \cvarg{type}{Specifies which of the related edges to return, one of the following:}
 218 \begin{description}
 219   \cvarg{CV\_NEXT\_AROUND\_ORG}{next around the edge origin (\texttt{eOnext} on the picture below if \texttt{e} is the input edge)}
 220   \cvarg{CV\_NEXT\_AROUND\_DST}{next around the edge vertex (\texttt{eDnext})}
 221   \cvarg{CV\_PREV\_AROUND\_ORG}{previous around the edge origin (reversed \texttt{eRnext})}
 222   \cvarg{CV\_PREV\_AROUND\_DST}{previous around the edge destination (reversed \texttt{eLnext})}
 223   \cvarg{CV\_NEXT\_AROUND\_LEFT}{next around the left facet (\texttt{eLnext})}
 224   \cvarg{CV\_NEXT\_AROUND\_RIGHT}{next around the right facet (\texttt{eRnext})}
 225   \cvarg{CV\_PREV\_AROUND\_LEFT}{previous around the left facet (reversed \texttt{eOnext})}
 226   \cvarg{CV\_PREV\_AROUND\_RIGHT}{previous around the right facet (reversed \texttt{eDnext})}
 227 \end{description}
 228 \end{description}
 229
 230 \includegraphics[width=0.5\textwidth]{pics/quadedge.png}
 231
 232 The function returns one of the edges related to the input edge.
 233
 234 \cvCPyFunc{Subdiv2DNextEdge}
 235 Returns next edge around the edge origin
 236
 237 \cvdefC{
 238 CvSubdiv2DEdge  cvSubdiv2DNextEdge( CvSubdiv2DEdge edge );
 239 }
 240 \cvdefPy{Subdiv2DNextEdge(edge)-> CvSubdiv2DEdge}
 241
 242 \begin{description}
 243 \cvarg{edge}{Subdivision edge (not a quad-edge)}
 244 \end{description}
 245
 246 \includegraphics[width=0.5\textwidth]{pics/quadedge.png}
 247
 248 The function returns the next edge around the edge origin: \texttt{eOnext} on the picture above if \texttt{e} is the input edge)
 249
 250 \cvCPyFunc{Subdiv2DLocate}
 251 Returns the location of a point within a Delaunay triangulation.
 252
 253 \cvdefC{
 254 CvSubdiv2DPointLocation  cvSubdiv2DLocate( \par CvSubdiv2D* subdiv,\par CvPoint2D32f pt,\par CvSubdiv2DEdge* edge,\par CvSubdiv2DPoint** vertex=NULL );
 255 }
 256 \cvdefPy{Subdiv2DLocate(subdiv, pt) -> (loc, where)}
 257
 258 \begin{description}
 259 \cvarg{subdiv}{Delaunay or another subdivision}
 260 \cvarg{pt}{The point to locate}
 261 \cvC{\cvarg{edge}{The output edge the point falls onto or right to}}
 262 \cvC{\cvarg{vertex}{Optional output vertex double pointer the input point coinsides with}}
 263 \cvPy{\cvarg{loc}{The location of the point within the triangulation}}
 264 \cvPy{\cvarg{where}{The edge or vertex.  See below.}}
 265 \end{description}
 266
 267 The function locates the input point within the subdivision. There are 5 cases:
 268
 269 \ifC
 270 \begin{itemize}
 271  \item The point falls into some facet. The function returns \texttt{CV\_PTLOC\_INSIDE} and \texttt{*edge} will contain one of edges of the facet.
 272  \item The point falls onto the edge. The function returns \texttt{CV\_PTLOC\_ON\_EDGE} and \texttt{*edge} will contain this edge.
 273  \item The point coincides with one of the subdivision vertices. The function returns \texttt{CV\_PTLOC\_VERTEX} and \texttt{*vertex} will contain a pointer to the vertex.
 274  \item The point is outside the subdivsion reference rectangle. The function returns \texttt{CV\_PTLOC\_OUTSIDE\_RECT} and no pointers are filled.
 275  \item One of input arguments is invalid. A runtime error is raised or, if silent or "parent" error processing mode is selected, \texttt{CV\_PTLOC\_ERROR} is returnd.
 276 \end{itemize}
 277 \fi
 278
 279 \ifPy
 280 \begin{itemize}
 281  \item The point falls into some facet.                          \texttt{loc} is \texttt{CV\_PTLOC\_INSIDE} and \texttt{where} is one of edges of the facet.
 282  \item The point falls onto the edge.                            \texttt{loc} is \texttt{CV\_PTLOC\_ON\_EDGE} and \texttt{where} is the edge.
 283  \item The point coincides with one of the subdivision vertices. \texttt{loc} is \texttt{CV\_PTLOC\_VERTEX} and \texttt{where} is the vertex.
 284  \item The point is outside the subdivsion reference rectangle.  \texttt{loc} is \texttt{CV\_PTLOC\_OUTSIDE\_RECT} and \texttt{where} is None.
 285  \item One of input arguments is invalid. The function raises an exception.
 286 \end{itemize}
 287 \fi
 288
 289 \cvCPyFunc{Subdiv2DRotateEdge}
 290 Returns another edge of the same quad-edge.
 291
 292 \cvdefC{
 293 CvSubdiv2DEdge  cvSubdiv2DRotateEdge( \par CvSubdiv2DEdge edge,\par int rotate );
 294 }\cvdefPy{Subdiv2DRotateEdge(edge,rotate)-> CvSubdiv2DEdge}
 295
 296 \begin{description}
 297 \cvarg{edge}{Subdivision edge (not a quad-edge)}
 298 \cvarg{rotate}{Specifies which of the edges of the same quad-edge as the input one to return, one of the following:
 299 \begin{description}
 300   \cvarg{0}{the input edge (\texttt{e} on the picture below if \texttt{e} is the input edge)}
 301   \cvarg{1}{the rotated edge (\texttt{eRot})}
 302   \cvarg{2}{the reversed edge (reversed \texttt{e} (in green))}
 303   \cvarg{3}{the reversed rotated edge (reversed \texttt{eRot} (in green))}
 304 \end{description}}
 305 \end{description}
 306
 307 \includegraphics[width=0.5\textwidth]{pics/quadedge.png}
 308
 309 The function returns one of the edges of the same quad-edge as the input edge.
 310
 311 \cvCPyFunc{SubdivDelaunay2DInsert}
 312 Inserts a single point into a Delaunay triangulation.
 313
 314 \cvdefC{
 315 CvSubdiv2DPoint*  cvSubdivDelaunay2DInsert( \par CvSubdiv2D* subdiv,\par CvPoint2D32f pt);
 316 }\cvdefPy{SubdivDelaunay2DInsert(subdiv,pt)-> point}
 317
 318 \begin{description}
 319 \cvarg{subdiv}{Delaunay subdivision created by the function \cvCPyCross{CreateSubdivDelaunay2D}}
 320 \cvarg{pt}{Inserted point}
 321 \end{description}
 322
 323 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.
 324
 325 \fi