CGAL官方版

CGAL简介

CGAL可以帮助用户快速建立计算系统。当你需要分析数据和计算时，可以从这个软件中添加相关的计算模块。CGAL中的算法和数据结构是由它们使用的对象类型和工作参数化的。它们与满足特定语法和语义要求的任何特定模板参数一起使用。CGAL提供不同的内核。根据对象的内部表示(如笛卡尔或同质性)，它们可以不同，或者它们可以提供不同的函数(如循环内核)。在创建新的软件包时，作者必须明确指定所用内核的要求，例如，他们可以指定关于算术的要求，作者可以在预定义的内核列表中指定目标内核(如exact _ predictions _ inextact _ constructions _ kernel)！

CGAL软件功能

计算几何算法库(CGAL)是一个C ++库，旨在提供对计算几何中高效可行算法的简单访问。

算术和代数

组合算法

几何核

凸包算法

多边形

细胞复合体和多面体

安排

三角测量

沃罗尼图

网格生成

形状重建

几何加工

空间搜索

几何优化

插入文字

支持图书馆

形象化

CGAL软件特色

CGAL包通常提供图形演示来演示包中的功能。在许多情况下，这个演示只是程序的高级版本，在开发的早期阶段，它被用作(图形)调试工具。在许多情况下，几何算法的输出比数字形式的输出更容易用图形来解释。所以应该使用CGAL强大的图形输出功能进行开发。

可用于调试包内部工作的程序(即用户可能无法访问的内容)

有趣和信息丰富的演示，突出功能，并介绍包中是否有错误。您可以在每个内部版本的demo和CGAL安装目录中找到其他demo/调试器程序。

鲁棒问题

几何设计和正确证明通常采用精确算法。计算不准确会导致算法的控制流出现错误决策甚至矛盾决策，所以很多实现都会崩溃，或者充其量只能对部分输入进行垃圾计算。对于某些应用，不良输入与所有可能的输入相比所占的比例很小，但对于其他应用，这一比例很大。

CGAL采用分层设计。某些组件的正确性取决于所用组件的正确性。组件的正确性指的是根据其(数学)规范的行为。简而言之，鲁棒性问题的根源在于硬件支持的默认算法不能真正满足算法要求，因为它不在实数上执行算法。

然而，由算法参数化(更准确地说，由数值类型参数化)的内核原语的一般实现假设插入的算法实际上表现为真实算法。通用代码不会也不应该(否则会降低“精确”数字类型的速度)处理任何潜在的不准确性。CGAL有许多“精确”的数字类型(完全由第三方提供)，其中“精确”意味着所有决策(比较)都是正确的，如果需要，数字的表示允许精确到任何精度。根据所需的计算，如果涉及理性计算，适当的精确数字类型可以是商数或gmpq。如果需要多项式的根，则通过使用达乐_realLEDACORE::Expr或CORE来提供解。

谓词和构式的作用。

CGAL支持将基本算术运算(即几何计算中的最低级别)封装为更高级别的单元(即几何实体的级别，即谓词和构造)。这里的谓词是广义的，即不仅原语返回布尔值，原语还返回枚举类型的值，如CGAL::Sign。因此，谓词计算的值不包含任何数字数据。基本构造可能涉及新计算的数值数据的新的原始几何对象，也就是说，它不是构造输入的一部分。这种基本构造的一个例子是计算两个给定点之间的直线段的中点。选择是一种特殊的结构。对于选择，构造对象中的所有数据已经是输入的一部分。一个例子是计算字典中两个给定点的较小点。

CGAL提供了几何图元的一般实现。这些假设是“精确的计算”。根据实际的数字输入数据，这种方法可能有效，也可能无效。CGAL还提供了[1]基元的特殊化，与任意精度整数或有理数等精确数值类型相比，这种特殊化(仍然相当通用)可以保证精确的谓词结果，并且效率更高。效率取决于使用快速浮点算法来过滤掉可用的浮点计算。区间算法主要用于这种滤波步骤。

CGAL使用说明

CGAL的配置变量摘要

大多数配置变量不是环境变量，而是ake变量。通过-D选项在命令行上提供它们，或者从的交互界面传递cmake-gui。除非另有说明，下面总结的所有变量都是ake变量。

1.1组件选择

以下布尔变量指示要配置和构建的CGAL组件。它们的值可以是开或关。

1.2编译器和链接器标志

下列变量指定编译器和链接器标志。每个变量包含编译器和链接器的命令行开关的空格分隔列表，它们的默认值由ake根据目标平台自动定义。

请记住，这些变量指定了一个标志列表，而不仅仅是一个标志。如果您为变量提供自己的定义，ake为该特定变量选择的标志列表将被完全覆盖。

对应于调试和发布版本的变量总是与特定版本类型的变量结合使用。

1.3附加编译器和链接器标志

以下变量可用于添加标志，而不会覆盖cmake定义的标志。

1.4杂项变量

请注意，默认的生成类型是调试，它仅用于调试，并将限制的性能。

1.5仅在构建程序时使用的变量(如演示或示例)。

1.6提供关于第三方库的变量

以下变量提供了CGAL使用的第三方库的可用性和位置信息。Ake会自动搜索依赖项，所以如果ake找不到什么，就需要指定这些变量。这由以NOTFOUND结尾的值表示。

因为第三方库是全系统的，所以下面列出的许多ake变量可以用作具有相似名称的环境变量。请记住，您必须提供其中一个，但不能两个都提供。

1.7升级库

大多数情况下，如果没有自动找到Boost，设置BOOST_ROOT变量就足够了。如果没有，您可以分别指定标题目录和库目录。如果在库目录中找不到特定的编译库，或者它的名称是非标准的，您也可以提供它的完整路径名。

默认情况下，当需要Boost二进制库时，将使用共享版本(如果存在)。如果要链接显式静态版本，可以将变量CGAL_Boost_USE_STATIC_LIBS设置为ON。

在Windows上，如果链接到Boost共享库，则必须确保。dll在运行时通过动态链接器找到文件。例如，可以通过添加将Boost的path添加到PATH环境变量中。dll。

1.8 P和MPFR图书馆

在Windows下，使用自动链接，所以只需要包含库的目录。您可以指定P | MPFR _图书馆_目录，而不是P | MPFR _图书馆。另一方面，在Linux下，需要实际的库文件名。因此，您可以指定P|MPFR_LIBRARIES。在任何情况下，都不需要两者都指定。

CGALGmp和Mfr都使用，因此都需要支持。如果其中任何一个不可用，Gmp和Mfr将被禁用。

在Linux下，也将搜索Gmpxx，您可以指定以下变量:

1.9 Qt5库

您必须将cmake或envinment变量Qt5_DIR设置为包含Qt5安装Qt 5config.cmake创建的文件的目录的路径。如果您使用的是开源版本，它应该是。/Qt-rywhere-open source-src-/qtbase/lib/cmake/Qt5

1.10莱达图书馆

当没有自动找到LEDA库时，它们以基本名称“达乐”和“ledaD”安装在系统上(分别用于发布版本和调试版本)，仅用LEDA_LIBRARY_DIRS变量表示库目录就足够了。如果不同的名称(例如，不同的名称)不起作用，您可以通过LEDA_LIBRARY_RELEASE和提供每个变体的完整路径名LEDA_LIBRARY_DEBUG。

如果LEDA不需要指定变量的定义和标志，那么就没有必要定义它们。

1.11 MPFI图书馆

CGAL提供基于此库的数值类型，但是CGAL库本身不依赖于Mfi。这意味着在编译使用上述数字类型的应用程序时，必须配置该库。

当Mpfi文件不在标准路径上时，必须使用环境变量来指定头文件和库文件的位置。

1.12塞尔维亚和RS3图书馆

如前所述，只有CGAL单变量代数核依赖于库Rs。因为代数内核不是作为CGAL库的一部分编译的，所以在安装过程中不会检测或配置该库。

Ake将尝试在标准头文件和库目录中找到Rs。如果没有自动检测到，则必须使用环境变量来指定头文件和库文件的位置。

需要Rsgmp4.2或更高版本和Mfi 1 . 3 . 4或更高版本。可能还需要定义与后一个库相关的变量。

Rs3有类似的变量。

1.13 NTL图书馆

当Ntl可用时，CGAL代数核中的一些多项式计算将被加速。因为代数内核不是作为CGAL库的一部分编译的，所以在安装过程中不会检测或配置该库。

Ake将尝试在标准头文件和库目录中找到Ntl。如果没有自动检测到，则必须使用环境变量来指定头文件和库文件的位置。

如何在ake中使用CGAL

本页将解释如何手动创建akeLists.txt文件来链接带有CGAL的自定义程序。

您可以使用脚本创建基本cgal__akeLists。

与CGAL链接

要链接CGAL库，请使用以下命令:

到其他CGAL库的链接类似。例如，使用CGAL_Core:

注意

CGAL目标定义了以下编译器标志:

-资金-数学和海湾合作委员会

/fp:stct /fp:除了-和MSVC

使用Qt5的最小示例

本节介绍了使用CGAL和Qt5实现某些图形用户界面功能的程序的最小示例。

akeLists.txt

CGAL主要设计目标

正确的

如果库组件按照其规范运行，则它是正确的。所以，从根本上讲，正确性是验证文件与实现是否一致的问题。在模块化程序中，一个模块的正确性取决于它自己的正确性和它所依赖的所有模块的正确性。显然，为了得到正确的结果，必须使用正确的算法和数据结构。

在可行性的意义上，准确性不应该与正确性混淆。计算近似解而不是精确解的算法没有错，只要它们的行为被清楚地记录下来，并且它们真的以指定的方式工作。此外，虽然在CGAL中我们希望提供一种处理降级的算法，但是只处理非降级情况的算法就其规格而言可能是正确的。

公司

与几何算法的实现特别相关的设计目标是鲁棒性。由于精度问题，几何算法的许多实现缺乏鲁棒性。关于CGAL中稳健问题的讨论，请参考“稳健问题”一章。

灵活的

潜在应用领域的不同需求要求库具有灵活性。可以识别四个灵活的子问题。

模块化。

明确地将CGAL构造成依赖关系尽可能少的模块，有助于用户学习和使用CGAL，因为这样更容易掌握整体结构，而且可以将重点缩小到那些实际感兴趣的模块。

适应能力强。

CGAL可以在具有几何类和算法的既定环境中使用，在这种情况下，模块可能需要在使用前进行调整。

可扩展。

CGAL不能满足所有的愿望。用户可能希望扩展库。将新的类和算法集成到CGAL中应该是可能的，实际上也是可取的。

打开

CGAL应该是开放的，以便与其他库共存，或者更好地与其他库和程序一起工作。在C ++标准中[4]

所有C ++平台的公共基础都是使用C ++标准库定义的。因此，遵循这个标准可以轻松自然地打开。标准之外还有重要的库，CGAL应该很容易适应。

使用方便

许多不同的品质可以帮助简化库的使用。哪个质量最重要取决于用户体验。这些品质就是上面提到的正确而稳健的问题。一般来说，重要的是图书馆变得有用之前的时间长度。另一个问题是必须学习和记忆的新概念和一般规则的例外。

易用性通常与灵活性相冲突，但在许多情况下可以找到解决方案。CGAL的灵活性不应分散初学者使用CGAL的注意力。

分布均匀

CGAL中设计的统一外观将有助于学习和记忆。一旦学会了，这个概念就应该应用到你想应用它的所有地方。一旦了解了特定类的函数名，就不应该为另一个类使用不同的名称。

CGAL是基于很多地方借鉴STL(标准模板库)或者C ++标准库其他部分的概念。一个例子是在CGAL中使用流和流操作符。另一个例子是在STL中使用容器类和算法。因此，这些概念应该统一使用。

在过去的几年里，CGAL开始使用boost库中的概念和思想，并提供了一个到boost库的接口。这些包括增强的图形库和增强的地图库。

和一个完整而最小的接口。

具有相同含义的目标是具有完整和最小接口的设计，例如，参见参考资料中的第18项。[9]。物体或模块的功能应齐全，但不应提供其他装饰功能。即使某个功能看似有助于一堂课的易用性，但从更全局的角度来看，可能会阻碍对课与课之间异同的理解，让学习和记忆变得更加困难。

功能丰富齐全。

我们的目标是收集有用和丰富的几何类、数据结构和算法。CGAL被认为是计算几何中算法研究的基础，因此需要一定的广度和深度。这一领域的标准技术应该出现在CGAL中。

完整性也与健壮性有关。

我们的目标是提供通用的解决方案，例如，不受一般工作假设的限制。CGAL中的算法应该能够处理特殊情况和退化。

当发现降级的处理效率较低时，除了处理所有降级的通用算法外，还应在库中提供更有效但不太通用的特殊变体。当然，有必要清楚地记录哪些降解被处理，哪些没有被处理。

效率

对于大多数几何算法，时间和空间复杂度的理论结果是已知的。此外，与最坏的情况相反，对实际投入效率的理论兴趣也在增长[13]。出于实际目的，有必要知道隐藏在标签中的常数因子，尤其是当有几个竞争算法时。o因此，如果没有最优解，就应该提供不同的实现方法，比如在进行时间和空间的权衡时，或者没有或者几乎没有简并时，就应该实现更有效的实现方法。