Utilizzo di CGAL per partizionare un poligono non semplice

Question

Supponiamo di avere un poligono non semplice, , in che modo CGAL può aiutarmi a suddividerlo in un insieme di poligoni semplici?

Ad esempio, invia un poligono rappresentata da una sequenza di punti 2D:

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

desidero acquisire due poligoni;

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

e

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

E 'fattibile per CGAL?

Answer 1

I due poligoni richiesti non costituiscono lo scafo originale. Se si desidera solo per rompere il vostro set originale in triangoli utilizzando (0,0) come uno dei vertici si può fare questo:

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

che dovrebbe dare output come questo:

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)