通過CGAL将一個多邊形剖分成Delaunay三角網

簡述了通過CGAL将一個多邊形剖分成Delaunay三角網的過程，并且給出了具體的實作代碼。

目錄

• 1. 概述
• 2. 實作
• 3. 結果
• 4. 參考

對于平面上的點集，通過Delaunay三角剖分算法能夠建構一個具有空圓特性和最大化最小角特性的三角網。空圓特性其實就是對于兩個共邊的三角形，任意一個三角形的外接圓中都不能包含有另一個三角形的頂點，這種形式的剖分産生的最小角最大。

更進一步的，可以給Delaunay三角網加入一些線段的限制條件，使得建構的Delaunay三角網能夠利用這些線段。利用這個特性，可以将一個多邊形剖分成Delaunay三角網，開源工具CGAL就正好提供了這個功能。

因為要顯示三角網的效果，是以我在《使用QT繪制一個多邊形》這篇博文提供的QT界面上進行修改，正好這篇文章提供的代碼還實作了在QT中繪制多邊形的功能。

關于網格化以及三角網剖分，在CGAL中提供了非常詳盡繁複的解決方案，我這裡選擇了CGAL::refine_Delaunay_mesh_2這個接口，這個接口能夠将多邊形區域建構成一個Delaunay三角網，如果目前的存在三角形不滿足Delaunay，就會在其中補充一些點來滿足Delaunay的相關特性。主要的實作代碼如下(具體代碼見文章最後)：

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Constrained_Delaunay_triangulation_2.h>
#include <CGAL/Delaunay_mesher_2.h>
#include <CGAL/Delaunay_mesh_face_base_2.h>
#include <CGAL/Delaunay_mesh_size_criteria_2.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Triangulation_vertex_base_2<K> Vb;
typedef CGAL::Delaunay_mesh_face_base_2<K> Fb;
typedef CGAL::Triangulation_data_structure_2<Vb, Fb> Tds;
typedef CGAL::Constrained_Delaunay_triangulation_2<K, Tds> CDT;
typedef CGAL::Delaunay_mesh_size_criteria_2<CDT> Criteria;
typedef CDT::Vertex_handle Vertex_handle;
typedef CDT::Point Point;

//三角化
void GraphicsPainter::Triangulate()
{
    //找到邊界上所有的像素點
    vector<Vector2d> ROIBoundPointList;
    CalBoundPoint(ROIBoundPointList);

    CDT cdt;
    vector<Vertex_handle> vertexList;
    cout<<ROIBoundPointList.size()<<endl;
//    for(int i = 0; i<pointList.size(); i++)
//    {
//        vertexList.push_back(cdt.insert(Point(pointList[i].x(), pointList[i].y() )));
//    }
    for(int i = 0; i<ROIBoundPointList.size(); i++)
    {
        vertexList.push_back(cdt.insert(Point(ROIBoundPointList[i].x, ROIBoundPointList[i].y )));
    }

    for(unsigned int i =0;i<vertexList.size()-1;i++)
    {
        cdt.insert_constraint(vertexList[i],vertexList[i+1]);
    }
    //cdt.insert_constraint(vertexList[vertexList.size()-1],vertexList[0]);


    std::cout << "Number of vertices: " << cdt.number_of_vertices() <<std::endl;
    std::cout << "Meshing the triangulation..." << std::endl;

    CGAL::refine_Delaunay_mesh_2(cdt, Criteria());
    std::cout << "Number of vertices: " << cdt.number_of_vertices() <<std::endl;


    CDT::Face_iterator fit;
    for (fit = cdt.faces_begin(); fit!= cdt.faces_end(); ++fit)
    {
        QVector<QPointF> triPoint;
        triPoint.push_back(QPointF(fit->vertex(0)->point().x(), fit->vertex(0)->point().y()));
        triPoint.push_back(QPointF(fit->vertex(1)->point().x(), fit->vertex(1)->point().y()));
        triPoint.push_back(QPointF(fit->vertex(2)->point().x(), fit->vertex(2)->point().y()));
        QPolygonF tri(triPoint);
        triList.push_back(tri);
    }

    bTri = true;
    update();
}
           

在QT界面上繪制一個多邊形，隻用多邊形上的點，最後的三角網格效果：

通過這篇博文《矢量線的一種栅格化算法》提供的栅格化算法，可以将一個多邊形栅格化，這樣就可以得到一個栅格多邊形，通過這個算法網格化，最後的效果：

可以發現這種方式會在内部新添加一些點，來滿足Delaunay特性。并且會形成邊界密集，中間稀疏的網格效果。在一些圖形、圖像進行中，會用到這種自适應網格（Adaptive Mesh）。

1. Delaunay三角剖分學習筆記

實作代碼