OpenCV，C++:Missing Triangles in Delaunay三角测量

Question

我在 Ubuntu 11.04 上使用 NetBeans 7.1，并希望使用 OpenCV 从一组点获取三角形。我按如下方式构建德劳内三角测量。

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

Answer 2

我遇到了同样的问题。我的解决方案是检查

cvSubdiv2DGetEdge（ t， CV_NEXT_AROUND_RIGHT ）;

看！ 有了这个，它找到了失踪的人，但错过了其他一些。所以我的解决方案是现在合并这两个结果。

Answer 3

使用 CV_NEXT_AROUND_LEFT 时，要选择的下一条边将是指定边的 LEFT 面上的边。例如，现在考虑一个由顶点V1、V2和V3形成的三角形，其边是Edge1、Edge2和Edge3。

此外，假设V1是Edge1的组织点，V2是Edge2的组织点，V3是Edge3的组织点（就像顺时针方向连接的向量）。 在这种情况下，左侧刻面始终在给定三角形之外，因此在您的代码中，此三角形将丢失。

我无法实现另一种防止这种情况的方法，除非将CV_NEXT_AROUND_LEFT与CV_NEXT_AROUND_RIGHT相结合并删除将要记录的重复三角形。