Sử dụng CGAL để phân vùng một đa giác không đơn giản

Question

Giả sử rằng tôi có đa giác không đơn giản, cách CGAL có thể giúp tôi phân vùng nó thành một tập hợp các đa giác đơn giản?

Ví dụ, cho một đa giác được đại diện bởi một chuỗi các 2D chỉ:

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

Tôi muốn để có được hai đa giác;

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

và

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

Có doable cho CGAL?

Answer 1

Hai đa giác bắt buộc của bạn không tạo thành thân tàu gốc. Nếu bạn chỉ muốn phá vỡ bộ hồ sơ gốc của bạn thành hình tam giác sử dụng (0,0) là một trong những đỉnh bạn có thể làm điều này:

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

nào sẽ cho bạn kết quả như thế này:

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)