Hello World
官网 CGAL 5.4 - Manual: Hello World
相关解释 https://blog.csdn.net/outtt/article/details/104751567
本教程面向知道C++和基本几何算法的CGAL新手。第一部分介绍如何定义点和段类（point ,segment），以及如何对它们应用几何断言(predicates，应该是用于判断的函数)。本节进一步指出了一个问题，即使用浮点数作为坐标时存在严重问题。在第二部分中，您将遇到一个典型的 CGAL 函数，该函数计算 2D 凸壳(2D convex hull)。第三部分显示了我们对 Traits 类的含义，第四部分解释了概念(concept)和模型(model)的概念。
1 三个点和一个段(Three Points and One Segment)
在第一个示例中，我们演示如何构造一些点和一个段，并对它们执行一些基本操作。
所有 CGAL 头文件都位于 子目录include/CGAL中。所有 CGAL 类和函数都位于命名空间 CGAL中。全局函数以小写字母开头，常量全部大写。对象的维度(dimension)用后缀表示。
几何基元(primitives)（如点类型）是在核(kernel)中定义的。我们为第一个示例选择的核对点的笛卡尔坐标使用精确的浮点数double。
除了类型之外，我们还会看到谓词(predicates)：如三点的方向测试。构造(constructions)：如距离和中点计算。谓词具有一组离散的可能结果，而构造则生成数字或另一个几何实体。
#include <iostream> #include <CGAL/Simple_cartesian.h> typedef CGAL::Simple_cartesian<double> Kernel; //笛卡尔坐标（cartesian）double型 typedef Kernel::Point_2 Point_2; //_2 ：2维 typedef Kernel::Segment_2 Segment_2; int main() { Point_2 p(1, 1), q(10, 10); std::cout << "p = " << p << std::endl; std::cout << "q = " << q.x() << " " << q.y() << std::endl; std::cout << "sqdist(p,q) = " << CGAL::squared_distance(p, q) << std::endl; Segment_2 s(p, q); Point_2 m(5, 9); std::cout << "m = " << m << std::endl; std::cout << "sqdist(Segment_2(p,q), m) = " << CGAL::squared_distance(s, m) << std::endl; std::cout << "p, q, and m "; switch (CGAL::orientation(p, q, m)) { case CGAL::COLLINEAR: std::cout << "are collinear\n"; break; case CGAL::LEFT_TURN: std::cout << "make a left turn\n"; break; case CGAL::RIGHT_TURN: std::cout << "make a right turn\n"; break; } std::cout << " midpoint(p,q) = " << CGAL::midpoint(p, q) << std::endl; return 0; }
使用浮点数进行几何图形计算可能会令人惊讶，如下一个示例所示。
#include <iostream> #include <CGAL/Simple_cartesian.h> typedef CGAL::Simple_cartesian<double> Kernel; typedef Kernel::Point_2 Point_2; int main() { { Point_2 p(0, 0.3), q(1, 0.6), r(2, 0.9); std::cout << (CGAL::collinear(p, q, r) ? "collinear\n" : "not collinear\n"); } { Point_2 p(0, 1.0 / 3.0), q(1, 2.0 / 3.0), r(2, 1); std::cout << (CGAL::collinear(p, q, r) ? "collinear\n" : "not collinear\n"); } { Point_2 p(0, 0), q(1, 1), r(2, 2); std::cout << (CGAL::collinear(p, q, r) ? "collinear\n" : "not collinear\n"); } return 0; }
输出： not collinear not collinear collinear
我们本来以为会得到3个collinear，但是前两个却不是。
这是因为这些分数不能表示为双精度(double)数字，并且共线性检验将在内部计算接近但不等于零的 3x3 矩阵的行列式，因此前两个测试的非共线性。
如果必须确保以完全精确度解释数字，则可以使用执行精确断言（exact predicates）和构造的 CGAL kernel。
#include <iostream> #include <CGAL/Exact_predicates_exact_constructions_kernel.h> #include <sstream> typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel; typedef Kernel::Point_2 Point_2; int main() { Point_2 p(0, 0.3), q, r(2, 0.9); { q = Point_2(1, 0.6); std::cout << (CGAL::collinear(p,q,r) ? "collinear\n" : "not collinear\n"); } { std::istringstream input("0 0.3 1 0.6 2 0.9"); input >> p >> q >> r; std::cout << (CGAL::collinear(p,q,r) ? "collinear\n" : "not collinear\n"); } { q = CGAL::midpoint(p,r); std::cout << (CGAL::collinear(p,q,r) ? "collinear\n" : "not collinear\n"); } return 0; }
输出： not collinear collinear collinear
在第一个块中，点仍然不是共线的，原因很简单，您看到的文本坐标会变成浮点数。当它们被转换为任意精度有理数时，它们正好代表浮点数，但不是文本！(文本坐标–>浮点数–>任意精度有理数)
这在第二个块中是不同的，它对应于从文件中读取数字。任意精度有理数直接从字符串构造，以便它们完全表示文本。（文本–>任意精度有理数）
在第三个块中，您可以看到作为中点构造的构造是精确的，正如内核类型的名称所暗示的那样。
在许多情况下，您将拥有"精确"的浮点数，因为它们是由某些应用程序计算的或从传感器获得的。它们不是字符串"0.1"或动态计算为"1.0/10.0"，而是全精度浮点数。如果它们是输入到不进行构造的算法的，则可以使用提供精确谓词但不精确构造的内核。其中一个例子是凸壳算法，我们将在下一节中看到。输出是输入的子集，算法仅比较坐标并执行方向测试。
乍一看，内核执行精确的谓词和构造似乎是完美的选择，但性能要求或有限的内存资源使它不是。此外，对于许多算法来说，进行精确的构造是无关紧要的。例如，曲面网格简化算法通过将边缘折叠到边缘的中点来迭代收缩边缘。
大多数 CGAL 软件包都解释了它们应该使用或支持哪种内核。
在看这里时纠结了很久，并不是很好理解直接赋值的浮点型不共线，从文本读取的浮点型共线。但是大多数时候都是从文件读取，所以影响不大，先这样吧。
2 点序列的凸壳(Convex Hull)
本节中的所有示例都计算一组点的 2D 凸壳。算法将其输入作为表示一系列点的开始/结束迭代器对，并且将结果（在示例中为凸壳上的点）写入输出迭代器。
2.1 内置数组中点的凸壳
在第一个示例中，我们有一个包含五个点的数组作为输入。由于这些点的凸壳是输入的子集，因此提供一个数组来存储具有相同大小的结果是安全的。
#include <iostream> #include <CGAL/Exact_predicates_inexact_constructions_kernel.h> #include <CGAL/convex_hull_2.h> typedef CGAL::Exact_predicates_inexact_constructions_kernel K; typedef K::Point_2 Point_2; int main() { Point_2 points[5] = { Point_2(0,0), Point_2(10,0), Point_2(10,10), Point_2(6,5), Point_2(4,1) }; Point_2 result[5]; Point_2 *ptr = CGAL::convex_hull_2( points, points+5, result ); std::cout << ptr - result << " points on the convex hull:" << std::endl; for(int i = 0; i < ptr - result; i++){ std::cout << result[i] << std::endl; } return 0; }
由于凸壳算法仅对输入点的坐标和方向测试进行比较，因此我们可以选择提供精确谓词但没有精确的几何构造的核。
凸 hull 函数采用三个参数，输入的开始和结束指针以及结果数组的开始指针。该函数将指针返回到结果数组中，该数组位于写入的最后一个凸壳点的后面，因此指针差值告诉我们凸壳上有多少个点。
2.2 vector中点的凸壳
在第二个示例中，我们将内置数组替换为标准模板库的std::vector
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h> #include <CGAL/convex_hull_2.h> #include <vector> typedef CGAL::Exact_predicates_inexact_constructions_kernel K; typedef K::Point_2 Point_2; typedef std::vector<Point_2> Points; int main() { Points points, result; points.push_back(Point_2(0,0)); points.push_back(Point_2(10,0)); points.push_back(Point_2(10,10)); points.push_back(Point_2(6,5)); points.push_back(Point_2(4,1)); CGAL::convex_hull_2( points.begin(), points.end(), std::back_inserter(result) ); std::cout << result.size() << " points on the convex hull" << std::endl; return 0; }
我们在向量中放置了一些点，调用类std::vector的push_back()方法。
然后，我们调用凸壳函数。前两个参数points.begin(),points.end()是迭代器，它们是指针的推广：它们可以取值(dereferenced)和递增(incremented)。凸壳函数是通用的，因为它将任何可以取值和递增的内容作为输入。
第三个参数是将结果写入的位置。在前面的示例中，我们提供了一个指向已分配内存的指针。此类指针的泛化是输出迭代器，它允许递增并为取值(dereferenced)的迭代器赋值。在这个例子中，我们从一个空的向量开始，它根据需要增长。因此，我们不能简单地传递它result.begin()，而是由帮助器函数生成的输出迭代器std::back_inserter(result)。此输出迭代器在递增时不执行任何操作，而是调用result.push_back(..)赋值。
如果您知道 STL，即标准模板库，那么上述内容非常有意义，因为这是 STL 将算法与容器分离的方式。如果您不了解STL，最好先熟悉其基本思想。
3 关于内核(Kernels)和特性(Traits)类
在本节中，我们将展示如何表达必须满足的要求，以便convex_hull_2()这样的函数可以在任意点类型上使用。
如果您查看该函数convex_hull_2()的手册页和其他 2D 凸壳算法，您会发现它们有两个版本。在到目前为止我们看到的示例中，函数采用两个迭代器作为输入点的范围，一个输出迭代器用于将结果写入。第二个版本有一个额外的模板参数Traits，以及一个这种类型的附加参数。
template<class InputIterator , class OutputIterator , class Traits > OutputIterator convex_hull_2(InputIterator first, InputIterator beyond, OutputIterator result, const Traits & ch_traits)
典型的凸壳算法使用的几何基元（primitives）是什么？当然，这取决于算法，让我们考虑一下什么是最简单的有效算法，即所谓的"Graham/Andrew Scan"。此算法首先从左到右对点进行排序，然后通过从排序列表中添加一个点又一个点来增量构建凸壳。要做到这一点，它必须至少知道一些点类型(point type)，它应该有一些想法如何对这些点进行排序(sort)，并且它必须能够评估三重点的方向。
这就是模板参数Traits的用武之地。ch_graham_andrew()必须提供以下嵌套类型：
Traits::Point_2Traits::Less_xy_2Traits::Left_turn_2Traits::Equal_2
如您所猜，Left_turn_2负责方向测试，Less_xy_2用于对点进行排序。这些类型必须满足的要求在https://doc.cgal.org/latest/Convex_hull_2/classConvexHullTraits__2.html
由于一个简单的原因，这些类型被重新组合。另一种选择是一个相当冗长的函数模板，以及一个更长的函数调用。
template <class InputIterator, class OutputIterator, class Point_2, class Less_xy_2, class Left_turn_2, class Equal_2> OutputIterator ch_graham_andrew( InputIterator first, InputIterator beyond, OutputIterator result);
有两个明显的问题：什么可以用作此模板参数的参数？为什么我们要有模板参数？
为了回答第一个问题，CGAL概念https://doc.cgal.org/latest/Kernel_23/classKernel.html的任何模型都提供了概念所需的内容。https://doc.cgal.org/latest/Convex_hull_2/classConvexHullTraits__2.html
至于第二个问题，考虑一个应用程序，我们想要计算投影到yz平面中的3D点的凸壳。使用Projection_traits_yz_3类，这是对上一示例的一个小修改。
#include <iostream> #include <iterator> #include <CGAL/Exact_predicates_inexact_constructions_kernel.h> #include <CGAL/Projection_traits_yz_3.h> #include <CGAL/convex_hull_2.h> typedef CGAL::Exact_predicates_inexact_constructions_kernel K3; typedef CGAL::Projection_traits_yz_3<K3> K; typedef K::Point_2 Point_2; int main() { std::istream_iterator< Point_2 > input_begin( std::cin ); std::istream_iterator< Point_2 > input_end; std::ostream_iterator< Point_2 > output( std::cout, "\n" ); CGAL::convex_hull_2( input_begin, input_end, output, K() ); return 0; }
另一个示例是关于用户定义的点类型，或来自 CGAL 以外的第三方库的点类型。将点类型与此点类型所需的谓词（predicates）一起放在类的作用域中，就可以使用这些点运行convex_hull_2()。
最后，让我们解释一下为什么一个特征对象(traits object)会传递给凸壳函数？它将允许使用更一般的投影特征对象来存储状态，例如，如果投影平面是由一个方向给出的，该方向在类Projection_traits_yz_3中是硬连线（hardwired）的。
4 概念(Concepts)和模型(Models)
在上一节中，我们写道："CGAL概念内核的任何模型都提供了概念所需的内容ConvexHullTraits_2。
概念(concept)是对类型(type)的一组要求，即它具有某些嵌套类型，某些成员函数，或者带有某些以类型为主的自由函数。概念的模型是满足概念要求的类(class)。
让我们看一下以下函数。
template <typename T> T duplicate(T t) { return t; }
如果你想用一个类C来实例化这个函数，类C至少必须提供一个复制构造函数，我们说这个类必须是可复制（CopyConstructible）的模型。单例类不满足此要求。
另一个例子是这个函数:
template <typename T> T& std::min(const T& a, const T& b) { return (a<b)?a:b; }
函数只有当operator<(…)在T中定义时才能编译，也就是说这个type必须是一个可比较（LessThanComparable）的模型。
具有所需自由函数的概念的一个例子是CGAL包中的HalfedgeListGraphCGAL和Boost Graph Library。为了成为一个HalfedgeListGraph的模型,类G必须有一个全局函数halfedges(const G&)。
具有必需特征类的概念的示例是InputIterator 。对于类 InputIterator，std::iterator_traits 的特化模型必须存在（或者泛型模板必须适用）。
5 更多阅读
我们还推荐来自Addison-Wesley的Nicolai M. Josuttis的标准教科书"The C++ Standard Library， A Tutorial and Reference"，或Matthew H. Austern的"Generic Programming and the STL"，用于STL及其概念和模型的概念。
CGAL 的其他资源是教程的其余部分和 https://www.cgal.org/ 的用户支持页面。
