1. cgal在ubuntu下的安装及Hello World的测试

ubuntu下的安装

CGAL安装

参考地址:https://doc.cgal.org/latest/Manual/usage.html

本在在ubuntu下安装:

sudo apt-get install libcgal-dev

安装后的路径:

头文件路径: /usr/include/CGAL

库文件路径: /usr/lib/x86_64-linux-gnu

在qt cretator 中使用示例:

在.pro中添加 LIBS += -lCGAL

教程 Hello World

原文地址:https://doc.cgal.org/latest/Manual/tutorial_hello_world.html

本教程适用于了解 C++ 并具有几何算法基础知识的 CGAL 新手。第一部分展示如何定义点和线段类，以及如何对其应用几何谓词。本节进一步提高了人们的认识，即使用浮点数作为坐标时存在严重问题。在第二部分中，您将遇到一个典型的 CGAL 函数，它计算 2D 凸包。第三部分展示了Traits类的含义，第四部分解释了概念和模型的概念。

1 三点一线

在第一个示例中，我们演示了如何构造一些点和一段，并对它们执行一些基本操作。

所有 CGAL 头文件都位于子目录中include/CGAL。所有 CGAL 类和函数都在命名空间中CGAL。类以大写字母开头，全局函数以小写字母开头，常量全部大写。物体的尺寸用后缀表示。

几何基元，如点类型，是在kernel中定义的。我们为第一个示例选择的内核使用double精度浮点数作为该点的笛卡尔坐标。

除了类型之外，我们还看到诸如三点方向测试之类的谓词，以及诸如距离和中点计算之类的*结构。*谓词具有一组离散的可能结果，而构造则产生一个数字或另一个几何实体。

文件 Kernel_23/points_and_segment.cpp

#include <iostream>
#include <CGAL/Simple_cartesian.h>
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_2 Point_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;
}

正如下一个示例所示，用浮点数处理几何图形可能会令人惊讶。

文件 Kernel_23/surprising.cpp

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

阅读代码，我们可以假设它会打印三次“共线”。然而实际输出如下：

不共线
不共线
共线

这是因为这些分数不能表示为双精度数，并且共线性测试将在内部计算 3x3 矩阵的行列式，该行列式接近但不等于 0，因此前两个测试的非共线性。

执行左转的点可能会发生类似的情况，但由于行列式计算期间的舍入误差，这些点似乎是共线的，或者执行右转。

如果您必须确保以完全精度解释您的数字，您可以使用执行精确谓词和提取结构的 CGAL 内核。

文件 Kernel_23/exact.cpp

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

这是输出，您可能仍然会感到惊讶。

不共线
共线
共线

在第一个块中，点仍然不共线，原因很简单，您看到的文本坐标会变成浮点数。当它们转换为任意精度有理数时，它们精确地表示浮点数，但不是文本！

这在第二个块中有所不同，它对应于从文件中读取数字。然后直接从字符串构造任意精度有理数，以便它们准确地表示文本。

在第三个块中，您会看到中点构造的构造是精确的，正如内核类型的名称所暗示的那样。

在许多情况下，您将拥有“精确”的浮点数，即它们是由某些应用程序计算或从传感器获取的。它们不是字符串“0.1”或动态计算为“1.0/10.0”，而是一个全精度浮点数。如果它们被输入到不进行构造的算法，则可以使用提供精确谓词但不精确构造的内核。一个这样的例子是凸包算法，我们将在下一节中看到。输出是输入的子集，算法仅比较坐标并执行方向测试。

乍一看，执行精确谓词和构造的内核似乎是完美的选择，但性能要求或有限的内存资源使其并非如此。此外，对于许多算法来说，进行精确的构造是无关紧要的。例如，表面网格简化算法通过将边缘折叠到边缘的中点来迭代地收缩边缘。

大多数 CGAL 包都会解释它们应该使用或支持哪种内核。

2 点序列的凸包

本节中的所有示例都计算一组点的 2D 凸包。我们展示了算法将其输入作为表示一系列点的开始/结束迭代器对，并将结果（在示例中为凸包上的点）写入输出迭代器。

2.1 内置数组中的点的凸包

在第一个示例中，我们有一个由五个点组成的数组作为输入。由于这些点的凸包是输入的子集，因此提供一个用于存储具有相同大小的结果的数组是安全的。

文件 Convex_hull_2/array_convex_hull_2.cpp

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

我们在上一节中已经看到 CGAL 附带了多个内核。由于凸包算法仅对输入点的坐标和方向进行比较，因此我们可以选择提供精确谓词但不提供精确几何构造的内核。

凸包函数采用三个参数，即输入的起始指针和结束指针，以及结果数组的起始指针。该函数将指针返回到结果数组中，正好位于最后写入的凸包点后面，因此指针差异告诉我们凸包上有多少个点。

2.2 向量中点的凸包

在第二个示例中，我们将内置数组替换为std::vector标准模板库的数组。

文件 Convex_hull_2/vector_convex_hull_2.cpp

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

我们将一些点放入向量中，调用类push_back()的方法std::vector。

然后我们调用凸包函数。前两个参数points.begin()和points.end()是迭代器，它们是指针的泛化：它们可以取消引用和递增。凸包函数是通用的，因为它将任何可以取消引用和递增的内容作为输入。

第三个参数是结果写入的位置。在前面的示例中，我们提供了指向已分配内存的指针。这种指针的泛化是输出迭代器，它允许递增并向取消引用的迭代器赋值。在此示例中，我们从一个空向量开始，该向量根据需要增长。因此，我们不能简单地传递它result.begin()，而是传递一个由辅助函数生成的输出迭代器std::back_inserter(result)。该输出迭代器在递增时不执行任何操作，而是调用result.push_back(..)赋值。

如果您了解 STL（标准模板库），那么上面的内容就很有意义，因为这就是 STL 将算法与容器解耦的方式。如果您不了解STL，您最好先熟悉一下它的基本思想。

3 关于内核和特征类

在本节中，我们将展示如何表达必须满足的要求，以便类似的函数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)

典型的凸包算法使用哪些几何基元？当然，这取决于算法，所以让我们考虑什么可能是最简单有效的算法，即所谓的“Graham/Andrew Scan”。该算法首先从左到右对点进行排序，然后通过从排序列表中逐个添加点来增量构建凸包。为此，它至少必须了解某种点类型，应该知道如何对这些点进行排序，并且必须能够评估三重点的方向。

这就是模板参数的用武之地Traits。因为ch_graham_andrew()它必须提供以下嵌套类型：

• Traits::Point_2
• Traits::Less_xy_2
• Traits::Left_turn_2
• Traits::Equal_2

你可以猜到，Left_turn_2负责方向测试，而 则Less_xy_2用于对点进行排序。这些类型必须满足的要求已与该概念一起完整记录ConvexHullTraits_2。

这些类型被重新分组的原因很简单。另一种选择是使用相当冗长的函数模板，以及更长的函数调用。

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概念的任何Kernel模型都提供了该概念所需的内容ConvexHullTraits_2

至于第二个问题，考虑一个我们想要计算投影到平面上的 3D 点的凸包的应用程序yz。使用该类Projection_traits_yz_3是对前面示例的一个小修改。

文件 Convex_hull_2/convex_hull_yz.cpp

#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 之外的第三方库的点类型。将点类型与该点类型所需的谓词放在类的范围内，您就可以convex_hull_2()使用这些点来运行。

最后，让我们解释一下为什么将一个traits对象传递给凸包函数？它将允许使用更通用的投影特征对象来存储状态，例如，如果投影平面由方向给出，则该方向在类中是硬连线的Projection_traits_yz_3。

4 概念和模型

在上一节中，我们写道：CGAL概念的任何**模型都提供了该概念所需的内容。 Kernel``ConvexHullTraits_2

概念是对类型的一组要求，即它具有某些嵌套类型、某些成员函数或带有某些以该类型为基础的自由函数*。**概念的模型*是满足概念要求的类。

我们来看看下面的函数。

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<(..)仅当为用作 as 的类型定义时，此函数才会编译T，并且我们说该类型必须是LessThanComparable的模型。

具有所需自由函数的概念的一个示例是HalfedgeListGraphCGAL 包CGAL 和 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 Planning and the STL”，介绍 STL 及其概念和概念。楷模。

CGAL 的其他资源包括教程的其余部分以及https://www.cgal.org/上的用户支持页面。