【opencv450-samples】delaunay 三角剖分和 voronoi 细分

该程序演示了 delaunay 三角剖分和 voronoi 细分的迭代构造。

This program demonstrates iterativeconstruction of delaunaytriangulation and voronoitessellation.

它在图像中绘制一组随机点，然后对它们进行三角测量。

It draws a random set of points in an imageand then delaunay triangulates them.

该程序以交互方式构建三角形，您可以通过按任意键来停止此过程

This program builds the triangulationinteractively, you may stop this process by hitting any key

视频演示

源码：

#include 
#include 
#include 


using namespace cv;
using namespace std;


static void help(char** argv)
{
    cout << "nThis program demonstrates iterative construction ofn"
            "delaunay triangulation and voronoi tessellation.n"
            "It draws a random set of points in an image and then delaunay triangulates them.n"
            "Usage: n";
    cout << argv[0];
    cout << "nnThis program builds the triangulation interactively, you may stop this process byn"
            "hitting any key.n";
}


static void draw_subdiv_point( Mat& img, Point2f fp, Scalar color )
{
    circle( img, fp, 3, color, FILLED, LINE_8, 0 );//绘制圆点
}


static void draw_subdiv( Mat& img, Subdiv2D& subdiv, Scalar delaunay_color )
{
#if 1
    vector triangleList;
    subdiv.getTriangleList(triangleList);
    vector pt(3);


    for( size_t i = 0; i < triangleList.size(); i++ )//绘制所有三角形
    {
        Vec6f t = triangleList[i];
        pt[0] = Point(cvRound(t[0]), cvRound(t[1]));
        pt[1] = Point(cvRound(t[2]), cvRound(t[3]));
        pt[2] = Point(cvRound(t[4]), cvRound(t[5]));
        line(img, pt[0], pt[1], delaunay_color, 1, LINE_AA, 0);
        line(img, pt[1], pt[2], delaunay_color, 1, LINE_AA, 0);
        line(img, pt[2], pt[0], delaunay_color, 1, LINE_AA, 0);
    }
#else
    vector edgeList;
    subdiv.getEdgeList(edgeList);
    for( size_t i = 0; i < edgeList.size(); i++ )//绘制所有边
    {
        Vec4f e = edgeList[i];
        Point pt0 = Point(cvRound(e[0]), cvRound(e[1]));
        Point pt1 = Point(cvRound(e[2]), cvRound(e[3]));
        line(img, pt0, pt1, delaunay_color, 1, LINE_AA, 0);
    }
#endif
}


static void locate_point( Mat& img, Subdiv2D& subdiv, Point2f fp, Scalar active_color )
{
    int e0=0, vertex=0;
    //返回指定点所属三角形相关信息
    
    subdiv.locate(fp, e0, vertex);


    if( e0 > 0 )
    {
        int e = e0;
        do
        {
            Point2f org, dst;
            if( subdiv.edgeOrg(e, &org) > 0 && subdiv.edgeDst(e, &dst) > 0 )//找到指定边的 起点和终点
                line(img, org, dst, active_color, 3, LINE_AA, 0);//绘制直线


            e = subdiv.getEdge(e, Subdiv2D::NEXT_AROUND_LEFT);//获取下一个左边的边
        }
        while( e != e0 );// 
    }


    draw_subdiv_point( img, fp, active_color );//在fp位置绘制圆点
}


//绘制voronoi图
static void paint_voronoi( Mat& img, Subdiv2D& subdiv )
{
    vector > facets;
    vector centers;
    subdiv.getVoronoiFacetList(vector(), facets, centers);


    vector ifacet;
    vector > ifacets(1);


    for( size_t i = 0; i < facets.size(); i++ )
    {
        ifacet.resize(facets[i].size());
        for( size_t j = 0; j < facets[i].size(); j++ )
            ifacet[j] = facets[i][j];


        Scalar color;
        color[0] = rand() & 255;
        color[1] = rand() & 255;
        color[2] = rand() & 255;
        fillConvexPoly(img, ifacet, color, 8, 0);


        ifacets[0] = ifacet;
        polylines(img, ifacets, true, Scalar(), 1, LINE_AA, 0);
        circle(img, centers[i], 3, Scalar(), FILLED, LINE_AA, 0);
    }
}




int main( int argc, char** argv )
{
    cv::CommandLineParser parser(argc, argv, "{help h||}");
    if (parser.has("help"))
    {
        help(argv);
        return 0;
    }


    Scalar active_facet_color(0, 0, 255), delaunay_color(255,255,255);
    Rect rect(0, 0, 600, 600);


    Subdiv2D subdiv(rect);//三角网剖分
    Mat img(rect.size(), CV_8UC3);


    img = Scalar::all(0);
    string win = "Delaunay Demo";
    cv::imshow(win, img);//黑色背景图


    for( int i = 0; i < 200; i++ )
    {   //随机200个点
        Point2f fp( (float)(rand()%(rect.width-10)+5),
                    (float)(rand()%(rect.height-10)+5));


        locate_point( img, subdiv, fp, active_facet_color );//红色圆点，绘制连接该点的三角形
        cv::imshow( win, img );


        if(cv::waitKey( 100 ) >= 0 )
            break;


        subdiv.insert(fp);//插入新点


        img = Scalar::all(0);//清空图像
        draw_subdiv( img, subdiv, delaunay_color );//绘制Delaunay三角剖分图
        cv::imshow( win, img );


        if(cv::waitKey( 100 ) >= 0 )
            break;
    }


    img = Scalar::all(0);//再次清空图像
    paint_voronoi( img, subdiv );//绘制Voronoi图
    cv::imshow( win, img );


    cv::waitKey(0);


    return 0;
}

参考：

三角剖分和Delaunay剖分的定义

如何把一个散点集合剖分成不均匀的三角形网格，这就是散点集的三角剖分问题，散点集的三角剖分，对数值分析以及图形学来说，都是极为重要的一项预处理技术

Delaunay三角剖分的特性

以下是Delaunay剖分所具备的优异特性：

1. 最接近：以最近邻的三点形成三角形，且各线段(三角形的边)皆不相交。

2. 唯一性：不论从区域何处开始构建，最终都将得到一致的结果。

3. 最优性：任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话，那么两个三角形六个内角中最小的角度不会变大。

4. 最规则：如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大。

5. 区域性：新增、删除、移动某一个顶点时只会影响临近的三角形。

6. 具有凸多边形的外壳：三角网最外层的边界形成一个凸多边形的外壳。

Delaunay剖分是一种三角剖分的标准，实现它有多种算法。

Lawson算法 Bowyer-Watson算法

Delaunay三角剖分实践与原理 - 知乎(zhihu.com)

https://zhuanlan.zhihu.com/p/42331420

[图形算法]Delaunay三角剖分算法 - 塞风朔雪 - 博客园 (cnblogs.com)

https://www.cnblogs.com/RenLiQQ/archive/2008/02/06/1065399.html

二维三角剖分通常用于计算机视觉中标记空间目标的特征或运动场景跟踪，目标识别，或两个不同的摄像机的场景匹配

Voronoi划分_lzhf1122的博客-CSDN博客_voronoi剖分

https://blog.csdn.net/lzhf1122/article/details/72866521

Voronoi图的简单方法_爱分享的小佳的博客-CSDN博客_voronoi图法

https://blog.csdn.net/gumenghua_com1/article/details/109839253

OpenCV三角网剖分 SubDiv2D 详解_唐国平的博客-CSDN博客

https://blog.csdn.net/m0_37742084/article/details/65437689

class SubDiv2D{
    // 两种构造函数
    Subdiv2D();// 第一种无参的构造函数
    
    
    Subdiv2D(Rect rect);
    //初始化
    void initDelaunay(Rect rect);
    //往Delaunay三角形里面追加点
    int insert(Point2f pt);
    void insert(const vector& ptvec);
    //返回指定点所属三角形相关信息
    
    int locate(Point2f pt, int& edge, int& vertex);
    // 找到与指定点最近的细分割的顶点。
    
    int findNearest(Point2f pt, Point2f* nearestPt=0);


    //找到Delaunay边的集合
    
    void getEdgeList(vector& edgeList) const;
    // 找到Delaunay三角形的顶点
    
    void getTriangleList(vector& triangleList) const;


    // 找到Voronoi区域
    
    void getVoronoiFacetList(const vector& idx, vector >& facetList,
                                     vector& facetCenters);
    //!取得顶点
    
    Point2f getVertex(int vertex, int* firstEdge=0) const;
    
    //! 找到指定边关联的一条边
    
    int getEdge( int edge, int nextEdgeType ) const;
    int nextEdge(int edge) const;
    int rotateEdge(int edge, int rotate) const;
    int symEdge(int edge) const;


    //找到指定边的开始点
    
    int edgeOrg(int edge, Point2f* orgpt=0) const;


    //找到指定边的终点
    
    int edgeDst(int edge, Point2f* dstpt=0) const;
}