2.1 介绍

CGAL 是一个用 C++ 描述的 , 包含三个主要部分的计算几何算法库 . 第一部分是核心 , 它包括基本的几何对象以及做用在这些对象上的各种操作 . 这些对象被实现成使用表现类参数化的独立的类 , 这样使得核心更具有灵活性和适应性 .

第二部分是一系列的基础几何数据结构和算法 . 它们被特征类参数化 . 而特征类定义了数据结构或者算法和它们使用的原生类型 (primitives) 见的接口 . 在很多情况下 CGAL 中的核心类可以作为这些数据结构或算法的特征类使用 .

第三部分是由一些支持设施比如为方便调试设计的迭代器 , 随机数生成器 ,I/O 支持以及一些可视化工具等等 . 这个部分主要介绍核心部分 . 核心由一些基础对象组成 , 比如点 , 向量 , 方向 , 直线 , 射线 , 线段 , 三角形 , 长方形和四面体 . 每个部分都有一些对这些对象进行操作的函数 . 一般有访问函数 ( 比如一个点的坐标 ), 测试点和这个对象的位置关系 , 得到对象的包围盒子的函数 , 长度 , 面积等等 . 核心中还包含一些基本操作 , 比如仿射变换 , 相交的检测与计算 , 距离计算 .

2.1.1 健壮性

几乎所有的论文中的几何算法正确性的证明都假定了精确的实数运算.这使得实现几何算法有一个根本问题 . 大部分的精确实数运算在实现过程中都是由不精确的浮点数运算所代替 . 这在大部分情况下都能有可接受的结果 . 但是即使是实现最简单的几何算法这样的简化都使得算法失效 . 由于不精确的运算造成的舍入误差可能导致判断不一致 , 使一些正确的输入数据产生错误的结果 . 解决这个问题的方法很多 . 其中一种是精确地计算 ( 精确到算法的所有判断都是精确的 ), 这种方法可行 , 但是相对浮点运算来说代价太大 .C.M.Hoffmann [Hof89a,Hof89b] 描述这在实现几何算法中出现的各种问题并且讨论了解决它们的办法 . 最近的一些观点出现在 [Sch00] 中 . 精确计算方法在 Yap 和 Dube[YD95][Yap97] 中有所介绍 .

在 CGAL 中你可以选择各种数据类型和算法 . 甚至可以同时使用多种运算类型而且很容易改变 , 例如测试的时候 . 所以你可以选择速度快而精度相对低的实现 , 也可以选择完全精确的实现 . 当然要付出时间和空间的代价 . 更多细节在数据类型以及支持库这些章节中 .

2.2 核心

我们学习的对象是 d 维欧几里得仿射空间 . 这里我们主要考虑 2 维和 3 维得情况 . 空间中的对象是有点集组成 . 表示点的一般方法是使用笛卡儿坐标 . 它假定了一个参照框架 ( 一个原点和 d 个正交轴 ). 这个框架中一个点是由一个 d 维的向量表示的 (c₀,c₁,...,c_d-1), 相应的线性空间中的向量也是如此 . 每个点都有唯一的笛卡儿坐标与之对应 . 另一种表示点的方法是齐次坐标 . 在这个框架中一个点是有一个 d+1(h0,h1...,hd) 维向量表示的 . 根据公式 ci=hi/hd, 对应的点的笛卡儿坐 ) 标 (c₀,c₁,...,c_d-1) 可以计算出来 . 注意齐次坐标的点的表示是不唯一的 . 当 λ ≠ 0 时 , 向量 (h₀,h₁,…h_d) 和向量 ( λ h_0, λ h₁ …, λ h_d) 表示同一个点 . 如果一个点的笛卡儿坐标是 (c0,c1,…,cd-1), 它可以表示成 (c0,c1,…,cd-1,1) 这个齐次坐标 . 齐次坐标系可实际上可以在一个更一般的空间的中表示对象 . 这个空间叫射影空间 . 在 CGAL 中我们不会进行射影几何的计算 . 我们使用齐次坐标是为了避免除法运算 , 而增加的这个坐标是作为公共分母 .