头大啊，自己写三维算法太累了，还是引入开源库吧
CGAL是计算几何算法库，是一个大型C++库的几何数据结构和算法，如Delaunay三角网、网格生成、布尔运算的多边形以及各种几何处理算法。
CGAL是用来在各个领域:计算机图形学、科学可视化、计算机辅助设计与建模、地理信息系统、分子生物学、医学影像学、机器人学和运动规划和数值方法
太复杂了，头大啊编译这个鬼东西，到处都是坑
一.CGAL安装
CGAL必须依赖Boost库 gmp库 mpfx库
boost_system-vc142-mt-gd-x64-1_74.lib
boost_system-vc142-mt-x64-1_74.lib
boost_thread-vc142-mt-gd-x64-1_74.lib
boost_thread-vc142-mt-x64-1_74.lib
libgmp-10.lib
libmpfr-4.lib
CGAL也会依赖 eigen库 openmesh库 opencv库 zlib库等
CGAL也依赖QT5库 （常用 QtWidgets QtGui QtOpenGL QtCore Qt）
注意：QT5的安装在VS中必须安装QT VS TOOLS功能插件，来支持QT中的UI界面，不然在VS中会识别不出来
#include "ui_ImageInterface.h" 这个在QT对应 ImageInterface.ui 要么用VS右键编译生成头文件，要么在QT的bin中找 uic.exe 进行cmd命令生成
注意:如果出现无法识别 CGAL::QGLViewer::staticMetaObject 这个东西跟QObject相关联，而它的识别需要QT的bin中找 moc.exe 进行cmd命令生成一个.cpp 最后链接到代码上
CGAL必须事先用cmake编译出 CGAL_Core-vc141
CGAL_ImageIO-vc141
CGAL_Qt5-vc141
CGAL-vc141
二.CGAL使用
1.创建点 线 面
//表示几何图元
typedef CGAL::Simple_cartesian<double> Kernel;
//表示点
typedef Kernel::Point_2 Point_2;
//表示线
typedef Kernel::Segment_2 Segment_2;
Point_2 p(1, 1), q(10, 10);
Segment_2 s(p, q);
2.计算点到线段的距离
Point_2 p(1,1), q(10, 10);
//两点距离
CGAL::squared_distance(p, q)
CGAL::orientation(p, q, m)
CGAL::midpoint(p, q)
三.CGAL解析
四.CGAL Examples
1.AABB_tree
2.Advancing_font_surface_reconstruction
3.Algebraic_foundations
4.Algebraic_kernel_d
5.Alpha_shapes_2
6.Alpha_shapes_3
7.Apollonius_graph_2
8.Approximate_min_ellipsoid_d
9.Arrangement_on_surface_2
10.Barycentric_coordinates_2
11.BGL_arrangement_2
12.BGL_graphcut
13.BGL_LCC
14.BGL_OpenMesh
15.BGL_polyhedron_3
16.BGL_surface_mesh
17.BGL_triangulation_2
18.Boolean_set_operations_2
19.Box_intersection_d
20.CGAL_ipelets
21.CGALimageIO
22.Circular_kernel_2
23.Circular_kernel_3
24.Circulator
25.Classification
26.Combinatorial_map
27.Cone_spanners_2
28.Convex_decomposition_3
29.Convex_decomposition_3
30.Convex_hull_2
31.Convex_hull_3
32.Core
33.Envelope_2
34.Envelope_3
35.Filtered_kernel
36.Generator
37.HalfedgeDS
38.Heat_method_3
39.Hyperbolic_triangulation_2
40.Inscribed_areas
41.Interpolation
42.Interval_skip_list
43.Jet_fitting_3
44.Kernel_23
45.Linear_cell_complex
46.Matrix_search
47.Mesh_2
48.Mesh_3
49.Min_annulus_d
50.Min_circle_2
51.Min_ellipse_2
52.Min_quadrilateral_2
53.Min_sphere_d
54.Min_sphere_of_spheres_d
55.Minkowski_sum_2
56.Minkowski_sum_3
57.Modular_arithmetric
58.Nef_2
59.Nef_3
60.Nef_32
61.Optimal_bounding_box
62.Optimal_transportation_reconstruction_2
63.Orthtree
64.Partition_2
65.Periodic_2_triangulation_2
66.Periodic_3_mesh_3
67.Periodic_3_triangulation_3
68.Periodic_4_hyperbolic_triangulation_2
69.Point_set_2
70.Point_set_3
71.Point_set_processing_3
72.Poisson_surface_reconstruction_3
73.Polygon
//绘制多边形
//draw_polygon.cpp
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#define CGAL_USE_BASIC_VIEWER
#ifdef CGAL_USE_BASIC_VIEWER
#include <CGAL/draw_triangulation_2.h>
#include <CGAL/draw_polygon_2.h>
#endif
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Polygon_2<K> Polygon_2;
typedef CGAL::Point_2<K> Point;
int main()
{
//create a polygon and put some points in it
Polygon_2 p;
p.push_back(Point(0, 0));
p.push_back(Point(4, 0));
p.push_back(Point(4, 4));
p.push_back(Point(2, 2));
p.push_back(Point(0, 4));
CGAL::draw(p);
return EXIT_SUCCESS;
}
//带洞的多边形
//draw_polygon_with_holes.cpp
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_with_holes_2.h>
#define CGAL_USE_BASIC_VIEWER
#ifdef CGAL_USE_BASIC_VIEWER
#include <CGAL/draw_polygon_with_holes_2.h>
#endif
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Polygon_with_holes_2<K> Polygon_with_holes_2;
typedef CGAL::Polygon_2<K> Polygon_2;
typedef CGAL::Point_2<K> Point;
int main()
{
//Create a polygon with three holes
Polygon_2 outer_polygon;
outer_polygon.push_back(Point(0, 0)); outer_polygon.push_back(Point(9, 0));
outer_polygon.push_back(Point(6, 8)); outer_polygon.push_back(Point(5, 3));
outer_polygon.push_back(Point(2, 8)); outer_polygon.push_back(Point(0, 8));
std::vector<Polygon_2> holes(3);
holes[0].push_back(Point(6, 2)); holes[0].push_back(Point(7, 1));
holes[0].push_back(Point(7, 3)); holes[0].push_back(Point(6, 3));
holes[0].push_back(Point(5, 2));
holes[1].push_back(Point(2, 1)); holes[1].push_back(Point(3, 1));
holes[1].push_back(Point(3, 3)); holes[1].push_back(Point(2, 2));
holes[1].push_back(Point(1, 2));
holes[2].push_back(Point(1, 4)); holes[2].push_back(Point(2, 4));
holes[2].push_back(Point(2, 5)); holes[2].push_back(Point(3, 5));
holes[2].push_back(Point(3, 6)); holes[2].push_back(Point(1, 6));
Polygon_with_holes_2 p(outer_polygon, holes.begin(), holes.end());
//And draw it
CGAL::draw(p);
return EXIT_SUCCESS;
}
//Example.cpp
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <list>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Point_2<K> Point;
typedef CGAL::Polygon_2<K> Polygon_2;
typedef Polygon_2::Vertex_iterator VertexIterator;
typedef Polygon_2::Edge_const_iterator EdgeIterator;
int main()
{
//create a polygon and put some points in it
Polygon_2 p;
p.push_back(Point(0, 0));
p.push_back(Point(4, 0));
p.push_back(Point(4, 4));
p.push_back(Point(2, 2));
p.push_back(Point(0, 4));
CGAL::set_pretty_mode(std::cout);
//CGAL::IO::set_pretty_mode(std::cout);
std::cout << "created the polygon p" << std::endl;
std::cout << p << std::endl;
//determine some properties of the polygon
bool IsSimple = p.is_simple();
bool IsConvex = p.is_convex();
bool IsClockwise = (p.orientation() == CGAL::CLOCKWISE);
double Area = p.area();
std::cout << "polygon p is";
if (!IsSimple) std::cout << "not";
std::cout << "simple." << std::endl;
std::cout << "polygon p is";
if (!IsConvex) std::cout << "not";
std::cout << "convex." << std::endl;
std::cout << "polygon p is";
if (!IsClockwise) std::cout << "not";
std::cout << "clockwise oriented" << std::endl;
std::cout << "the area of polygon p is" << Area << std::endl;
std::cout << std::endl;
// apply some algorithms
Point q(1, 1);
std::cout << "created point q = " << q << std::endl;
std::cout << std::endl;
bool IsInside = (p.bounded_side(q) == CGAL::ON_BOUNDED_SIDE);
std::cout << "point q is";
if (!IsInside) std::cout << "not";
std::cout << "inside polygon p" << std::endl;
std::cout << std::endl;
//traverse the vertices and the edges
int n = 0;
for (VertexIterator vi = p.vertices_begin(); vi != p.vertices_end(); ++vi)
std::cout << "vertex" << n++ << "=" << *vi << std::endl;
std::cout << std::endl;
n = 0;
for (EdgeIterator ei = p.edges_begin(); ei != p.edges_end(); ++ei)
std::cout << "edge" << n++ << "=" << *ei << std::endl;
return 0;
}
//Polygon.cpp
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <iostream>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point;
typedef CGAL::Polygon_2<K> Polygon_2;
using std::cout;
using std::endl;
int main()
{
Point points[] = { Point(0, 0), Point(5.1, 0), Point(1, 1), Point(0.5, 6) };
Polygon_2 pgn(points, points + 4);
//check if the polygon is simple
cout << "The polygon is " << (pgn.is_simple() ? "" : "not") << "simple" << endl;
//check if the polygon is convex
cout << "The polygon is " << (pgn.is_convex() ? "" : "not") << "convex" << endl;
return 0;
}
//提供了判断点是否在多边形内部或者外部的算法
//polygon_algorithms.cpp
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_2_algorithms.h>
#include <iostream>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point;
using std::cout;
using std::endl;
void check_inside(Point pt, Point* pgn_begin, Point* pgn_end, K traits)
{
cout << "The point" << pt;
switch (CGAL::bounded_side_2(pgn_begin, pgn_end, pt, traits)) {
case CGAL::ON_BOUNDED_SIDE :
cout << "is inside the polygon
";
break;
case CGAL::ON_BOUNDARY:
cout << "is on the polygon boudary
";
break;
case CGAL::ON_UNBOUNDED_SIDE:
cout << "is outside the polygon
";
break;
}
}
int main()
{
Point points[] = { Point(0, 0), Point(5.1, 0), Point(1, 1), Point(0.5, 6) };
//check if the polygon is simple
cout << "The polygon is" << (CGAL::is_simple_2(points, points + 4, K()) ? "" : "not") << "simple" << endl;
check_inside(Point(0.5, 0.5), points, points + 4, K());
check_inside(Point(1.5, 2.5), points, points + 4, K());
check_inside(Point(2.5, 0), points, points + 4, K());
return 0;
}
//projected_polygon.cpp
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Projection_traits_yz_3.h>
#include <CGAL/Polygon_2_algorithms.h>
#include <iostream>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_3 Point_3;
int main()
{
Point_3 points[4] = { Point_3(0, 1, 1), Point_3(0, 2, 1), Point_3(0, 2, 2), Point_3(0, 1, 2) };
bool b = CGAL::is_simple_2(points, points + 4, CGAL::Projection_traits_yz_3<K>());
if (!b) {
std::cerr << "Error polygon is not simple" << std::endl;
return 1;
}
return 0;
}
74.Polygon_mesh_processing
75.Polygonal_surface_reconstruction
76.Polyhedron
77.Polyhedron_IO
78.Polyline_simplification_2
79.Polynomial
80.Polytope_distance_d
81.Principal_component_analysis
82.Profiling_tools
83.Property_map
84.QP_solver
85.RangeSegmentTrees
86.Rectangular_p_center_2
87.Ridges_3
88.Scale_space_reconstruction_3
89.Segment_Delaunay_graph_2
90.Segment_Delaunay_graph_Linf_2
91.Set_movable_separability_2
92.Shape_detection
93.Skin_surface_3
94.Snap_rounding_2
95.Solver_interface
96.Spatial_searching
97.Spatial_sorting
98.STL_Extension
99.Straight_skeleton_2
100.Stream_lines_2
101.Stream_support
102.Subdivision_method_3
103.Surface_mesh
104.Surface_mesh_approximation
105.Surface_mesh_deformation
106.Surface_mesh_parameterization
107.Surface_mesh_segmentation
108.Surface_mesh_shortest_path
109.Surface_mesh_simplification
110.Surface_mesh_skeletonization
111.Surface_mesh_topology
112.Surface_mesher
113.Surface_sweep_2
114.TDS_3
115.Tetrahedral_remeshing
116.Triangulation
117.Triangulation_2
118.Triangulation_3
119.Visibility_2
120.Voronoi_diagram_2
五.CGAL Demo
1.AABB_tree
2.Alpha_shapes_2
3.Alpha_shapes_3
4.Apollonius_graph_2
5.Arrangement_on_surface_2
6.Bounding_volumes
7.CGAL_ipelets
8.Circular_kernel_2
9.Circulal_kernel_3
10.Convex_hull_3
11.Generator
12.Geomview
13.GraphicsView
14.Hyperbolic_triangulation_2
15.icons
16.Interpolation
17.L1_Voronoi_diagram_2
18.Largest_empty_rect_2
19.Linear_cell_complex
20.Mesh_2
21.Optimal_transportation_reconstruction_2
22.Periodic_2_triangulation_2
23.Periodic_3_triangulation_3
24.Periodic_4_hyperbolic_triangulation_2
25.Periodic_LIoyd_3
26.Polygon
27.Polyhedron
28.Polyhedron_IO
29.Polyline_simplication_2
30.Principal_component_analysis
31.resources
32.Segment_Delaunay_graph_2
33.Segment_Delaunay_graph_Linf_2
34.Snap_rounding_2
35.Spatial_searching_2
36.Stream_lines_2
37.Surface_mesh_deformation
38.Surface_mesher
39.Triangulation_2
40.Triangulation_3
41.Triangulation_3_Geomview_demos