1.安装依赖库

• 默认已经安装好CMake软件

1.1 boost

• (1) 直接apt包安装：Ubuntu 20.04默认安装1.7.1版本的库，对应只能编译CGAL的5.6.2版本库

>> sudo apt-get update
>> sudo apt-get install libboost-all-dev

• (2) 源码安装：使用源码安装最新版本boost，后面CGAL才能安装最新版本，目前V6.01版本要求boost库最低是1.7.2版本的

>> sudo apt-get install zlib1g-dev libbz2-dev
>> wget https://archives.boost.io/release/1.86.0/source/boost_1_86_0.zip
>> unzip boost_1_86_0.zip
>> cd boost_1_86_0 && ./bootstrap.sh --with-libraries=all && ./b2 && sudo ./b2 install

1.2 GNU Multiple Precision Arithmetic

• GMP下载地址

>> wget https://gmplib.org/download/gmp/gmp-6.3.0.tar.xz
>> tar -xf gmp-6.3.0.tar.xz 
>> mv gmp-6.3.0 gmp 
>> cd gmp && ./configure && make -j 8 && sudo make install

1.3 GNU Multiple Precision Floating-Point Reliably

• MPFR下载地址

>> wget https://www.mpfr.org/mpfr-current/mpfr-4.2.1.zip
>> unzip mpfr-4.2.1.zip -d mpfr
>> cd mpfr && ./configure && make -j 8 && sudo make install

2.CGAL库编译安装

• CGAL是纯头文件库，安装过程十分简单：

# 1.下载源码
>> git clone git@github.com:CGAL/cgal.git
# 2.切换tag：最新版需要boost库版本为Version 1.72 or later
# 而ubuntu20.04默认安装的boost库版本为1.71，如果是源码安装的boost库，这一步可以不切换
>> cd cgal && git checkout v5.6.2
>> mkdir build && cd build && cmake .. -DCMAKE_BUILD_TYPE=Release 
>> make && sudo make install
# 3.需要编译例子时
>> cd build && cmake .. -DCMAKE_BUILD_TYPE=Release -DWITH_examples=ON
# 3.1 全部例子
>> make examples
# 3.2 单个例子
>> cd examples/[具体例子] && make -j 8

3.CGAL实例使用

3.1 点和线段

​ CGAL类和函数都在命名空间CGAL中，命名规则如下：

class：大写字母开头，维度以后缀表示
global function：小写字母开头
const variable：全部大写

​ 当前例子中，使用两个double类型数构成一个点Point_2的笛卡尔坐标，两个点又构成一个线段Segment_2，这些类型都在 Kernel内中定义的。除了类型外，还有 Predicate，如判断三点方向、计算距离和中点等。

#include <iostream>
#include <CGAL/Simple_cartesian.h>

// 定义Kernel类
typedef CGAL::Simple_cartesian<double> Kernel;
// 点
typedef Kernel::Point_2 Point_2;
// 线段
typedef Kernel::Segment_2 Segment_2;

int main()
{
  // 1.构造两个点
  Point_2 p(1,1), q(10,10);

  std::cout << "p = " << p << std::endl;
  std::cout << "q = " << q.x() << " " << q.y() << std::endl;

  // 2.计算两个点之间距离
  std::cout << "sqdist(p,q) = "
            << CGAL::squared_distance(p,q) << std::endl;

  // 3.构造线段
  Segment_2 s(p,q);
  Point_2 m(5, 9);

  std::cout << "m = " << m << std::endl;
  // 4.计算点到线段之间距离
  std::cout << "sqdist(Segment_2(p,q), m) = "
            << CGAL::squared_distance(s,m) << std::endl;

  std::cout << "p, q, and m ";
  // 5.计算三个点之间方向：m与p,q构成线段之间关系
  switch (CGAL::orientation(p,q,m)){
  // 5.1 共线
  case CGAL::COLLINEAR:
    std::cout << "are collinear\n";
    break;
  // 5.2 左边
  case CGAL::LEFT_TURN:
    std::cout << "make a left turn\n";
    break;
  // 5.3 右边
  case CGAL::RIGHT_TURN:
    std::cout << "make a right turn\n";
    break;
  }

  // 6.计算中点
  std::cout << " midpoint(p,q) = " << CGAL::midpoint(p,q) << std::endl;
  return 0;
}

• 当前示例位于examples/Kernel_23目录下，编译完所有例子后，运行一下：

>> cd examples/Kernel_23
>> ./points_and_segment
p = 1 1
q = 10 10
sqdist(p,q) = 162
m = 5 9
sqdist(Segment_2(p,q), m) = 8
p, q, and m make a left turn
 midpoint(p,q) = 5.5 5.5

3.2 浮点型坐标

​ 使用浮点数进行几何运算时，由于数值精度问题，可能得不到期望的结果：

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

​ 运行：

>> cd examples/Kernel_23
>> ./surprising
not collinear
not collinear
collinear

​ 按照代码逻辑，应该打印三次“共线”，但实际却是两次不“共线“和一次”共线“，这是因为这些分数不能表示为双精度 double类型的数，共线测试内部会计算一个​3\times 3矩阵的行列式，这个行列式的值将会接近但不等于0，因此会将前面两个判定为不”共线“。

​ 类似的情况也可能发生在左转的点上，但由于行列式在计算过程中的舍入误差，这些点可能会被判定为共线或执行右转。如果必须保证输入坐标是绝对浮点型精度的，那么可以使用如下CGAL的 Kernel来执行精准 predicates

和 constructions提取。

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

​ 执行一下：

>> cd examples/Kernel_23
>> ./exact
not collinear
collinear
collinear

​ 第一块主要问题就在浮点运算问题，第二个块能解析为全精度是因为从字符串流中输入后，封装坐标不再是 double类型，而是一个 gmp对象，从而使得运算精度不同。

4.参考资料

• [1] CGAL 6.0.1 - Manual: Hello World
• [2] CGAL 入门基础
• [3] CGAL入门解释