Planar subdivision.
#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;
Planar subdivision is the subdivision of a plane into a set of non-overlapped regions (facets) that cover the whole plane. The above structure describes a subdivision built on a 2d point set, where the points are linked together and form a planar graph, which, together with a few edges connecting the exterior subdivision points (namely, convex hull points) with infinity, subdivides a plane into facets by its edges.
For every subdivision there exists a dual subdivision in which facets and points (subdivision vertices) swap their roles, that is, a facet is treated as a vertex (called a virtual point below) of the dual subdivision and the original subdivision vertices become facets. On the picture below original subdivision is marked with solid lines and dual subdivision with dotted lines.
OpenCV subdivides a plane into triangles using Delaunay’s algorithm. Subdivision is built iteratively starting from a dummy triangle that includes all the subdivision points for sure. In this case the dual subdivision is a Voronoi diagram of the input 2d point set. The subdivisions can be used for the 3d piece-wise transformation of a plane, morphing, fast location of points on the plane, building special graphs (such as NNG,RNG) and so forth.
Quad-edge of planar subdivision.
/* one of edges within quad-edge, lower 2 bits is index (0..3)
and upper bits are quad-edge pointer */
typedef long CvSubdiv2DEdge;
/* quad-edge structure fields */
#define CV_QUADEDGE2D_FIELDS() \
int flags; \
struct CvSubdiv2DPoint* pt[4]; \
CvSubdiv2DEdge next[4];
typedef struct CvQuadEdge2D
{
CV_QUADEDGE2D_FIELDS()
}
CvQuadEdge2D;
Quad-edge is a basic element of subdivision containing four edges (e, eRot, reversed e and reversed eRot):
Point of original or dual subdivision.
#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;
This integer can be used to index auxillary data associated with each vertex of the planar subdivision
Calculates the coordinates of Voronoi diagram cells.
Parameters: |
|
---|
The function calculates the coordinates of virtual points. All virtual points corresponding to some vertex of the original subdivision form (when connected together) a boundary of the Voronoi cell at that point.
Removes all virtual points.
Parameters: |
|
---|
The function removes all of the virtual points. It is called internally in CalcSubdivVoronoi2D if the subdivision was modified after previous call to the function.
Creates an empty Delaunay triangulation.
Parameters: |
|
---|
The function creates an empty Delaunay subdivision, where 2d points can be added using the function SubdivDelaunay2DInsert . All of the points to be added must be within the specified rectangle, otherwise a runtime error will be raised.
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 rect .
Finds the closest subdivision vertex to the given point.
Parameters: |
|
---|
The function is another function that locates the input point within the subdivision. It finds the subdivision vertex that is the closest to the input point. It is not necessarily one of vertices of the facet containing the input point, though the facet (located using Subdiv2DLocate ) is used as a starting point. The function returns a pointer to the found subdivision vertex.
Returns the edge destination.
Parameters: |
|
---|
The function returns the edge destination. The returned pointer may be NULL if the edge is from dual subdivision and the virtual point coordinates are not calculated yet. The virtual points can be calculated using the function CalcSubdivVoronoi2D .
Returns one of the edges related to the given edge.
Parameters: |
|
---|
The function returns one of the edges related to the input edge.
Returns next edge around the edge origin
Parameters: |
|
---|
The function returns the next edge around the edge origin: eOnext on the picture above if e is the input edge)
Returns the location of a point within a Delaunay triangulation.
Parameters: |
|
---|
The function locates the input point within the subdivision. There are 5 cases:
Returns another edge of the same quad-edge.
Parameters: |
|
---|
The function returns one of the edges of the same quad-edge as the input edge.
Inserts a single point into a Delaunay triangulation.
Parameters: |
|
---|
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.