阿狗问道——算法几何

数与形本相倚依，焉能分作两边飞；数无形时少直觉，形少数时难入微。

——华罗庚

几何是基于形的数学。相比于代数的抽象，几何以其触手可及和举目即视的“形”揭开艰深数学的神秘面纱。在超越千年数学历史的涤荡中，平面几何、立体几何、非欧几何、黎曼几何、微分几何、射影几何、计算几何等诸多具体的几何相关学科纷至沓来，不断拓宽人们关于“形”的探索途径。计算几何又是这几何家族中特别的一位：她年富力强，自1969年作为模式识别的代用词被提出开始，满打满算也就四十来岁；她行为具体，总是将复杂的几何形体化为计算机所能接受的具体语言；她理实交融，让几乎所有的理论都有匹配的实用算法；她兴盛发达，短短几十年就延展至计算机图形学、计算机视觉、人工智能等多个新兴领域。

要想了解这门与算法相伴共生的几何学科，不妨先从她的诸多算法窥其一斑。假设今天我要约好友去参观一个著名的博物馆，又假设时光倒流，我所在的是九十年代人们还在使用公用电话的校园。我首先需要给好友打一个电话，怎样才能找到离自己最近的那部公用电话机呢？如果可以根据电话机的分布将校园划分为一个个区域，每个区域都对应一部最近的公用电话，那么无论我身在何处，这个问题都能立即给出答案。试问，这些区域是什么形状，又如何划分呢？这就是著名的Voronoi图（Voronoi diagram）计算问题。常常伴随该问题出现的是用于三角网格化的Delaunay三角剖分（Delaunay triangulation）。

图1:Voronoi图（左）与Delaunay三角剖分（右）

现在，我要去博物馆与朋友集合。假设我手中有两张地图，一张描述了城市中所有的建筑物，另一张则绘制了城市的所有道路，我需要同时参考两张图的信息找到要去的博物馆。这就是著名的地图叠合问题（geographic overlay），它涉及到如何计算某张地图中的建筑在另一张地图中的定位，以及一些几何求交问题。接下来，我需要选择一条最短的路径到博物馆，且途中要避开建筑物和其他障碍。对于人来说这也许并不难，但要让机器人来完成这个任务，就涉及到路径和速度的规划，即运动规划（motion planning）问题。

图2：地图叠合（左）与运动规划（右）

一番辛苦之后，终于可以在博物馆里畅游了。馆中尽是珍品，然而却无人看守，摄像头的安装是必要的。然而，太多摄像头不仅会破坏博物馆整体的视觉美感，也会给游客带来心理上的不适。那么，如何安装最少的摄像头，使得每件珍品都至少被一个摄像头监管到呢？这就是所谓的画廊看守问题（art gallery problem）。

图3：画廊看守（左）与光线跟踪（右）

如果这家博物馆相当大，展区安排层次复杂，如何可以走最短的路程，将所有展品全都欣赏到，而尽量不重复呢？这是著名的邮递员问题（Chinese postman problem）。假设博物馆允许拍照，而我希望将某件展品嵌入到计算机的其他环境场景中去，那就需要根据展品的三维模型数据做渲染，而渲染就要用到光线跟踪（ray tracing）算法。倘若我根本就没有该展品的三维数据，那又该怎么办呢？我可以从不同角度拍几张展品的照片，通过这些照片的二维图像尽可能地恢复其三维模型，这是三维重建（3D reconstruction）。

故事可以继续讲下去，越来越多的计算几何问题将跃然纸上，连成一串闪亮的珍珠。在前面的讲述中，Voronoi图的计算、地图叠合、画廊看守、光线跟踪算法等，都是针对计算几何早期的经典问题，而邮递员问题最早出现在图论中，运动规划更多地被用于机器人与数控机床，三维场景重建则属于计算机图形学的热门话题。因此，计算几何作为研究几何与算法的学科，与很多其他学科之间有着千丝万缕的联系，人们很难为其划定泾渭分明的边界。

在前面的故事场景中，提到的基本是基于离散数据和模型的算法，而计算几何绝不仅仅是离散问题和算法的集合，它也拥有一脉与微分几何及逼近论息息相关的血液。在这支血液中，关于连续曲线曲面的理论研究颇为丰富，也衍生出了许多著名算法，它们形成了起源于1974年的计算机辅助几何设计（CAGD）。

计算机辅助几何设计集中研究计算机图像系统环境中曲面的表示和逼近。上世纪六、七十年代，汽车、轮船制造业与计算机图形系统初遇，通过简单鼠标操作拖动控制网格即可调整设计光滑曲线的Bézier曲线应运而生，它的孪生兄弟de Casteljau算法可将控制网格在不断细分下达到同一条光滑曲线。这对孪生兄弟几乎同期分别诞生于法国雷诺汽车公司与雪铁龙汽车公司，由此翻开了计算机辅助几何设计这一全新领域的扉页。

不仅利于直观设计，Bézier曲线比普通参数曲线在数值计算上更为稳定。然而，当设计师想局部调整Bézier曲线的形状时，一个控制点的拖动会带动整条曲线的形变。样条（spline）的产生解决了这一难题，在设计中可以做到“牵一发而不动全身”。B-样条和NURBS样条自诞生之日起就活跃在CAD/CAM等工业设计的舞台上。debor算法之于B-样条的角色，类似于de Casteljau算法之于Bézier曲线，可以直接通过对控制网格细分而实现曲线上点的绘制，从而取代复杂的公式计算。曲面造型方面，还有Coons曲面和Catmull-Clark细分曲面等。这些CAGD领域早期的概念和算法，至今仍作为最基本的元素，深深植根在CAD/CAM和计算机图形学等相关学科的诸多具体问题之中。

图4：Bézier曲线及de Casteljau算法（左）与B-样条曲线（右）

图5：Coons曲面（左）与Catmull-Clark细分曲面（右）

算法相关的几何，将图论、微分几何、逼近论等古典学科带到了现代计算机科学飞速发展的舞台前，它们随着时代变换了面孔，却依然保存有古老数学的精神实质。在计算机辅助几何设计出现之后，计算机图形学、计算机视觉、机器人学、人工智能等，越来越多的新兴学科在人类智慧的演绎下萌芽、生长、成熟，并带来新一轮学科的诞生。计算机科学的步伐不会停止，算法相关的故事就永远讲不完。与古典数学的优雅从容相比，现代计算机科学驱动下的算法几何一路风尘仆仆。人们发现，人们思索，人们校正，将一路上的收获聚成计算机与数学交融的风景线。

（文中图片来自Mark de Berg et al. Computational Geometry: Algorithms and Applications.第三版、Wikipedia.com及百度搜索）

作者：贾晓红

单位：中国科学院数学与系统科学研究院