c++ - OpenCV，C++ : Missing Triangles in Delaunay Triangulation

Question

我在 Ubuntu 11.04 上使用 NetBeans 7.1，并希望使用 OpenCV 从一组点中获取三角形。我按如下方式构建 Delaunay 三角剖分。

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() 具有以下形式。

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);
}

这让我得到了大部分三角形，但有些缺失了。例如，我设置了一组近似矩形网格的点。我得到以下(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)

所以 (106,1);(204,1);(103,101) 缺失，至少有一个三角形重复。

Answer 1

您的 if 语句似乎有错误？为什么要将 newPoint.x 与 boundRect.y 进行比较？

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