Блог

Предположим, что у меня есть непростой полигон, как CGAL может помочь мне разбить его на набор простых полигонов?

Например, укажите полигон, представленный последовательностью 2D точек:

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

Я хочу получить два полигона;

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

и

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

Выполнимо ли это для CGAL?

Требуемые вами два полигона не составляют исходную оболочку. Если вы просто хотите разбить свой исходный набор на треугольники, используя (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) 
 

Вопрос кажется заброшенным… В любом случае, я добавляю простой код для ответа на него:

 #include <iostream>
#include <vector>

#include <CGAL/Arrangement_2.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>

using Kernel = CGAL::Exact_predicates_exact_constructions_kernel;
using Traits = CGAL::Arr_segment_traits_2<Kernel>;
using Arrangement = CGAL::Arrangement_2<Traits>;
using Point = Traits::Point_2;
using Segment = Traits::Segment_2;

int main()
{
  // ------ create a segment chain
  Point const p1(1, 1), p2(1, -1), p3(-1, 1), p4(-1, -1);
  std::vector<Segment> const cv = {{p1, p2}, {p2, p3}, {p3, p4}, {p4, p1}};
  // ------ create the arrangement
  Arrangement arr;
  CGAL::insert(arr, cv.cbegin(), cv.cend());
  // ------ print the arrangement bounded faces 
  auto faceN = 1;
  for (auto fit = arr.faces_begin(); fit != arr.faces_end();   fit)
  {
    if (not fit->is_unbounded())
    {
      std::cout << "Face #" << faceN   << ": ";
      auto const heitBeg = fit->outer_ccb();
      auto heit = heitBeg;
      do {std::cout << "[" << heit->curve() << "]";} while (  heit != heitBeg);
      std::cout << std::endl;
    }
  }
}
 

Функция CGAL::insert автоматически вычисляет точку пересечения (0,0). Результат:

 Face #1: [-0 -0 -1 1][-1 1 -1 -1][-1 -1 -0 -0]
Face #2: [-0 -0 1 1][1 -1 -0 -0][1 1 1 -1]