阿狗问道——算法几何

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

——华罗庚

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

相关文章

来自专栏量子位

“不正经”NIPS大会指北:嘻哈歌手、感人长队,以及最佳论文

夏乙 问耕 假装发自加州 量子位 出品 | 公众号 QbitAI ? 这几天,AI圈人士纷纷前往洛杉矶附近风景宜人的长滩。 他们在这里排长队、晒太阳、看大海、听...

3415
来自专栏量子位

2018谷歌学术影响因子发布:NIPS首次跃进Top 100,CVPR排名泛AI领域第一

刚刚,谷歌发布了2018年最新版学术指标(Google Scholar Metrics,GSM)榜单。通过综合衡量学术会议和期刊论文中已发表的论文,谷歌对学术出...

1530
来自专栏大数据挖掘DT机器学习

【趣味】数据挖掘(8)——K-平均聚类及蛋鸡悖论

本文从农村中学并迁选址问题出发,介绍了数据挖掘十大算法中位居第二的K-平均聚类,后又借用牛顿迭代原理,议论蛋鸡悖论。从过去的数据挖掘课程PPT取些素材,...

3556
来自专栏灯塔大数据

从国足说起,网络流算法远比你想的要好玩

? 这个问题的由来是想起来11月18日将会有国足世预赛的比赛,于是今天去看了看国足目前在小组中的积分。在积分榜中,我们可以看到与中国同组的马尔代夫和不丹都已经...

2435
来自专栏量子位

论PS的功力,英伟达的AI这次谁也不服

前一阵子,流传过这样一个段子:“甲方不要PS!让我们用Photoshop做!”足以说明开头的结论。

1002
来自专栏人工智能快报

深度学习的起源与先行者

在二十世纪五十年代就存在深度学习的概念了。麦肯锡全球研究院发文简要回顾了深度学习是如何从概念发展为现实的,而使之实现的关键人物又是谁。

692
来自专栏龙行天下CSIEM

科学瞎想系列之五十九 变频调速与节能

节能是当今的热门话题之一,所谓节能就是达到同样的目的和效果,所消耗的能量尽量减少。节能的技术不胜枚举,变频调速就是最常见的一种。我们先看看变频调速是怎么节能的。...

2705
来自专栏机器之心

KDD 2017获奖论文公布:数据挖掘领域的顶级研究与应用成果

机器之心报道 参与:蒋思源、李亚洲 数据挖掘领域的顶会 KDD 2017 目前正在火热进行中。昨日,机器之心报道了滴滴被 KDD 2017 接收的论文。今日...

32010
来自专栏机器之心

机器之心年度盘点:2017年人工智能领域度备受关注的科研成果

3689
来自专栏企鹅号快讯

理性的相亲方法!精品课:《决策树》

今天是我坚持的第两百一十一天!每天逼自己成长进步一点! 假如你是一个女孩子,你妈妈一直很为你的终身大事担心,今天又要给你介绍对象了。你随口一问:多大了?她说:2...

2069

扫码关注云+社区