阿狗问道——算法几何

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

——华罗庚

几何是基于形的数学。相比于代数的抽象,几何以其触手可及和举目即视的“形”揭开艰深数学的神秘面纱。在超越千年数学历史的涤荡中,平面几何、立体几何、非欧几何、黎曼几何、微分几何、射影几何、计算几何等诸多具体的几何相关学科纷至沓来,不断拓宽人们关于“形”的探索途径。计算几何又是这几何家族中特别的一位:她年富力强,自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及百度搜索)

作者:贾晓红

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

本文来自企鹅号 - 全球大搜罗媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能快报

深度学习帮助科学家开展实时引力波探测

“ 美国国家超级计算应用中心的科学家正在利用深度学习对引力波进行实时探测。 ” 位于美国伊利诺伊大学厄巴纳-尚佩恩分校(University of Illi...

3488
来自专栏大数据文摘

视觉研究的前世今生(上)

1916
来自专栏机器之心

专栏 | 上海纽约大学张峥教授:2017年影响力论文推荐

这篇文章特意选择在 NIPS2017 会议期间发表,但与会者并没有特别大的反应。相反,在研讨会上这篇文章引起了关于通用智能的一场针锋相对的讨论。

872
来自专栏ACM算法日常

谁是史上最强将领?算法证明:拿破仑

编者按:本文编译自towardsdatascience原标题为Napoleon was the Best General Ever, and t...

851
来自专栏理论坞

日韩系风格卡牌示范教程《千叶真琴》

在时下流行的卡牌插画中,有一种卡牌凭借着时尚、清新、靓丽的画面风格倍受年轻人的喜爱,这就是日韩系风格卡牌。它们的代表就是Applibot公司旗下的《不良道》。游...

752
来自专栏思影科技

NEJM:Waving Hello to Noninvasive Deep-Brain Stimulation

近日多伦多大学Andres M. Lozano等人在新英格兰医学杂志发文,介绍了无创深部脑刺激技术。通过两个频率差异较小的电场信号刺激,激活深部大脑细胞,同时避...

3405
来自专栏新智元

【蒲慕明院士】人工智能可借鉴的 5 大自然神经网络特性(35PPT)

【新智元导读】2016中国人工智能大会(CCAI 2016)日前在京召开。中国科学院外籍院士、中国科学院神经学研究所所长蒲慕明27日发表演讲《脑科学能为人工智能...

3614
来自专栏量子位

最擅长玩《毁灭战士》的AI开源了 | 来自CMU的论文&代码

李林 发自 凹非寺 量子位 出品 | 公众号 QbitAI ? 最擅长玩《毁灭战士(DOOM)》的那个AI,最近开源了。 它叫Arnold,来自卡耐基梅隆大学“...

3345
来自专栏CSDN技术头条

大数据专家教你用数据模型来找女朋友

男生和女生分别是来自不同星球的科学事实已经众所周知的了.男生们总是认为,女生们都是迷一样的生物,他们的情感状态浮动似乎是以秒单位在变化的,难以理解,更勿论预测了...

2169
来自专栏数据科学与人工智能

【数据科学】数据科学家教你用数据模型来恋爱。

男生和女生分别是来自不同星球的科学事实已经众所周知的了.男生们总是认为,女生们都是迷一样的生物,他们的情感状态浮动似乎是以秒单位在变化的,难以理解,更勿论预测了...

1967

扫码关注云+社区