CODEWITHSUNDEEP
c++openglopencvtriangulationdelaunay
OtagoHarbour
OtagoHarbour

Reputation: 4183

OpenCV,C++: Missing Triangles in Delaunay Triangulation

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.

vector< Triangle > CTwoDTriangulation::delaunayDiv(const vector< Point_<T> > & vP,   cv::Rect boundRect, vector<Triangle>& triangles, int& numTriangles)
{
    CvSubdiv2D* subdiv;
    int numPts=vP.size();
    CvPoint newPoint;

    CvMemStorage *storage;
    storage = cvCreateMemStorage(0);
    subdiv =  cvCreateSubdivDelaunay2D( boundRect, storage );
    for (size_t e = 0; e<numPts; e++)
    {
        newPoint=vP.at(e);
        if (newPoint.x>=boundRect.y && newPoint.y>=boundRect.y && newPoint.x<boundRect.width &&  newPoint.y<boundRect.height)
                cvSubdivDelaunay2DInsert(subdiv, vP.at(e));
    }

    CvSeqReader  reader;
    int i, total = subdiv->edges->total;
    int elem_size = subdiv->edges->elem_size;

    triangles.resize(2*total-5);    // Maximum number of triangles for number of edges
    numTriangles=0;

    cvStartReadSeq( (CvSeq*)(subdiv->edges), &reader, 0 );

    Triangle V;

    for( i = 0; i < total; i++ )
    {
        CvQuadEdge2D* edge = (CvQuadEdge2D*)(reader.ptr);

        if( CV_IS_SET_ELEM( edge ))
        {
            CvSubdiv2DEdge e = (CvSubdiv2DEdge)edge;
            if (FindTriangleFromEdge(e, V)) 
        {
            triangles.at(numTriangles++)=V;
        }
    }
    CV_NEXT_SEQ_ELEM( elem_size, reader );
}
cvReleaseMemStorage(&storage);

return triangles;
}

FindTriangleFromEdge() has the following form.

void CTwoDTriangulation::FindTriangleFromEdge(CvSubdiv2DEdge e, Triangle& V)
{
   CvSubdiv2DEdge t = e;    // Number of type size_t
   CvPoint buf[3];          // Triangle vertices
   int iPointNum = 3;
   int  j;
   CvPoint pts[3];

   for(j = 0; j < iPointNum; j++ )
   {
        CvSubdiv2DPoint* point = cvSubdiv2DEdgeOrg( t );
        if( !point ) break;
        pts[j].x=point->pt.x;
        pts[j].y=point->pt.y;
        buf[j] = cvPoint( cvRound(point->pt.x), cvRound(point->pt.y));
        t = cvSubdiv2DGetEdge( t, CV_NEXT_AROUND_LEFT );
   }
  AddTriangle(buf, pts, V);
}

This gets me most of the triangles but some are missing. For example, I set a set of points that approximate a rectangular grid. I get the following (5,1);(103,101);(1,101)
(106,1);(103,101);(5,1)
(5,1);(106,1);(103,101)
(204,101);(106,1);(208,1)
(208,1);(307,101);(204,101)
(309,1);(307,101);(204,101)

So (106,1);(204,1);(103,101)is missing and at least one triangle is duplicated.

Upvotes: 0

Views: 1424

Answers (3)

pdpcosta
pdpcosta

Reputation: 199

When you use CV_NEXT_AROUND_LEFT the next edge to be chosen will be the one on LEFT facet of the specified edge. Now consider, for example, a triangle formed by vertices V1, V2 and V3, whose sides are Edge1, Edge2 and Edge3.

Additionally, imagine that V1 is the Org Point of Edge1, V2 is the Org Point of Edge2 and V3 is the Org Point of Edge3 (like vectors connected in a clockwise orientation). In this case, the left facets are always outside the given triangle so, in your code, this triangle will be missing.

I could not realize another way of preventing this except by combining CV_NEXT_AROUND_LEFT with CV_NEXT_AROUND_RIGHT and removing the duplicate triangles that will be recorded.

Upvotes: 0

Thomas Schwarze
Thomas Schwarze

Reputation: 1

I had the same problem. My solution was to check against

cvSubdiv2DGetEdge( t, CV_NEXT_AROUND_RIGHT );

and look! with this it found the missing ones, but misses some others. So my solution is to combine both results for now.

Upvotes: 0

Sammy
Sammy

Reputation: 346

Your if statement seems to have a bug? Why are you comparing newPoint.x with boundRect.y?

if (newPoint.x>=boundRect.y && newPoint.y>=boundRect.y && newPoint.x<boundRect.width &&  newPoint.y<boundRect.height)
            cvSubdivDelaunay2DInsert(subdiv, vP.at(e));

Upvotes: 1

Related Questions