使用CGAL分割非簡單多邊形

Question

假設我有一個非簡單多邊形， CGAL如何幫助我將它分割成一組簡單的多邊形？

例如，給由2D的一個序列代表的多邊形點：

(1, 1) (1, -1) (-1, 1) (-1, -1) 

我希望獲得兩個多邊形;

(1, 1) (1, -1) (0, 0) 

和

(0, 0) (-1, 1) (-1, -1) 

它是可行的CGAL？

Answer 1

您需要的兩個多邊形不能組成原始的船體。如果你只是想使用打破你原來設定成三角形（0,0），你可以做到這一點的頂點之一：

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h> 
#include <CGAL/Constrained_Delaunay_triangulation_2.h> 
#include <CGAL/Delaunay_mesh_vertex_base_2.h> 
#include <CGAL/Delaunay_mesh_face_base_2.h> 
#include <vector>  

typedef CGAL::Exact_predicates_inexact_constructions_kernel  K; 
typedef K::Point_2            Point_2; 
typedef CGAL::Delaunay_mesh_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 CDT::Vertex_handle          Vertex_handle; 
typedef CDT::Face_iterator          Face_iterator;  

int main(int argc, char* argv[]) 
{ 
    // Create a vector of the points 
    // 
    std::vector<Point_2> points2D ; 
    points2D.push_back(Point_2( 1, 1)); 
    points2D.push_back(Point_2( 1, -1)); 
    points2D.push_back(Point_2(-1, 1)); 
    points2D.push_back(Point_2(-1, -1)); 
    points2D.push_back(Point_2(0, 0)); 

    size_t numTestPoints = points2D.size(); 

    // Create a constrained delaunay triangulation and add the points 
    // 
    CDT cdt; 
    std::vector<Vertex_handle> vhs; 
    for (unsigned int i=0; i<numTestPoints; ++i){ 
     vhs.push_back(cdt.insert(points2D[i])); 
    } 

    int i=0; 
    for (Face_iterator fit = cdt.faces_begin() ; fit != cdt.faces_end(); ++fit) { 
     printf("Face %d is (%f,%f) -- (%f,%f) -- (%f,%f) \n",i++, 
       fit->vertex(0)->point().x(),fit->vertex(0)->point().y(), 
       fit->vertex(1)->point().x(),fit->vertex(1)->point().y(), 
       fit->vertex(2)->point().x(),fit->vertex(2)->point().y()); 

    } 

    return 0 ; 
} 

應該給這樣你的輸出：

Face 0 is (0.000000,0.000000) -- (1.000000,-1.000000) -- (1.000000,1.000000) 
Face 1 is (0.000000,0.000000) -- (1.000000,1.000000) -- (-1.000000,1.000000) 
Face 2 is (-1.000000,-1.000000) -- (0.000000,0.000000) -- (-1.000000,1.000000) 
Face 3 is (-1.000000,-1.000000) -- (1.000000,-1.000000) -- (0.000000,0.000000)