假设我有一个非简单多边形,CGAL如何帮助我把它分割成一组简单的多边形?
例如,给出一个由2D点序列表示的多边形:
(1, 1) (1, -1) (-1, 1) (-1, -1)
我想获得两个多边形;
(1, 1) (1, -1) (0, 0)
和
(0, 0) (-1, 1) (-1, -1)
对于CGAL是否可行?
这个问题似乎被抛弃了…无论如何,我要添加一个简单的代码来回答这个问题:
#include <iostream>
#include <vector>
#include <CGAL/Arrangement_2.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Polygon_2.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;
using Polygon = CGAL::Polygon_2<Kernel>;
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());
// ------ iterate the arrangement bounded faces and create simple polygons
std::vector<Polygon> polygons;
for (auto fit = arr.faces_begin(); fit != arr.faces_end(); ++fit)
{
if (not fit->is_unbounded())
{
Polygon poly;
auto const heitBeg = fit->outer_ccb();
auto heit = heitBeg;
do {poly.push_back(heit->source()->point());} while (++heit != heitBeg);
polygons.push_back(poly);
}
}
// ------ print simple polygons
auto polyN = 1;
for (auto const& p: polygons)
{
std::cout << "Polygon #" << polyN++ << ": ";
for (auto const& v: p.vertices()) std::cout << '(' << v << ") ";
std::cout << std::endl;
}
}
函数CGAL::insert
自动计算交点(0,0)。输出为:
Polygon #1: (-0 -0) (-1 1) (-1 -1)
Polygon #2: (1 1) (-0 -0) (1 -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)