Hello World

Author

CGAL编辑委员会

本教程面向了解C++并具备基本几何算法知识的CGAL新手。第一部分展示如何定义点和线段类，以及如何对它们应用几何谓词。该部分还会提醒读者在使用浮点数作为坐标时存在的严重问题。第二部分将介绍一个典型的CGAL函数，用于计算二维凸包。第三部分解释我们所说的特征类（Traits class）的含义，第四部分则阐述概念（concept）和模型（model）的概念。

三个点和一条线段

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

所有CGAL头文件都位于include/CGAL子目录中。所有CGAL类和函数都在CGAL命名空间中。类名以大写字母开头，全局函数以小写字母开头，常量则全部大写。对象的维度通过后缀表示。

几何基元（如点类型）在核（kernel）中定义。在这个第一个示例中，我们选择的核使用双精度浮点数来表示点的笛卡尔坐标。

除了类型之外，我们还会看到谓词（predicates），如三点方向测试，以及构造（constructions），如距离和中点计算。谓词具有有限的可能结果集，而构造则产生数值或其他几何实体。

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

使用浮点数进行几何计算可能会带来意外结果，如下例所示。

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

阅读代码时，我们可能会认为它会打印三次"collinear"（共线）。然而，实际输出如下：

not collinear
not collinear
collinear

这是因为这些分数无法用双精度数精确表示，共线性测试在内部会计算一个3x3矩阵的行列式，其结果接近但不等于零，因此前两次测试显示非共线。

类似的情况也可能发生在执行左转的点上，由于行列式计算过程中的舍入误差，这些点可能看起来是共线的，或者执行右转。

如果你需要确保数字以其完整精度进行解释，可以使用执行精确谓词和精确构造的CGAL核。

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

以下是输出结果，可能仍会让你感到惊讶：

not collinear
collinear
collinear

在第一个代码块中，点仍然不共线，原因很简单：你看到的文本坐标首先被转换为浮点数。当它们随后被转换为任意精度有理数时，它们精确表示了浮点数，而不是原始文本！

第二个代码块则不同，它对应于从文件读取数字。任意精度有理数直接从字符串构造，因此它们精确表示了文本。

在第三个代码块中，你可以看到构造操作（如中点构造）是精确的，正如核类型的名称所暗示的那样。

在许多情况下，你会遇到"精确"的浮点数，它们是由某些应用程序计算得出或从传感器获取的。它们不是字符串"0.1"或通过"1.0/10.0"即时计算的，而是完整精度的浮点数。如果它们作为输入提供给不进行构造的算法，你可以使用提供精确谓词但不精确构造的核。凸包算法就是一个这样的例子，我们将在下一节中看到。输出是输入的子集，算法只比较坐标和执行方向测试。

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

大多数CGAL包都会说明应该使用或支持哪种类型的核。

点序列的凸包

本节的所有示例都计算点集的二维凸包。我们将展示算法如何通过表示点范围的起始/结束迭代器对获取输入，并将结果（在示例中是凸包上的点）写入输出迭代器。

内置数组中点的凸包

在第一个示例中，输入是一个包含五个点的数组。由于这些点的凸包是输入的子集，因此提供相同大小的数组来存储结果是安全的。

File 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提供了几种核。由于凸包算法只进行坐标比较和输入点的方向测试，我们可以选择提供精确谓词但不提供精确几何构造的核。

凸包函数接受三个参数：输入的起始和结束指针，以及结果数组的起始指针。该函数返回结果数组中最后一个凸包点之后的指针，因此指针差可以告诉我们凸包上有多少个点。

Vector中点的凸包

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

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

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

然后我们调用凸包函数。前两个参数points.begin()和points.end()是迭代器，它们是指针的泛化：可以解引用和递增。凸包函数是泛型的，意味着它可以接受任何可以解引用和递增的输入。

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

如果你了解STL（标准模板库），上述内容完全合理，因为这就是STL将算法与容器解耦的方式。如果你不了解STL，最好先熟悉其基本概念。

关于核和特征类

在本节中，我们将说明如何表达使用任意点类型的convex_hull_2()函数所必须满足的要求。

如果你查看convex_hull_2()函数和其他二维凸包算法的手册页，你会看到它们有两个版本。在我们之前看到的示例中，函数接受输入点范围的两个迭代器和用于写入结果的输出迭代器。第二个版本有一个额外的模板参数Traits和该类型的额外参数。

template<class InputIterator , class OutputIterator , class Traits >
OutputIterator
convex_hull_2(InputIterator first,
              InputIterator beyond,
              OutputIterator result,
              const Traits & ch_traits)

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

这就是模板参数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概念所要求的内容。

至于第二个问题，想象一个需要计算三维点投影到yz平面的凸包的应用。使用Projection_traits_yz_3类，这只是前一个示例的小修改。

File 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()。

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

概念和模型

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

概念（concept）是对类型的一组要求，即它必须具有某些嵌套类型、某些成员函数，或者带有以该类型为参数的某些自由函数。概念的模型（model）是满足概念要求的类。

让我们看看下面的函数。

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

只有当用作T的类型定义了operator<(..)时，这个函数才能编译，我们说该类型必须是LessThanComparable的模型。

需要自由函数的概念的一个例子是CGAL包PkgBGL中的`HalfedgeListGraph`。为了成为`HalfedgeListGraph`的模型，类`G`必须有一个全局函数`halfedges(const G&)`等。

需要特征类的概念的一个例子是InputIterator。对于InputIterator的模型，必须存在类 std::iterator_traits 的特化（或者通用模板必须适用）。

进一步阅读

我们还推荐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/上的用户支持页面。