OpenCV: Extracting Triangles from Delaunay Triangulation

Question

I am using NetBeans 7.1 on Ubuntu 11.04 and would like to obtain triangles from a set of points using OpenCV. I build the Delaunay triangulation as follows.

CvMemStorage *storage;
size_t      ptIndex;
CvSubdiv2D* subdiv;

storage = cvCreateMemStorage(0);
subdiv =  cvCreateSubdivDelaunay2D( boundRect, storage );
for (ptIndex = 0; ptIndex<numPts; ptIndex++)
    cvSubdivDelaunay2DInsert(subdiv, points[ptIndex]);

That part seems to work OK. It runs and the resulting storage looks like this.

storage 0xb287a90
signature 1116274688
bottom 0x2a2d57a0
prev 0x0 next 0x2a2e5730
top 0x2cc947d0
prev 0x2cc84840
next 0x0 parent 0x0 signature
bottom
top
parent
block_size
free_space
block_size 65408
free_space 0

I have look at the documentation for these functions here but cannot find any function for extracting the triangles.

I would be most grateful if someone could tell me how to extract the triangles.

Peter.

Michael Kupchick Michael Kupchick · Accepted Answer · 2012-02-16T22:57:57

You can iterate edges like this:

CvMemStorage* storage = cvCreateMemStorage();
CvSubdiv2D* subdivision = cvCreateSubdivDelaunay2D(rect, storage);
for (int i = 0; i < points.size(); ++i)
{
    cvSubdivDelaunay2DInsert(subdivision, points[i].Point);
}

cvCalcSubdivVoronoi2D(subdivision);
CvSeqReader reader;
CvSeq* seq = (CvSeq*) subdivision->edges;
cvStartReadSeq(seq, &reader);
for (int i = 0; i < seq->total; ++i)
{
    CvQuadEdge2D* edge = (CvQuadEdge2D*)reader.ptr;
    if (CV_IS_SET_ELEM(edge))
    {
       // TODO: implement some edge related logic here...   
    }
    CV_NEXT_SEQ_ELEM(seq->elem_size, reader);
}

if (storage != 0)
{
    cvReleaseMemStorage(&storage);
}

Then you can use cvSubdiv2DGetEdge with CV_NEXT_AROUND_LEFT as type parameter it will iterate on the edges from the same facet (triangle)

OpenCV: Extracting Triangles from Delaunay Triangulation

1 Answers