1 \section{Planar Subdivisions}
5 \cvfunc{CvSubdiv2D}\label{CvSubdiv2D}
10 #define CV_SUBDIV2D_FIELDS() \
13 int is_geometry_valid; \
14 CvSubdiv2DEdge recent_edge; \
15 CvPoint2D32f topleft; \
16 CvPoint2D32f bottomright;
18 typedef struct CvSubdiv2D
25 Planar subdivision is the subdivision of a plane into a set of
26 non-overlapped regions (facets) that cover the whole plane. The above
27 structure describes a subdivision built on a 2d point set, where the points
28 are linked together and form a planar graph, which, together with a few
29 edges connecting the exterior subdivision points (namely, convex hull points)
30 with infinity, subdivides a plane into facets by its edges.
32 For every subdivision there exists a dual subdivision in which facets and
33 points (subdivision vertices) swap their roles, that is, a facet is
34 treated as a vertex (called a virtual point below) of the dual subdivision and
35 the original subdivision vertices become facets. On the picture below
36 original subdivision is marked with solid lines and dual subdivision
39 \includegraphics[width=0.5\textwidth]{pics/subdiv.png}
41 OpenCV subdivides a plane into triangles using Delaunay's
42 algorithm. Subdivision is built iteratively starting from a dummy
43 triangle that includes all the subdivision points for sure. In this
44 case the dual subdivision is a Voronoi diagram of the input 2d point set. The
45 subdivisions can be used for the 3d piece-wise transformation of a plane,
46 morphing, fast location of points on the plane, building special graphs
47 (such as NNG,RNG) and so forth.
49 \cvfunc{CvQuadEdge2D}\label{CvQuadEdge2D}
51 Quad-edge of planar subdivision.
54 /* one of edges within quad-edge, lower 2 bits is index (0..3)
55 and upper bits are quad-edge pointer */
56 typedef long CvSubdiv2DEdge;
58 /* quad-edge structure fields */
59 #define CV_QUADEDGE2D_FIELDS() \
61 struct CvSubdiv2DPoint* pt[4]; \
62 CvSubdiv2DEdge next[4];
64 typedef struct CvQuadEdge2D
66 CV_QUADEDGE2D_FIELDS()
72 Quad-edge is a basic element of subdivision containing four edges (e, eRot, reversed e and reversed eRot):
74 \includegraphics[width=0.5\textwidth]{pics/quadedge.png}
76 \cvfunc{CvSubdiv2DPoint}\label{CvSubdiv2DPoint}
78 Point of original or dual subdivision.
81 #define CV_SUBDIV2D_POINT_FIELDS()\
83 CvSubdiv2DEdge first; \
87 #define CV_SUBDIV2D_VIRTUAL_POINT_FLAG (1 << 30)
89 typedef struct CvSubdiv2DPoint
91 CV_SUBDIV2D_POINT_FIELDS()
97 \item[id] This integer can be used to index auxillary data associated with each vertex of the planar subdivision
100 \cvCPyFunc{CalcSubdivVoronoi2D}
101 Calculates the coordinates of Voronoi diagram cells.
104 void cvCalcSubdivVoronoi2D( \par CvSubdiv2D* subdiv );
106 \cvdefPy{CalcSubdivVoronoi2D(subdiv)-> None}
109 \cvarg{subdiv}{Delaunay subdivision, in which all the points are already added}
112 The function calculates the coordinates
113 of virtual points. All virtual points corresponding to some vertex of the
114 original subdivision form (when connected together) a boundary of the Voronoi
117 \cvCPyFunc{ClearSubdivVoronoi2D}
118 Removes all virtual points.
121 void cvClearSubdivVoronoi2D( CvSubdiv2D* subdiv );
122 }\cvdefPy{ClearSubdivVoronoi2D(subdiv)-> None}
125 \cvarg{subdiv}{Delaunay subdivision}
128 The function removes all of the virtual points. It
129 is called internally in \cvCPyCross{CalcSubdivVoronoi2D} if the subdivision
130 was modified after previous call to the function.
133 \cvCPyFunc{CreateSubdivDelaunay2D}
134 Creates an empty Delaunay triangulation.
137 CvSubdiv2D* cvCreateSubdivDelaunay2D( \par CvRect rect,\par CvMemStorage* storage );
138 }\cvdefPy{CreateSubdivDelaunay2D(rect,storage)-> delaunay\_triangulation}
141 \cvarg{rect}{Rectangle that includes all of the 2d points that are to be added to the subdivision}
142 \cvarg{storage}{Container for subdivision}
145 The function creates an empty Delaunay
146 subdivision, where 2d points can be added using the function
147 \cvCPyCross{SubdivDelaunay2DInsert}. All of the points to be added must be within
148 the specified rectangle, otherwise a runtime error will be raised.
150 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}.
152 \cvCPyFunc{FindNearestPoint2D}
153 Finds the closest subdivision vertex to the given point.
156 CvSubdiv2DPoint* cvFindNearestPoint2D( \par CvSubdiv2D* subdiv,\par CvPoint2D32f pt );
157 }\cvdefPy{FindNearestPoint2D(subdiv,pt)-> point}
160 \cvarg{subdiv}{Delaunay or another subdivision}
161 \cvarg{pt}{Input point}
164 The function is another function that
165 locates the input point within the subdivision. It finds the subdivision vertex that
166 is the closest to the input point. It is not necessarily one of vertices
167 of the facet containing the input point, though the facet (located using
168 \cvCPyCross{Subdiv2DLocate}) is used as a starting
169 point. The function returns a pointer to the found subdivision vertex.
171 \cvCPyFunc{Subdiv2DEdgeDst}
172 Returns the edge destination.
175 CvSubdiv2DPoint* cvSubdiv2DEdgeDst( \par CvSubdiv2DEdge edge );
177 \cvdefPy{Subdiv2DEdgeDst(edge)-> point}
180 \cvarg{edge}{Subdivision edge (not a quad-edge)}
183 The function returns the edge destination. The
184 returned pointer may be NULL if the edge is from dual subdivision and
185 the virtual point coordinates are not calculated yet. The virtual points
186 can be calculated using the function \cvCPyCross{CalcSubdivVoronoi2D}.
188 \cvCPyFunc{Subdiv2DEdgeOrg}
189 Returns the edge origin.
192 CvSubdiv2DPoint* cvSubdiv2DEdgeOrg( \par CvSubdiv2DEdge edge );
193 }\cvdefPy{Subdiv2DEdgeOrg(edge)-> point}
196 \cvarg{edge}{Subdivision edge (not a quad-edge)}
199 The function returns the edge
200 origin. The returned pointer may be NULL if the edge is from dual
201 subdivision and the virtual point coordinates are not calculated
202 yet. The virtual points can be calculated using the function
203 \cvCPyCross{CalcSubdivVoronoi2D}.
205 \cvCPyFunc{Subdiv2DGetEdge}
206 Returns one of the edges related to the given edge.
209 CvSubdiv2DEdge cvSubdiv2DGetEdge( CvSubdiv2DEdge edge, CvNextEdgeType type );
212 }\cvdefPy{Subdiv2DGetEdge(edge,type)-> CvSubdiv2DEdge}
214 #define cvSubdiv2DNextEdge( edge ) cvSubdiv2DGetEdge( edge, CV_NEXT_AROUND_ORG )
218 \cvarg{edge}{Subdivision edge (not a quad-edge)}
219 \cvarg{type}{Specifies which of the related edges to return, one of the following:}
221 \cvarg{CV\_NEXT\_AROUND\_ORG}{next around the edge origin (\texttt{eOnext} on the picture above if \texttt{e} is the input edge)}
222 \cvarg{CV\_NEXT\_AROUND\_DST}{next around the edge vertex (\texttt{eDnext})}
223 \cvarg{CV\_PREV\_AROUND\_ORG}{previous around the edge origin (reversed \texttt{eRnext})}
224 \cvarg{CV\_PREV\_AROUND\_DST}{previous around the edge destination (reversed \texttt{eLnext})}
225 \cvarg{CV\_NEXT\_AROUND\_LEFT}{next around the left facet (\texttt{eLnext})}
226 \cvarg{CV\_NEXT\_AROUND\_RIGHT}{next around the right facet (\texttt{eRnext})}
227 \cvarg{CV\_PREV\_AROUND\_LEFT}{previous around the left facet (reversed \texttt{eOnext})}
228 \cvarg{CV\_PREV\_AROUND\_RIGHT}{previous around the right facet (reversed \texttt{eDnext})}
232 The function returns one of the edges related to the input edge.
234 \cvCPyFunc{Subdiv2DLocate}
235 Returns the location of a point within a Delaunay triangulation.
238 CvSubdiv2DPointLocation cvSubdiv2DLocate( \par CvSubdiv2D* subdiv,\par CvPoint2D32f pt,\par CvSubdiv2DEdge* edge,\par CvSubdiv2DPoint** vertex=NULL );
239 }\cvdefPy{Subdiv2DLocate(subdiv, pt) -> (loc, where)}
242 \cvarg{subdiv}{Delaunay or another subdivision}
243 \cvarg{pt}{The point to locate}
244 \cvC{\cvarg{edge}{The output edge the point falls onto or right to}}
245 \cvC{\cvarg{vertex}{Optional output vertex double pointer the input point coinsides with}}
246 \cvPy{\cvarg{loc}{The location of the point within the triangulation}}
247 \cvPy{\cvarg{where}{The edge or vertex. See below.}}
250 The function locates the input point within the subdivision. There are 5 cases:
254 \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.
255 \item The point falls onto the edge. The function returns \texttt{CV\_PTLOC\_ON\_EDGE} and \texttt{*edge} will contain this edge.
256 \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.
257 \item The point is outside the subdivsion reference rectangle. The function returns \texttt{CV\_PTLOC\_OUTSIDE\_RECT} and no pointers are filled.
258 \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.
264 \item The point falls into some facet. \texttt{loc} is \texttt{CV\_PTLOC\_INSIDE} and \texttt{where} is one of edges of the facet.
265 \item The point falls onto the edge. \texttt{loc} is \texttt{CV\_PTLOC\_ON\_EDGE} and \texttt{where} is the edge.
266 \item The point coincides with one of the subdivision vertices. \texttt{loc} is \texttt{CV\_PTLOC\_VERTEX} and \texttt{where} is the vertex.
267 \item The point is outside the subdivsion reference rectangle. \texttt{loc} is \texttt{CV\_PTLOC\_OUTSIDE\_RECT} and \texttt{where} is None.
268 \item One of input arguments is invalid. The function raises an exception.
272 \cvCPyFunc{Subdiv2DRotateEdge}
273 Returns another edge of the same quad-edge.
276 CvSubdiv2DEdge cvSubdiv2DRotateEdge( \par CvSubdiv2DEdge edge,\par int rotate );
277 }\cvdefPy{Subdiv2DRotateEdge(edge,rotate)-> CvSubdiv2DEdge}
280 \cvarg{edge}{Subdivision edge (not a quad-edge)}
281 \cvarg{rotate}{Specifies which of the edges of the same quad-edge as the input one to return, one of the following:
283 \cvarg{0}{the input edge (\texttt{e} on the picture above if \texttt{e} is the input edge)}
284 \cvarg{1}{the rotated edge (\texttt{eRot})}
285 \cvarg{2}{the reversed edge (reversed \texttt{e} (in green))}
286 \cvarg{3}{the reversed rotated edge (reversed \texttt{eRot} (in green))}
290 The function returns one of the edges of the same quad-edge as the input edge.
292 \cvCPyFunc{SubdivDelaunay2DInsert}
293 Inserts a single point into a Delaunay triangulation.
296 CvSubdiv2DPoint* cvSubdivDelaunay2DInsert( \par CvSubdiv2D* subdiv,\par CvPoint2D32f pt);
297 }\cvdefPy{SubdivDelaunay2DInsert(subdiv,pt)-> point}
300 \cvarg{subdiv}{Delaunay subdivision created by the function \cvCPyCross{CreateSubdivDelaunay2D}}
301 \cvarg{pt}{Inserted point}
304 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.