关于计算机系开设“计算几何”课程的建议

吴壮志

摘要:本文主要讨论了在大学计算机系开设“计算几何”课程的可行性和必要性,对“计算几何”这门学科进行了概略的介绍,给出了课程大纲的具体建议,并对推荐的教材和参考书进行了详细分析。

关键词:计算几何;几何算法;CGAL

中图分类号:G642文献标识码:B

1为什么要开设“计算几何”课程

1.1学科简介

20世纪70年代末,以M.I.Shamos 1978年的博士论文为标志,“计算几何”(Computational Geometry)从算法分析和设计中孕育而生。它是一门研究几何物体数据结构和算法的学科,目的是设计渐进的精确的几何算法来解决几何问题。

“计算几何”作为一个被广泛认同的学科,拥有自己的学术刊物和学术会议,并形成了一个由众多研究人员组成的学术团体。它作为一个研究学科之所以取得成功,一方面是因为所研究问题和得到的解的优美性,另一方面是由于其应用领域的广泛性。图象处理、计算机图形学、CAD/CAM、地理信息系统、机器人等都是其应用领域。在这些领域中,研究人员会碰到大量与几何有关的算法问题,计算几何则提供了一系列解决此类问题的算法、数据结构和几何范式(paradigms)。

一般说来,判断一个学科是否成熟的标志是,这个学科是否有公认的标准教科书,是否有自己的学术刊物和学术会议。对计算几何来说,目前已存在多本经典教材,多个与其相关的学术刊物和学术会议,已经是一个十分成熟的学科。

与计算几何有关的学术会议有:

(1)ACM Symposium On Computational Geometry (SoCG);

(2)Canadian Conference on Computational Geometry

(CCCS);

(3)International Workshop on Computational Geometry and Applications(CGA)。

相关学术刊物有:

(1)Computational Geometry: Theory and Applications;

(2)Discrete & Computational Geometry;

(3)International Journal on Computational Geometry and Application。

相关教材有:

(1)Mark de Berg,M. van Kreveld, M. Overmars, O. Schwarzkopf. Computational geometry: algorithms and applications (Second Edition). Springer-Verlag, 2000.

(Mark de Berg,M. van Kreveld, M. Overmars, O. Schwarzkopf,著. 邓俊辉,译. 计算几何:算法与应用(第2版),清华大学出版社,2005.)

(2)Joseph O'Rourke. Computational geometry in C(Second Edition). Cambridge University Press, 1998.

(3)F. P.Preparata, M. I. Shamos. Computational Geometry: An Introduction, Spinger-Verlag, New York, 2000.

([美]F.P.普雷帕拉塔,M.I.沙莫斯,著. 庄心谷,译.“计算几何导论”,科学出版社,1998.)

(4) 周培德,著. 计算几何:算法分析与设计(第2版),清华大学出版社,2004.

1.2国内外大学“计算几何”课程的开课状况

“计算几何”从“算法分析和设计”中孕育而生,主要研究与几何问题有关的算法,它的比较典型的应用领域包括计算机图形学、图像处理、地理信息系统、机器人学和CAD/CAM等。在上述领域中,研究人员会碰到大量与几何有关的算法问题,计算几何则提供了一系列解决此类问题的算法、数据结构和几何范式。学生掌握了这些知识和处理问题方法,对将来开展这些领域工作将有很大的帮助。因此,在计算机专业开设“计算几何”这门课程具有十分重要的意义,尤其是对即将从事专业研究的研究生。

目前国际知名大学(如Brown University,Carnegie Mellon University,Duke University,University of Maryland,University of Illinois,香港科技大学等)的计算机系早已将“计算几何”作为硕士生或高年级本科生的专业基础课程。

比较起来,国内对计算几何的研究起步较晚,研究人员少,开课大学少(只有清华大学、北京航空航天大学等有限的几所大学开设此课程),这与计算几何学科所处的地位十分不称。目前已有许多人认识到“计算几何”学科的重要性,相信在不久的将来这种局面一定会改变。

值得注意的是,由于历史的原因,还有一门在国外被称为“计算机辅助几何设计”(Computer Aided Geometric Design,简称CAGD)的学科,国内也称为计算几何,专门研究几何图形信息(曲面和三维实体)的计算机表示、分析、修改和综合,与CAD/CAM关系十分密切,一般在机械系和数学系开设。

1.3关于CGAL

计算几何近年来最大的发展是由欧洲和以色列的多个科研院所合作开发的计算几何算法库(Computational Geometry Algorithms Library,简称CGAL)。CGAL已经开源发布多年,并取得巨大成功。作为一套开源、内容全面、实现稳定的计算几何算法库,CGAL的出现正在影响并将改变计算几何的教学和学习方法,具体体现在如下三个方面:(1)CGAL作为计算几何的准标准实现,使大家有了一个通用的教学和学习交流平台;(2)以前只能在理论上讨论的算法,现在可以直接观察算法的动态运行过程和结果;(3)进一步可以通过阅读算法实现源代码来学习算法。

2课程大纲建议

2.1课程描述

课程名称:计算几何

课程类型:计算机系本科高年级学生和研究生选修课

学时学分:36学时,2学分

先修要求:计算引论,数据结构,程序设计,高等数学,线性代数

2.2基本目的

设置本课程的目的就在于让学生掌握必要的计算几何概念、几何问题的典型算法、数据结构和几何范式,熟悉计算几何解决的经典问题,了解计算几何的应用领域。

2.3课程内容和课时安排

“计算几何”包括的内容十分丰富,本课程想要涵盖所有的内容是不可能的。本课程选材主要从算法和应用的角度出发,精心挑选计算几何中比较有代表性以及实用性强的内容进行讲授。推荐内容和课时如下。

(1) 计算几何概述(2课时)

介绍计算几何的简单历史,相关基础知识,主要研究内容,当前的研究动态。

(2)CGAL介绍(2课时)

介绍与CGAL有关的C++知识(template,STL等),CGAL的基本组成和结构,CGAL的编译、运行和调试环境等。

(3) 线段求交(Line Segment intersection) (2课时)

讲授求解“给定一个线段的集合,求出线段的所有交点”的问题的扫描线算法(Plane Sweep Algorithm)。此问题有广泛的应用背景,例如GIS中的地图叠合计算,计算机图形学中隐藏面消除的物空间算法等。

(4) 简单多边形(Simple Polygons) (2课时)

结合经典的画廊问题(Art-Ggllery Problem)讲授简单多边形的三角化算法。

(5) 凸包(Convex Hulls) (2课时)

讲授点集的凸包算法。凸包问题是计算几何中研究最早的一个问题,是计算几何中最基础的结构,点的三角化等问题都可以转化为凸包问题。

(6) 点定位问题(Point Location) (2课时)

讲授点的定位算法。点的定位问题是一类最基本的查询问题,应用十分广泛,例如地图上的鼠标位置定位问题。

(7) 范围查找(Range Searching) (2课时)

讲授范围查找算法。范围查找问题是点定位问题的对偶问题,范围查找问题的定义如下:指定d维空间的一个域D(称为查询域),范围查找时报告点集S包含在D中的子集S,或者计算点集S位于D内的元素个数。数据库查询问题即为一个典型的范围查找问题。

(8)Voronoi图(Voronoi Diagram) (2课时)

讲授点集的Voronoi图构造算法。Voronoi图是计算几何的一种基础性的结构,在许多应用中扮演了关键性的角色,例如邮局问题(post office problem)。

(9)Delaunay三角化(Delaunay Triangulation)(2课时)

讲授点集的Delaunay三角化构造算法。Delaunay三角化是Voronoi图的对偶图,也是计算几何的一种基础性的结构,应用及其广泛。

(10) 线性规划(linear Programming) (2课时)

讲授线性规划方法及其应用。线性规划为解决多类问题的一种有名的算法技术,许多几何问题能够表述为变量较少的线性规划问题,例如最小半径球问题(给定空间的一个点集,计算包含所有点的最小半径球)。

(11) 排列(Arrangement) (2课时)

讲授排列及其应用。一个线段和多边形的集合对平面的划分,称为一个排列(an arrangement)。排列可以用来解决多类问题,因此排列的算法和复杂性问题十分重要。机器人的路径规划问题可以表述为排列问题。

(12) 路径规划(Motion Planning) (2课时)

结合机器人的最短路径问题讲授路径规划算法。

(13) 几何数据结构Geometric Data Structures) (2课时)

讲授DCEL(Doubly-Connected Edge List),Quad-tree, K-d tree, Interval Trees, Priority Search Trees, Segment Trees等数据结构。

(14) 几何算法设计范式(Geometric Algorithm Paradigms) (2课时)

讲授分治法(Divide and Conquer Algorithm)、扫描法(Sweep Algorithm)、几何变换法(Geometric Transformation Algorithm)、随机增量法(Randomized Incremental Algorithm)等。

(15) 学生上机(8课时)

学生上机时间可以穿插到上述内容中间。

3教材和参考书推荐

《计算几何导论》是F. P.Preparata和M. I. Shamos 80年代初在M. I. Shamos的博士论文的基础上写成的专著,是计算几何领域的第一本标准教材,虽然其内容已经多年没有更新,但仍然为公认的计算几何参考书。科学出版社于1998年将其翻译为中本出版,应该说具有独到的眼见。

Joseph O'Rourke的《Computational geometry in C》也是一本比较公认的好教材,其内容比较经典,特别注重实践环节,所有算法都给出了C语言实现。

Mark de Berg, M. van Kreveld, M. Overmars和O.

Schwarzkopf著的《计算几何:算法与应用》(第2版)是目前公认的计算几何领域的经典教材。该教材准确地讲述了计算几何的基本概念,注重实践环节,每章都设有“注释及评论”和“习题”,扩大读者视野、启迪读者思维,及时反映了该学科领域的发展动向。国际知名大学开设的“计算几何”课程一般都会指定此书作为教材。该书已由清华大学邓俊辉副教授翻译为中文经清华大学出版社出版。

周培德教授著的《计算几何:算法分析与设计》是国内出版的第一本中文版计算几何专著,是一本较好的计算几何参考书。作者周培德教授多年来一直从事计算几何算法研究,是多部教材和专著的作者。

上述几本教材由于多种原因也存在一定的局限性。《计算几何导论》于1985年写成,虽然经典,但没有反映近20年来计算几何的最新成果。《Computational geometry in C》虽然注重实现,但是用C实现的,没有使用CGAL,这会加重学习负担。《计算几何:算法与应用》和《计算几何:算法分析与设计》的第1版成书在2000年以前,第2版除了对旧版进行勘误、增加新的内容外,编撰思路和书的结构等基本没有改变。由于当时CGAL还没有流行,使得以上教材不可能十分注算法实现。

由于计算几何领域近年来发展显著(如CGAL的出现),新的算法和应用领域不断出现,计算几何领域仅有上述描述的几部教材还远不能满足实际的需求。因此,如果能够提供新的借鉴已有教材优点、反映计算几何最新的研究成果、强调实现的教材,将会很有吸引力。与其他计算机学科动辄几十部甚至上百部教材相比,确实需要有关方面的研究人员多出几部精品教材,满足各类读者的需求,希望国内学者将来能写出有影响的教材来。

4结论

计算几何已经是一个成熟的学科,主要研究与几何问题有关的算法,典型的应用领域包括计算机图形学、图像处理、地理信息系统(GIS)、机器人学和CAD/CAM等。国外许多知名大学早已将计算几何作为硕士生或高年级本科生的专业基础课程。鉴于计算几何学科的基础性和应用的广泛性,建议国内的计算机系开设此课程。

参考文献:

[1]David Eppstein. Geometry in Action: Computational geometry conferences and workshops[EB/OL]. http://www.ics.uci. edu/-eppstein/gina/conf.html.

[2]Mark de Berg,M. van Kreveld, M. Overmars, O. Schwarzkopf. 计算几何:算法与应用[M]. 邓俊辉,译. 2版. 北京:清华大学出版社,2005.

[3]Joseph ORourke. Computational geometry in C(Second Edition)[M]. Cambridge:Cambridge University Press, 1998.

[4][美]F.P.普雷帕拉塔,M.I.沙莫斯. 计算几何导论[M]. 庄心谷,译. 北京:科学出版社,1998.

[5] 周培德. 计算几何:算法分析与设计[M]. 2版. 北京:清华大学出版社,2004.