Hello World CGAL 5.4入门

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 
#include 
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 
#include 
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 
#include 
#include 
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 
#include 
#include 
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 
#include 
#include 
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_2
• Traits::Less_xy_2
• Traits::Left_turn_2
• Traits::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 
#include 
#include 
#include 
#include 
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/ 的用户支持页面。