# Learning OpenCV 3″ Delaunay triangulation and Voronoi diagram explanation

OpenCV2, OpenCV3 contains triangulation of the interface, but the reference document is not introduced to the study has brought trouble.

There is a classic book “Learn OpenCV ” to do a detailed introduction to it. But suffer from the new version of this book, has not yet translated into Chinese, so now on the OpenCV triangulation of the information are on the OpenCV1, is the C language interface .

I learn to share side, their understanding of the level is limited, if any mistakes, thank you correct me. Due to limited time, not verbatim translation, according to the content to.

Original reference “Learning OpenCV 3” Appendix A: Plane split. Pp. 923-937.

A large part of the front is the theory of plane division, do not do translation, just mention it. Delaunay triangulation of the characteristics and related calculation methods. Delaunay is a point set triangulation of the standard, in all subdivision schemes, satisfying the minimum angle of all triangles is the largest. Delaunay is the only one that is closest to the regular triangulation. Delaunay has many algorithms to achieve. OpenCV application is a point-by-point insertion method, which can be derived from the function interface.

The Delaunay triangulation and the Voronoi diagram are dual, which means that the Delaunay section is calculated and the Voronoi diagram is determined. Intuitively feel:

Focus on the following is the OpenCV function interface on the understanding and use of method description.

# Create Delaunay or Voronoi split

First of all need to open up a place in memory to store Delaunay split. We also need a box (remember, in order to speed up the calculation, the algorithm processing process, in the box outside the need for a virtual peripheral triangle).

To start as soon as possible, it is assumed that these points must be in a 600 * 600 image.

// STRUCTURE FOR DELAUNAY SUBDIVISION
//

cv::Rect rect(0, 0, 600, 600); // Our outer bounding box
cv::Subdiv2D subdiv(rect); // Create the initial subdivision

The code creates an initial split, and a triangle contains a specific rectangle.

Next, we need to know how to insert the point. These points must be 32-bit float type, or a point with an integer coordinate value (cv :: Point). In the following case, they are automatically converted to float types. The insertion point uses the cv::Subdiv2D::insert()function.

cv::Point2f fp; //This is our point holder
for( int i = 0; i < as_many_points_as_you_want; i++ ) {
// However you want to set points
//
fp = your_32f_point_list[i];
subdiv.insert(fp);
}

Now that the point has been entered, we can get Delaunay triangulation. Calculate the triangle from the Delaunay Triangulation, using the getTiangleList()function.

vector<cv::Vec6f> triangles;
subdiv.getTriangleList(triangles);

After calling, each of the triangles Vec6fcontains three vertices:X1, Y1, X2, Y2, X3, Y3,).

Get the corresponding Voronoi diagram using the function getVoronoiFaceList.

vector<vector<cv::Point2f> > facets;
vector<cv::Point2f> centers;
subdiv.getVoronoiFacetList(vector<int>(), facets, centers);

facetsContains the Voronoi facet . The point data contains only the vertices of the polygon , and centerscontains the corresponding center of the center.

It is worth mentioning that Delaunay triangulation is iteratively constructed, meaning that every insertion point, triangulation will be updated, so it is always updated. However, the Voronoi diagram is when you call a calcVoronoi()one-time build. Optionally, you can call the previously mentioned getVoronoiFaceList()(it’s called internally calcVoronoi()) to update it.

Now that we have created a two-dimensional point set of Delaunay splitting as well as the corresponding Voronoi diagram. The next step is to learn how to traverse this division.

# Traverse the Delaunay division

The basic data element is the edge , through the serial number access edge. With this sequence number, you can also access adjacent edges. Additional parameters can also specify the position of the edge you want to access with the current edge. Each side of the two endpoints is called originand destination. One side will share these points with the other side. Finally, there is a corresponding (dual) edge, where each edge of the Delaunay segment has a corresponding edge of the Voronoi segment.

Remember that in the cv::Subdiv2Dinterface, the edge is always straightforward, which is actually for convenience.

Also, there is direction. The two points contain two sides because of the distinction originand destination.

## According to the side access point

Whether Delaunay is subdivided or Voronoi is split, edges have both starting and ending points. The endpoint of the access side is as follows:

int cv::Subdiv2D::edgeOrg( int edge, cv::Point2f* orgpt = 0 ) const;
int cv::Subdiv2D::edgeDst( int edge, cv::Point2f* dstpt = 0 ) const;

edgeIs the input, is the serial number. The second entry point of the parameter table itself. The number of the function return point.

Given the point number, you can get the coordinates of the point, and the associated edges.

cv::Point2f cv::Subdiv2D::getVertex( int vertex, int* firstEdge = 0 ) const;

Need to pay attention, and the same side, the point number. Of course there are coordinates. Subdiv2DThe interface is deliberately designed so that in the vast majority of interface functions, you mainly use the edge and point numbers.

## Locate points in the section

One possible situation is that you have a specific point of location information, but want to find it in the section of the serial number.
A similar situation: Probably this point is not actually a vertex in a split, but you want to find a triangle or a small piece that contains this point. Method locate()to a point as input, return to this point where a side. Or an edge that contains the triangle or face of the point (if the edge is not a vertex). Note that in this case, the return is not necessarily the nearest edge, but simply returns one of the sides of the triangle or block containing the point. When the point is the vertex, it locate()also returns the ID of the vertex.

int cv::Subdiv2D::locate(
cv::Point2f pt,
int& edge,
int& vertex
);

Function returns the value, tells us that the point of the landing position

Cv :: Subdiv2D :: PTLOC_INSIDE
points fall inside the dough, * edge is one of the edges.

Cv :: Subdiv2D :: PTLOC_ON_EDGE
points on the edge * edge contains this side.

Cv :: Subdiv2D :: PTLOC_VERTEX
points fall on the vertex of the split, * vertex contains the vertex pointer.

Cv :: Subdiv2D :: PTLOC_OUTSIDE_RECT
point falls outside the reference rectangle and the return pointer is invalid.

Cv :: Subdiv2D :: PTLOC_ERROR

## Surround the vertex traversal

Given an edge, you may want to access the new edge connected to the beginning or end of the edge. The way to do this is to specify a starting edge where we search for the next edge around the “head” or “tail” point, counterclockwise, or clockwise. The description of this design is shown below. We through the function getEdge()to achieve.

int cv:Subdiv2D::getEdge(
int edge,
int nextEdgeType // see text below
) const;



When calling this function, we need to provide the current edge and nextEdgeTypeparameters, the optional parameter values ​​are as follows:

• Cv :: Subdiv2D :: NEXT_AROUND_ORG, around the next point (eOnext)
• Cv :: Subdiv2D :: NEXT_AROUND_DST, around the next edge (eDnext)
• Cv :: Subdiv2D :: PREV_AROUND_ORG, around an edge (reverse eRnext)
• Cv :: Subdiv2D :: PREV_AROUND_DST, on the end of an edge (reverse eLnext)

How to traverse depends entirely on you, you can also traverse around the triangle or face, the parameter values ​​are as follows:

• Cv :: Subdiv2D :: NEXT_AROUND_LEFT, surrounds the next edge of the left side block (eLnext)
• Cv :: Subdiv2D :: NEXT_AROUND_RIGHT, the next edge of the right side of the block (eRnext)
• Cv :: Subdiv2D :: PREV_AROUND_LEFT, around the left side of the block on the side (reversed eOnext)
• Cv :: Subdiv2D :: PREV_AROUND_RIGHT, surround the right side of the block (reversed eDnext)

(The translator’s note: “the next edge” of the implied access order, around the point of access is counterclockwise, around the polygon is counterclockwise ring)

Do not worry about the edge of the Delaunay triangle, or the edge of the polygon of the Voronoi diagram, since the serial number of the input edge already contains this information, and you can learn more about the numbering method.

You can also choose a convenient way to call nextEdge():

// equivalent to getEdge(edge, cv::Subdiv2D::NEXT_AROUND_ORG)
//
int cv:Subdiv2D::nextEdge(
int edge
) const;

It is getEdge()equivalent to the function by cv :: Subdiv2D :: NEXT_AROUND_ORG call. This function is convenient when we want to access all the edges that surround a point. For some application scenarios helpful, for example, from a virtual external triangle within a vertex, looking for convex hull.

## Rotating edge

Suppose you have a serial number on hand. Whether you are getting it from other functions or trying to traverse the entire graph from a specific serial number, call the following function you can jump from the edge of the Delaunay split to the edge of the corresponding Voronoi split.

int cv::Subdiv2D::rotateEdge(
int edge,
int rotate // get other edges in the same quad-edge: modulo 4 operation
) const;

Parameter rotatespecifies that you want to rotate the way, you can select the following parameter specifies the next side, refer to the diagram easier to understand:

• 0, the input edge (e next e is)
• 1, rotated edge (eRot)
• 2, reverse side (reverse e)
• 3, the reverse rotation of the edge (reverse eRot)

(Translator’s Note: As can be seen from the figure, the rotation side is the default around the starting point counterclockwise)

### Vertex and its naming order

As a result of the Delaunay split initialization, the following facts are always true:

1. 0 vertex is empty vertex, no coordinates.
2. Next, vertices 1, 2, and 3 are the “virtual” vertices outside the given outer rectangle, each of which is set to a position distant from the point set.
(Translator ‘s Note: understood as an illusory position, uncertain position, I will see these three points as the three vertices of the outer triangle, because the triangle is also fictional.
3. The next point is the point on the point set, provided to the Subdiv2Dobject.

### Edge and its naming order

Subdiv2DEach edge in the object is given an integer value, which is used by four groups, and the edges representing each of the four numbers are associated:

• Edge% 4 == 0
a Delaunay edge
• Edge% 4 == 1
Voronoi side perpendicular to the initial edge
• Edge% 4 == 2
is opposite to the initial edge
• Edge% 4 == 3
The reverse of the Voronoi side above

### Virtual edges and empty edges

Edge 0 is empty, does not point to any place (or, more precisely, its two endpoints are vertex 0 – also empty).

The edges of edges 1, 2, 3 are always connected to the virtual vertices of the virtual Delaunay edges. Refers to an unfixed virtual edge because its two vertices are virtual. (Translator ‘s Note: Because both sides are illusory, side of course is also, and no one end is real point.

The start and end of the sky are (0,0).

Rotate the edge of the edge, will get another empty edge. The “first edge” from the empty point is also an empty edge, followed by nextEdge()the same side.

The “first edge” accessed from any virtual vertex is always connected to another virtual vertex. (Translator’s Note: “the first side” how to understand?)

## Determine the external triangle

Now, when we create a Delaunay split on a point set, the first three points always construct an external triangle (not including point 0). We can access the three vertices in the following ways:

Point2f outer_vtx[3];
for( int i = 0; i < 3; i++ ) {
outer_vtx[i] = subdiv.getVertex(i+1);
}

We can get three edges of an external triangle:

int outer_edges[3];
outer_edges[0] = 1*4;
outer_edges[1] = subdiv.getEdge(outer_edges[0], Subdiv2D::NEXT_AROUND_LEFT);
outer_edges[2] = subdiv.getEdge(outer_edges[1], Subdiv2D::NEXT_AROUND_LEFT);

(Translator’s Note: So to say, the edge of the edge is always an edge of the triangle)

## Determine the convex hull, which is accessed around the convex hull

Recall that, Subdiv2D(rect)according to the constructor, we initialized the Delaunay partition with an external rectangle. Based on this, the following statement holds:

• If there is such an edge, its starting and ending points are outside the rectangle, and then the edge in the split fictional external triangle. This side, we call the virtual side is not fixed .
• If there is such an edge, its two endpoints are distributed on both sides of the rectangle inside and outside, and then the inside of the point on the set of convex hull. Each point on the convex hull is connected to the two vertices of the fictional peripheral triangle, and the serial numbers of the two sides are adjacent. We put this one end in the rectangle, one end of the virtual point in the virtual side of the edge, called a fixed virtual edge.

Based on the above facts, we can quickly find the convex hull. For example, starting at vertices 1, 2, 3, we know that the three points are three virtual vertices on the fictitious external triangle. We can use a nextEdge()collection that can quickly generate all fixed virtual edges (simply reject an unfixed virtual edge). And then call rotateEdge(), take the reverse side, and then call 1, or 2 times nextEdge, will fall on the edge of the convex hull. To be precise, a fixed virtual edge corresponds to the edge of a convex hull, the set of these edges is convex.

(Translator’s Note:
solve some doubts
1. nextEdge () can all access points around the edges, so start from 1,2,3 will get all of the fixed virtual edge.
2. The edge can be obtained by starting and ending numbers You can
distinguish between unfixed virtual edges, fixed virtual edges, and unfixed virtual edges by the serial number of the two edges. 3. rotateEdge (2) Moves the starting point of the edge from the vertex of the fictional triangle to the apex of the convex hull
. Calling once or twice nextEdge () just verifies that the convex hull has two wires with the virtual triangle.
)

# Use examples

We can use locate()the edge of the Delaunay triangle to be accessed step by step. In the following example, write a function that takes a given point and what to do on each side of the Delaunay triangle that contains the point:

void locate_point(
cv::Subdiv2D& subdiv,
const cv::Point2f& fp,

) {
int e;
int e0 = 0;
int vertex = 0;
subdiv.locate( fp, e0, vertex );
if( e0 > 0 ) {
e = e0;
do // Always 3 edges — this is a triangulation, after all.
{
//
// Do something with e …
e = subdiv.getEdge( e, cv::Subdiv2D::NEXT_AROUND_LEFT );
}
while( e != e0 );
}
}

Given a point, we can also call the following function to find the nearest point:

int Subdiv2D::findNearest(
cv::Point2f pt,
cv::Point2f* nearestPt
);

Instead locate(), findNearest()it returns the integer ID of the nearest vertex in the split. The input point does not have to fall within the face block or triangle. It is worth noting that this function is not a const function, because it does not update the data when it calculates Voronoi diagram.

Similarly, we can surround the Voronoi block and then draw it out.

void draw_subdiv_facet(
cv::Mat& img,
cv::Subdiv2D& subdiv,
int edge
) {
int t = edge;
int i, count = 0;
vector<cv::Point> buf;
// Count number of edges in facet
do{
count++;
t = subdiv.getEdge( t, cv::Subdiv2D::NEXT_AROUND_LEFT );
} while (t != edge );
// Gather points
//
buf.resize(count);
t = edge;
for( i = 0; i < count; i++ ) {
cv::Point2f pt;
if( subdiv.edgeOrg(t, &pt) <= 0 )
break;
buf[i] = cv::Point(cvRound(pt.x), cvRound(pt.y));
t = subdiv.getEdge( t, cv::Subdiv2D::NEXT_AROUND_LEFT );
}
// Around we go
//
if( i == count ){
cv::Point2f pt;
subdiv.edgeDst(subdiv.rotateEdge(edge, 1), &pt);
fillConvexPoly(
img, buf,
cv::Scalar(rand()&255,rand()&255,rand()&255),
8, 0
);
vector< vector<cv::Point> > outline;
outline.push_back(buf);
polylines(img, outline, true, cv::Scalar(), 1, cv::LINE_AA, 0);
draw_subdiv_point( img, pt, cv::Scalar(0,0,0) );
}
}