文章目录
1.介绍
计算几何算法库(CGAL)是用c++编写的，由三个主要部分组成。第一部分是内核，它由固定大小的不可修改的几何原语对象和对这些原语对象的操作组成。这些对象既表示为独立的类(由表示类参数化，表示类指定用于计算的底层数字类型)，也表示为内核类的成员(允许内核具有更大的灵活性和适应性)。第二部分是基本几何数据结构和算法的集合，这些数据结构和算法由特征类参数化，这些特征类定义了数据结构或算法与其使用的原语之间的接口。在许多情况下，CGAL中提供的内核类可以用作这些数据结构和算法的特征类。库的第三部分包括非几何支持工具，如循环器、随机源、用于调试的I/O支持以及用于将CGAL连接到各种可视化工具的接口。
参考手册的这一部分介绍了内核。核包含恒定大小的对象，如点、矢量、方向、直线、射线、线段、三角形、等距矩形和四面体。每种类型都有一组函数，可以应用于该类型的对象。您通常会找到访问函数(例如点的坐标)，测试点相对于对象的位置，返回边界框，对象的长度或面积的函数，等等。CGAL内核进一步包含了仿射变换、交叉点检测和计算、距离计算等基本运算。
1.1.鲁棒性
理论论文中提出的几乎所有几何算法的正确性证明都假定了实数精确计算。这导致了几何算法实现的一个基本问题。在实现中，精确的实数运算常常被不精确的浮点运算所取代。这通常会为许多输入数据带来可接受的结果。然而，即使对于最简单的几何算法的实现，这种简化有时也不起作用。由不准确的算术引入的舍入误差可能导致不一致的决策，从而导致某些正确输入数据的意外失败。有许多方法可以解决这个问题，其中之一是精确计算(计算得如此精确，以至于算法做出的所有决策都是精确的)，这在许多情况下是可能的，但比标准浮点算法更昂贵。C. M. Hoffmann[3]，[2]阐述了几何算法实现中出现的一些问题，并讨论了解决这些问题的一些方法。最近的综述在[5]中给出。精确的计算范式由Yap和dub[6]和Yap[7]讨论。
在CGAL中，您可以选择基础的数字类型和算法。您可以同时使用不同类型的算术，并且可以很容易地更改选择，例如用于测试。因此，您可以在快速但偶尔不精确的算术实现和保证精确计算和精确结果的实现之间进行选择。当然，您必须为执行时间和存储空间的准确性付费。有关数字类型及其功能和性能的更多详细信息，请参阅专用章节。
2.内核表示
我们的研究对象是d维仿射欧几里得空间。这里我们主要关注情况d=2和d=3。那个空间里的物体是点的集合。表示这些点的一种常用方法是使用笛卡尔坐标，它假设一个参考系(一个原点和d个正交轴)。在这个框架中，一个点由一个d元组(c0,c1，…，cd−1)表示，因此是底层线性空间中的向量。每个点都由这样的笛卡尔坐标唯一地表示。另一种表示点的方法是齐次坐标。在该框架中，点由(d+1)-元组(h0,h1，…，hd)表示。通过公式ci=hi/hd，可以计算出笛卡尔坐标(c0,c1，…，cd−1)对应的点。注意齐次坐标不是唯一的。为λ≠0元组(h0, h1,…,hd)和(λ⋅h0,λ⋅h1,…,λ⋅hd)表示相同的点。对于笛卡尔坐标(c0,c1，…，cd−1)的点，一个可能的齐次表示是(c0,c1，…，cd−1,1)。齐次坐标实际上允许在更一般的空间，射影空间Pd中表示物体。在CGAL中，我们不计算射影几何。相反，我们使用齐次坐标来避免除法操作，因为额外的坐标可以作为公分母。
2.1.通过参数化实现泛型
几乎所有内核对象(以及相应的函数)都是带有参数的模板，该参数允许用户选择内核对象的表示形式。用作此参数实参的类型必须满足语法和语义上的某些要求。需求列表定义了一个抽象的内核概念。对于所有内核对象类型，类型CGAL::Type< kernel >和Kernel::Type是相同的。
CGAL为核概念提供了四类具体模型，两个基于点的笛卡尔表示，两个基于点的齐次表示。内核对象的接口设计使得它可以很好地使用笛卡尔和同构表示。例如，2D中的点也有一个带有三个参数的构造函数(该点的三个齐次坐标)。用内核类参数化的公共接口允许开发独立于所选表示的代码。我们说模型的“族”，因为这两个族也都是参数化的。用户可以选择用于表示坐标的数字类型。
由于稍后会说明的原因，内核类为数字类型提供了两个类型名，即kernel::FT和kernel::RT。类型Kernel::FT必须满足在CGAL中称为FieldNumberType的要求。这大致意味着Kernel::FT是这样一种类型，其操作+，−，和/的定义语义(近似)与数学意义上的字段的语义相对应。注意，严格地说，内置类型int不满足字段类型的要求，因为int对应的是环的元素而不是字段，特别是操作/不是的逆。对Kernel::RT类型的要求较弱。此类型必须满足CGAL中称为RingNumberType的要求。这大致意味着Kernel::RT是这样一种类型，其操作+，−，*的定义语义(近似)与数学意义上的环的定义语义相对应。
2.2.笛卡尔核
与Cartesian< FieldNumberType>你可以选择坐标的笛卡尔表示。当你选择笛卡尔表示法时你必须同时声明坐标的类型。与笛卡尔表示类一起使用的数字类型应该是如上所述的FieldNumberType。如上所述，内置类型int不是FieldNumberType。然而，对于一些笛卡尔表示的计算，不需要除法操作，即在这种情况下，RingNumberType就足够了。使用Cartesian<FieldNumberType>::FT和Cartesian<FieldNumberType>::RT都映射到FieldNumberType。
Cartesian< FieldNumberType>在内部使用引用计数以节省复制成本。CGAL还提供了Simple_cartesian<FieldNumberType>，这是一个使用笛卡尔表示但不使用引用计数的内核。使用Simple_cartesian<FieldNumberType>调试更容易，因为坐标存储在类中，因此可以直接访问坐标。根据算法的不同，它也可能比Cartesian<FieldNumberType>效率略高或略低。同样，在Simple_cartesian<FieldNumberType>Simple_cartesian<FieldNumberType>::FT和Simple_cartesian<FieldNumberType>::RT都映射到FieldNumberType。
2.3.同质核
齐次坐标允许在数值计算中避免除法运算，因为额外的坐标可以作为公分母。避免除法对于精确的几何计算是有用的。与Homogeneous< RingNumberType>您可以为内核对象的坐标选择同构表示。对于笛卡尔表示，必须声明用于存储坐标的类型。由于同构表示不使用除法，因此与同构表示类相关联的数字类型必须是弱概念RingNumberType的模型。然而，这个核提供的一些操作涉及除法，例如计算距离的平方或笛卡尔坐标。为了保持对Homogeneous数字类型参数的低要求，将数字类型Quotient<RingNumberType>用于需要除法的操作。这个数字类型可以看作是一个适配器，它将RingNumberType转换为FieldNumberType。它将数字维持为商，即分子和分母。对于homoous<RingNumberType>， homoous<RingNumberType>::FT等于Quotient<RingNumberType>， homoous<RingNumberType>::RT等于RingNumberType。
Homogeneous< RingNumberType>在内部使用引用计数以节省复制成本。CGAL还提供了simple_homogenous <RingNumberType>，这是一个使用同构表示但不使用引用计数的内核。使用simple_homoious <RingNumberType>调试更容易，因为坐标存储在类中，因此可以直接访问坐标。根据算法的不同，它也可能比homogeneousringnumbertype>效率更高或更低。同样，在simple_homogenous <RingNumberType>类型simple_homoous<RingNumberType>::FT等于Quotient<RingNumberType>而Simple_homogeneous<RingNumberType>::RT等于RingNumberType。
2.4.命名约定
内核类的使用不仅避免了问题，而且使所有的CGAL类非常统一。它们通常包括:
几何对象的大写基名，如 Point, Segment, or Triangle。
下划线后跟对象的维度，例如_2、_3或_d。
作为参数的内核类，其本身用数字类型参数化，例如Cartesian<double>或Homogeneous< leda_integer>。
2.5.内核作为trait类
CGAL基本库中的算法和数据结构由一个trait类参数化，该trait类包含了算法或数据结构所操作的对象以及相应的操作。对于基本库中的大多数算法和数据结构，您可以使用内核作为trait类。对于一些算法，你甚至不需要指定内核;使用传递给算法的几何对象的类型自动检测它。在其他一些情况下，算法或数据结构需要的不仅仅是内核概念所提供的。在这些情况下，内核不能用作trait类。
2.6.选择内核和预定义内核
如果从积分笛卡尔坐标开始，许多几何计算将只涉及积分数值。特别是，对于只计算谓词的几何计算来说，这是正确的，这相当于行列式计算。例如点集的三角剖分和凸包计算。在这种情况下，笛卡尔表示可能是首选，即使是环类型。您可以使用精度有限的整数类型，如int或long，使用double来表示整数(它们的尾数比int有更多的位，并且可以很好地溢出)，或者使用任意精度的整数类型，如用于GMP整数的包装器Gmpz、leda_integer或MP_Float。注意，除非使用任意精度环类型，否则可能由于溢出而产生不正确的结果。
如果要构造新的点，例如两条直线的交点，笛卡尔坐标的计算通常涉及除法。因此，需要使用具有笛卡尔表示的FieldNumberType，或者切换到同质表示。double类型是FieldNumberType的一个(虽然不精确)模型。您还可以将任何RingNumberType放入Quotient适配器中，以获得一个字段类型，然后可以将其放入笛卡尔格式。但是在RingNumberType上使用同构表示通常是更好的选择。其他有效的FieldNumberTypes是leda_rational和leda_real。
如果计算的可靠性对您来说至关重要，那么正确的选择可能是保证精确计算的数字类型。Filtered_kernel提供了一种应用过滤技术的方法[1]，以实现具有精确和高效谓词的内核。还有一些人更喜欢内置的double类型，因为他们需要速度，可以使用近似的结果，甚至是算法，有时会崩溃或由于累积的舍入误差而计算不正确的结果。
预定义的内核
为了方便用户使用，CGAL为一般有用的内核提供了5种类型。它们都是笛卡尔核。它们都支持从双笛卡尔坐标中构造点。所有这5个核都提供了精确的几何谓词。
它们处理几何结构的方式不同:
Exact_predicates_inexact_constructions_kernel:提供精确的几何谓词，但几何结构可能由于舍入错误而不精确。然而，对于许多CGAL算法来说，它已经足够了，并且比下面具有精确结构的内核更快。
Exact_predicates_exact_constructions_kernel:除了精确的几何谓词外，还提供精确的几何结构。
Exact_predicates_exact_constructions_kernel_with_sqrt:与Exact_predicates_exact_constructions_kernel相同，但数字类型是概念FieldWithSqrt的模型。[1]。
Exact_predicates_exact_constructions_kernel_with_kth_root与Exact_predicates_exact_constructions_kernel相同，但数字类型是概念FieldWithKthRoot的模型。[1]。
Exact_predicates_exact_constructions_kernel_with_root_of:与Exact_predicates_exact_constructions_kernel相同，但数字类型是概念FieldWithRootOf的模型。[1]。
3.几何内核
3.1.点与向量
在CGAL中，我们严格区分点、向量和方向。**一个点是欧几里得空间Ed中的一个点，一个向量是两个点p2 p1的差表示方向和从p1到p2在向量空间Rd中的距离，一个方向是一个我们不考虑它长度的向量。**它们是不同的数学概念。例如，它们在仿射变换下的表现是不同的，在仿射几何中添加两个点是没有意义的。通过将它们放在不同的类中，我们不仅可以获得更清晰的代码，还可以通过编译器进行类型检查，从而避免歧义表达式。因此，做这种区分是值得的。
CGAL定义了一个ORIGIN类型的符号常量ORIGIN，它表示原点上的点。这个常数用于点和向量之间的转换。从点p减去它得到p的轨迹向量。
Cartesian<double>::Point_2 p(1.0, 1.0), q;
Cartesian<double>::Vector_2 v;
v = p - ORIGIN;//两点相减得到向量
q = ORIGIN + v;//点和向量相加得到点
assert( p == q );
为了得到一个向量v对应的点，你只需要在ORIGIN上加上v。如果你想确定点q在两个点p1和p2之间，你可以写：
q = p_1 + (p_2 - p_1) / 2.0;
请注意，这些结构不涉及与当前可用的表示类进行转换的任何性能开销。
3.2.内核对象
除了点(Kernel::Point_2, Kernel::Point_3)，向量(Kernel::Vector_2, Kernel::Vector_3)，方向(Kernel::Direction_2, Kernel::Direction_3)， CGAL还提供直线，射线，线段，平面，三角形，四面体，等边矩形，等边长方体，圆和球。
CGAL中的行(Kernel::Line_2, Kernel::Line_3)是定向的。在二维空间中，它们将平面划分为正侧和负侧。直线上的任意两点都有这条直线的方向。一条射线(Kernel::Ray_2, Kernel::Ray_3)是一条线上的半无限区间，这条线从这个区间的有限端点指向这个区间内的任何其他点。段(Kernel::Segment_2, Kernel::Segment_3)是有向直线上的有界区间，其端点是有序的，因此它们与直线的方向相同。
平面是E3中2维的仿射子空间，穿过三个点，或一个点和一条线、射线或线段。CGAL提供了环境空间E3中的任意平面与该空间中E2的嵌入之间的对应关系。就像线一样，平面是有方向的，并将空间划分为正、负两个面。在CGAL中，没有针对半空间的特殊类。2D和3D中的半空间应该分别由有方向的线和平面表示。
对于多边形和多面体，内核提供三角形、等边矩形、等边长方体和四面体。更复杂的多边形[3]和多面体或多面体表面可以从基本库(Polygon_2, Polyhedron_3)中获得，因此它们不属于内核的一部分。与任何约旦曲线一样，三角形、等距矩形和圆形将平面分成两个区域，一个有界，一个无界。
3.3.方位和相对位置
CGAL中的几何对象具有测试点相对于对象的位置的成员函数。全维物体及其边界用相同的类型表示，例如，半空间和超平面没有区别，球、盘和圆也没有区别。这样的对象将环境空间分成两个全维部分，一个有界部分和一个无界部分(例如圆)，或者两个无界部分(例如超平面)。默认情况下，这些对象是定向的，也就是说，产生的一部分称为正侧，另一部分称为负侧。这两个都可以是无界的。
这些对象有一个成员函数oriented_side()，用于确定测试点是在正侧、负侧还是在有向边界上。这些函数返回一个类型为orientted_side的值。那些将空间划分为有界部分和无界部分的对象有一个返回类型为bounded_side的成员函数bounded_side()。
如果对象是低维的，例如三维空间中的三角形或二维空间中的线段，则只需要测试一个点是否属于该对象。这个成员函数叫做has_on()，它接受一个点作为参数并返回一个布尔值。
4.谓语和结构
4.1.谓词
**谓词是几何内核的核心。它们是组成几何算法和封装决策的基本单元。**因此，它们的正确性对于控制流和几何算法实现的正确性至关重要。CGAL在广义上使用谓词一词。不仅返回布尔值的组件被称为谓词，而且返回枚举类型(如Comparison_result或Orientation)的组件也被称为谓词。我们说组件，是因为谓词被实现为函数和函数对象(由内核类提供)。
CGAL为点集的方向(orientation()， left_turn()， right_turn()， collinear()， coplanar())提供了谓词，用于根据给定的顺序比较点，特别是用于比较笛卡尔坐标(例如lexicographally_xy_smaller())，圆内和球内测试，以及比较距离的谓词。
4.2.结构
生成既不是bool类型也不是enum类型的对象的函数和函数对象称为构造。构造涉及新数值的计算，并且可能由于舍入误差而不精确，除非使用具有精确数字类型的内核。
仿射变换(Kernel::Aff_transformation_2, Kernel::Aff_transformation_3)允许在任意仿射变换下生成新的对象实例。这些转换包括平移、旋转(仅在2D中)和缩放。内核中的大多数几何对象都有一个成员函数transform(Aff_transformation t)，它将转换应用于对象实例。
CGAL还提供了一组函数，用于检测或计算2D核的对象与3D核中的许多对象之间的交集，以及计算它们的平方距离的函数。此外，内核对象的一些成员函数是构造函数。
所以有计算欧几里德距离平方的例程，但是没有计算距离本身的例程。为什么?首先，这两个值可以很容易地相互推导(通过取平方根或平方)。因此，只提供一个而不提供另一个对用户来说只是一个小小的不便。其次，通常任何一个值都可以使用。这是比较(平方)距离的例子。第三，库想要激发距离的平方而不是距离的使用。可以在更多的情况下计算距离的平方，并且计算成本更低。我们没有提供更自然的例程，距离例程的问题是它需要根号运算。这有两个缺点:
4.3.交集和变量返回类型
有些函数，例如intersection()，可以返回不同类型的对象。为了以一种类型安全的方式实现这一点，CGAL使用boost::optional<boost:: variant<T…比;比;其中T…是所有可能产生的几何对象的列表。交叉口的确切结果类型可以通过占位符类型说明符auto指定。
4.4.例子
在下面的例子中，auto用于指定交叉计算返回值的类型:
typedef CGAL::Simple_cartesian<double> K;
typedef K::Point_2 Point_2;
typedef K::Segment_2 Segment_2;
Segment_2 segment_1, segment_2;
std::cin >> segment_1 >> segment_2;
/* use auto */
auto v = intersection(segment_1, segment_2);
if (v)
{
/* not empty */
if (const Point_2 *p = boost::get<Point_2>(&*v))
{
/* do something with *p */
}
else
{
const Segment_2 *s = boost::get<Segment_2>(&*v);
/* do something with *s */
}
}
else
{
/* empty intersection */
}
4.5.建构性谓词
为了测试点p相对于由三个点q,r和s定义的平面的位置，人们可能会构造平面Kernel::Plane_3(q,r,s)并使用方法orientted_side §。如果对平面进行多次测试，这可能是值得的。然而，除非数字类型是精确的，否则构造的平面只是近似值，舍入误差可能导致orientted_side §返回与p、q、r和s的实际方向不同的方向。
在CGAL中，我们提供了这样的谓词，在这些谓词中，这些几何决策是直接通过参考输入点p, q, r, s来做出的，而不需要像平面这样的中间对象。对于上述测试，获得结果的推荐方法是使用方向(p,q,r,s)。对于精确的数字类型，情况是不同的。如果要对同一平面进行多个测试，则构造平面并使用orientted_side §是值得的。
5可扩展内核
本手册部分描述用户如何在现有的CGAL内核中插入用户定义的几何类。用一个例子最好地说明了这一点。
5.1.介绍
CGAL定义了几何核的概念。这样的内核提供了类型、构造对象和广义谓词。CGAL基本库中大多数计算几何算法和数据结构的实现都是用几何特征类来参数化类或函数的。在大多数情况下，这个几何特征类必须是CGAL几何核概念的一个模型(但也有一些例外)。
5.2.举例
假设我们有以下point类，其中坐标存储在双精度数组中，其中还有另一个数据成员color，它显示在构造函数中。
文件 Kernel_23/MyPointC2.h
#pragma once
#include <CGAL/Origin.h>
#include <CGAL/Bbox_2.h>
class MyPointC2 {
private:
double vec[2];
int col;
public:
MyPointC2() : col(0)
{
*vec = 0;
*(vec + 1) = 0;
}
MyPointC2(const double x, const double y, int c = 0)
: col(c)
{
*vec = x;
*(vec + 1) = y;
}
const double& x() const { return *vec; }
const double& y() const { return *(vec + 1); }
double & x() { return *vec; }
double& y() { return *(vec + 1); }
int color() const { return col; }
int& color() { return col; }
bool operator==(const MyPointC2 &p) const
{
return (*vec == *(p.vec)) && (*(vec + 1) == *(p.vec + 1) && (col == p.col));
}
bool operator!=(const MyPointC2 &p) const
{
return !(*this == p);
}
};
如前所述，这个类非常简洁，例如，它没有bbox()方法。人们可能会认为计算边界框的基本库算法(例如，计算多边形的边界框)将无法编译。幸运的是，它可以，因为它不使用几何对象的成员函数，但它使用了仿函数Kernel::Construct_bbox_2。
为了使MyPointC2正确地工作，我们必须提供以下仿函数。
文件 Kernel_23/MyConstruct_bbox_2.h
#ifndef MYCONSTRUCT_BBOX_2_H
#define MYCONSTRUCT_BBOX_2_H
template <class ConstructBbox_2>
class MyConstruct_bbox_2 : public ConstructBbox_2 {
public:
using ConstructBbox_2::operator();//改变父类成员的私有属性
CGAL::Bbox_2 operator()(const MyPointC2& p) const {
return CGAL::Bbox_2(p.x(), p.y(), p.x(), p.y());
}
};
#endif //MYCONSTRUCT_BBOX_2_H#pragma once
/*using 指示使用某命名空间，对命名空间成员进行声明也就是说指明用哪个命名空间的成员
1.using声明(引入单个名称)
using声明是将命名空间中某个名字单独引入到当前作用域。这使得我们在当前作用域下可以直接使用该名字而无需使用作用域限定符::
using std::string;
string s = "123";
using声明可以改变派生类对父类成员的访问控制。
class Base{
protected:
int bn1;
int bn2;
};
class Derived: private Base{ //私有继承
public:
using Base::bn1; //在当前作用域中引入了父类的保护成员, 在当前作用域中可以访问
};
class DerivedAgain: public Derived{ //在Derived的子类中仍然可以访问bn1
};
int main(){
Derived d;
DerivedAgain da;
d.bn1 = 1;
d.bn2 = 2; //error, 'bn2' is a private member of 'Base'
da.bn1 = 3; //ok
std::cout<<d.bn1<<std::endl;
return 0;
}
尽管Derived是Base的私有继承，但是通过using声明父类的成员，我们就可以在Derived类以及其后续派生类中使用了。
2.using指示(引入命名空间)
using指示就是将一个命名空间中的所有名字全部引入到当前作用域(将命名空间在当前作用域展开)。可能会存在命名冲突的问题
using namespace std; //我们常用的std命名空间展开
3. 类型重定义(替代typedef)
using alias = typename; //使用别名去替代原始类型(重命名)
在C++11中，我们可以使用这样的语法来替代typedef的功能了。
using ULL = unsigned long long; //typedef unsigned long long ULL;
using func = void(*)(int, int); //typedef void(*func)(int, int);
*/
对于点的笛卡尔坐标的随机访问也是类似的。由于坐标存储在双精度数组中，因此可以使用double*作为随机访问迭代器。
文件 Kernel_23/MyConstruct_coord_iterator.h
#ifndef MYCONSTRUCT_COORD_ITERATOR_H
#define MYCONSTRUCT_COORD_ITERATOR_H
class MyConstruct_coord_iterator {
public:
const double* operator()(const MyPointC2& p)
{
return &p.x();
}
const double* operator()(const MyPointC2& p, int)
{
const double* pyptr = &p.y();
pyptr++;
return pyptr;
}
};
#endif //MYCONSTRUCT_COORD_ITERATOR_H
我们要提供的最后一个仿函数是构造点的仿函数。也就是说，您不必强制将Origin作为参数的构造函数添加到类中，也不必强制添加具有同构坐标的构造函数。仿函数是CGAL算法和类之间的一种粘合层。
文件 Kernel_23/MyConstruct_point_2.h
#ifndef MYCONSTRUCT_POINT_2_H
#define MYCONSTRUCT_POINT_2_H
template <typename K, typename OldK>
class MyConstruct_point_2
{
typedef typename K::RT RT;
typedef typename K::Point_2 Point_2;
typedef typename K::Line_2 Line_2;
typedef typename Point_2::Rep Rep;
public:
typedef Point_2 result_type;
// Note : the CGAL::Return_base_tag is really internal CGAL stuff.
// Unfortunately it is needed for optimizing away copy-constructions,
// due to current lack of delegating constructors in the C++ standard.
Rep // Point_2
operator()(CGAL::Return_base_tag, CGAL::Origin o) const
{
return Rep(o);
}
Rep // Point_2
operator()(CGAL::Return_base_tag, const RT& x, const RT& y) const
{
return Rep(x, y);
}
Rep // Point_2
operator()(CGAL::Return_base_tag, const RT& x, const RT& y, const RT& w) const
{
return Rep(x, y, w);
}
Point_2
operator()(const CGAL::Origin&) const
{
return MyPointC2(0, 0, 0);
}
Point_2
operator()(const RT& x, const RT& y) const
{
return MyPointC2(x, y, 0);
}
const Point_2&
operator()(const Point_2 & p) const
{
return p;
}
Point_2
operator()(const Line_2& l) const
{
typename OldK::Construct_point_2 base_operator;
Point_2 p = base_operator(l);
return p;
}
Point_2
operator()(const Line_2& l, int i) const
{
typename OldK::Construct_point_2 base_operator;
return base_operator(l, i);
}
// We need this one, as such a functor is in the Filtered_kernel
Point_2
operator()(const RT& x, const RT& y, const RT& w) const
{
if (w != 1) {
return MyPointC2(x / w, y / w, 0);
}
else {
return MyPointC2(x, y, 0);
}
}
};
#endif //MYCONSTRUCT_POINT_2_H
现在我们准备把拼图拼在一起了。我们不会详细解释它，但是您可以看到有新的point类和仿函数的类型。所有其他类型都是继承的。
文件 Kernel_23/MyKernel.h
#ifndef MYKERNEL_H
#define MYKERNEL_H
#include <CGAL/Cartesian.h>
#include "MyPointC2.h"
#include "MySegmentC2.h"
#include "MyConstruct_bbox_2.h"
#include "MyConstruct_coord_iterator.h"
#include "MyConstruct_point_2.h"
// K_ is the new kernel, and K_Base is the old kernel
template < typename K_, typename K_Base >
class MyCartesian_base
: public K_Base::template Base<K_>::Type
{
typedef typename K_Base::template Base<K_>::Type OldK;
public:
typedef K_ Kernel;
typedef MyPointC2 Point_2;
typedef MySegmentC2<Kernel> Segment_2;
typedef MyConstruct_point_2<Kernel, OldK> Construct_point_2;
typedef const double *Cartesian_const_iterator_2;
typedef MyConstruct_coord_iterator Construct_cartesian_const_iterator_2;
typedef MyConstruct_bbox_2<typename OldK::Construct_bbox_2>
Construct_bbox_2;
Construct_point_2
construct_point_2_object() const
{
return Construct_point_2();
}
Construct_bbox_2
construct_bbox_2_object() const
{
return Construct_bbox_2();
}
Construct_cartesian_const_iterator_2
construct_cartesian_const_iterator_2_object() const
{
return Construct_cartesian_const_iterator_2();
}
template < typename Kernel2 >
struct Base
{
typedef MyCartesian_base<Kernel2, K_Base> Type;
};
};
template < typename FT_ >
struct MyKernel
: public CGAL::Type_equality_wrapper <
MyCartesian_base<MyKernel<FT_>, CGAL::Cartesian<FT_> >,
MyKernel<FT_> >
{};
#endif // MYKERNEL_H
最后，我们给出一个如何使用这个新内核的示例。谓词和构造与新点一起工作，它们可以用来构造段和三角形，以及来自基本库的数据结构，因为Delaunay三角剖分与它们一起工作。内核本身可以通过将其插入Filtered_kernel而变得健壮。
文件 Kernel_23/MyKernel.cpp
#include <CGAL/basic.h>
#include <CGAL/Filtered_kernel.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/squared_distance_2.h>
#include <cassert>
#include "MyKernel.h"
#include "MyPointC2_iostream.h"
typedef MyKernel<double> MK;
typedef CGAL::Filtered_kernel_adaptor<MK> K;
typedef CGAL::Delaunay_triangulation_2<K> Delaunay_triangulation_2;
typedef K::Point_2 Point;
typedef K::Segment_2 Segment;
typedef K::Ray_2 Ray;
typedef K::Line_2 Line;
typedef K::Triangle_2 Triangle;
typedef K::Iso_rectangle_2 Iso_rectangle;
const int RED= 1;
const int BLACK=2;
int main()
{
Point a(0,0), b(1,0), c(1,1), d(0,1);
a.color()=RED;
b.color()=BLACK;
d.color()=RED;
Delaunay_triangulation_2 dt;
dt.insert(a);
K::Orientation_2 orientation;
orientation(a,b,c);
Point p(1,2), q;
p.color() = RED;
q.color() = BLACK;
std::cout << p << std::endl;
K::Compute_squared_distance_2 squared_distance;
std::cout << "squared_distance(a, b) == "
<< squared_distance(a, b) << std::endl;
Segment s1(p,q), s2(a, c);
K::Construct_midpoint_2 construct_midpoint_2;
Point mp = construct_midpoint_2(p,q);
std::cout << "midpoint(" << p << " , " << q << ") == " << mp << std::endl;
assert(s1.source().color() == RED);
K::Intersect_2 intersection;
const auto intersect = intersection(s1, s2);
K::Construct_cartesian_const_iterator_2 construct_it;
K::Cartesian_const_iterator_2 cit = construct_it(a);
assert(*cit == a.x());
cit = construct_it(a,0);
cit--;
assert(*cit == a.y());
Line l1(a,b), l2(p, q);
intersection(l1, l2);
intersection(s1, l1);
Ray r1(d,b), r2(d,c);
intersection(r1, r2);
intersection(r1, l1);
squared_distance(r1, r2);
squared_distance(r1, l2);
squared_distance(r1, s2);
Triangle t1(a,b,c), t2(a,c,d);
intersection(t1, t2);
intersection(t1, l1);
intersection(t1, s1);
intersection(t1, r1);
Iso_rectangle i1(a,c), i2(d,p);
intersection(i1, i2);
intersection(i1, s1);
intersection(i1, r1);
intersection(i1, l1);
t1.orientation();
std::cout << s1.source() << std::endl;
std::cout << t1.bbox() << std::endl;
std::cout << "done" << std::endl;
return 0;
}
5.3.限制
点类必须具有成员函数x()和y()(以及3d点的z())。我们可能会引入处理坐标访问的函数对象。当我们在MyKernel::Point_2和Point_2<MyKernel>之间强制类型相等时，将颜色作为第三个参数的构造函数不可用。
6.投射特征类
有时将2D算法应用于平面上的3D点的投影是有用的。例如三角形地形，它是具有高程的点，或从平行切片重建的表面，其中人们想要检查多边形的简单性或方向。
为此，CGAL提供了几个投影性状类，它们是二维三角形、二维多边形和二维凸壳性状类的性状类概念的模型。投影特征类列在概念的“Is Model Of”部分。
7.设计和实现历史
1995年1月，在乌得勒支大学的一次会议上，Olivier Devillers、Andreas Fabri、Wolfgang Freiseisen、Geert-Jan Giezeman、Mark Overmars、Stefan Schirra、Otfried Schwarzkopf(现在的Otfried Cheong)和Sven Schönherr讨论了CGAL内核的基础。解决了许多设计和软件工程问题，例如命名约定、类的耦合(平面类与深度类层次结构)、内存分配、编程约定、原子对象、点和向量的可变性、存储附加信息、对内核对象的操作的正交性、将多边形等非恒定大小的对象视为动态数据结构(因此不作为(最内部)内核的一部分)。
参加会议的人委托Stefan Schirra编写规范草案。最终的规范草案有意在CGAL的前身c++ gal和Plageo以及LEDA的几何部分上建模。该规范已经突出了点/矢量数据的笛卡尔和同构表示以及数字类型参数化的共存。在讨论草案的过程中，形成了一个内核设计小组。这个小组的成员是Andreas Fabri, Geert-Jan Giezeman, Lutz Kettner, Stefan Schirra和Sven Schönherr。内核设计小组的工作对原始设计进行了重大的改变和改进，例如点和向量之间的强烈分离。也许最重要的改进是为以前不耦合的笛卡尔和同构表示设计了一个共同的上层结构。可以说，内核是由这个小组设计的。内核后来根据herv<s:1> Brönnimann、Bernd Gärtner、Michael Hoffmann和Lutz Kettner的建议进行了修订。
内核的第一个版本是在cgal项目(esprit ltr iv项目编号21957)开始时在内部提供的。从那时起，更多的人通过CGAL邮件列表上的讨论为内核的发展做出了贡献。基于笛卡尔表示法的实现(最初)由Andreas Fabri提供，同质表示法(最初)由Stefan Schirra提供。交点和距离计算由Geert-Jan Giezeman实现。Susan Hert对内核的整体维护做了进一步的工作。Philippe Guigue为3D三角形提供了有效的相交测试。Andreas Fabri、Michael Hoffmann和Sylvain Pion改进了对内核的可扩展性和适应性的支持。Pedro Machado manhes de Castro和Monique Teillaud介绍了3D圆。在2010年，Pierre Alliez, stamophane Tayeb和Camille Wormser为3D三角形添加了相交构造，并为边界框添加了有效的相交测试。