關(guān)于計(jì)算機(jī)系開(kāi)設(shè)“計(jì)算幾何”課程的建議

吳壯志

摘要:本文主要討論了在大學(xué)計(jì)算機(jī)系開(kāi)設(shè)“計(jì)算幾何”課程的可行性和必要性,對(duì)“計(jì)算幾何”這門(mén)學(xué)科進(jìn)行了概略的介紹,給出了課程大綱的具體建議,并對(duì)推薦的教材和參考書(shū)進(jìn)行了詳細(xì)分析。

關(guān)鍵詞:計(jì)算幾何;幾何算法;CGAL

中圖分類(lèi)號(hào):G642文獻(xiàn)標(biāo)識(shí)碼:B

1為什么要開(kāi)設(shè)“計(jì)算幾何”課程

1.1學(xué)科簡(jiǎn)介

20世紀(jì)70年代末,以M.I.Shamos 1978年的博士論文為標(biāo)志,“計(jì)算幾何”(Computational Geometry)從算法分析和設(shè)計(jì)中孕育而生。它是一門(mén)研究幾何物體數(shù)據(jù)結(jié)構(gòu)和算法的學(xué)科,目的是設(shè)計(jì)漸進(jìn)的精確的幾何算法來(lái)解決幾何問(wèn)題。

“計(jì)算幾何”作為一個(gè)被廣泛認(rèn)同的學(xué)科,擁有自己的學(xué)術(shù)刊物和學(xué)術(shù)會(huì)議,并形成了一個(gè)由眾多研究人員組成的學(xué)術(shù)團(tuán)體。它作為一個(gè)研究學(xué)科之所以取得成功,一方面是因?yàn)樗芯繂?wèn)題和得到的解的優(yōu)美性,另一方面是由于其應(yīng)用領(lǐng)域的廣泛性。圖象處理、計(jì)算機(jī)圖形學(xué)、CAD/CAM、地理信息系統(tǒng)、機(jī)器人等都是其應(yīng)用領(lǐng)域。在這些領(lǐng)域中,研究人員會(huì)碰到大量與幾何有關(guān)的算法問(wèn)題,計(jì)算幾何則提供了一系列解決此類(lèi)問(wèn)題的算法、數(shù)據(jù)結(jié)構(gòu)和幾何范式(paradigms)。

一般說(shuō)來(lái),判斷一個(gè)學(xué)科是否成熟的標(biāo)志是,這個(gè)學(xué)科是否有公認(rèn)的標(biāo)準(zhǔn)教科書(shū),是否有自己的學(xué)術(shù)刊物和學(xué)術(shù)會(huì)議。對(duì)計(jì)算幾何來(lái)說(shuō),目前已存在多本經(jīng)典教材,多個(gè)與其相關(guān)的學(xué)術(shù)刊物和學(xué)術(shù)會(huì)議,已經(jīng)是一個(gè)十分成熟的學(xué)科。

與計(jì)算幾何有關(guān)的學(xué)術(shù)會(huì)議有:

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

(2)Canadian Conference on Computational Geometry

(CCCS);

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

相關(guān)學(xué)術(shù)刊物有:

(1)Computational Geometry: Theory and Applications;

(2)Discrete & Computational Geometry;

(3)International Journal on Computational Geometry and Application。

相關(guān)教材有:

(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,著. 鄧俊輝,譯. 計(jì)算幾何:算法與應(yīng)用(第2版),清華大學(xué)出版社,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.沙莫斯,著. 莊心谷,譯.“計(jì)算幾何導(dǎo)論”,科學(xué)出版社,1998.)

(4) 周培德,著. 計(jì)算幾何:算法分析與設(shè)計(jì)(第2版),清華大學(xué)出版社,2004.

1.2國(guó)內(nèi)外大學(xué)“計(jì)算幾何”課程的開(kāi)課狀況

“計(jì)算幾何”從“算法分析和設(shè)計(jì)”中孕育而生,主要研究與幾何問(wèn)題有關(guān)的算法,它的比較典型的應(yīng)用領(lǐng)域包括計(jì)算機(jī)圖形學(xué)、圖像處理、地理信息系統(tǒng)、機(jī)器人學(xué)和CAD/CAM等。在上述領(lǐng)域中,研究人員會(huì)碰到大量與幾何有關(guān)的算法問(wèn)題,計(jì)算幾何則提供了一系列解決此類(lèi)問(wèn)題的算法、數(shù)據(jù)結(jié)構(gòu)和幾何范式。學(xué)生掌握了這些知識(shí)和處理問(wèn)題方法,對(duì)將來(lái)開(kāi)展這些領(lǐng)域工作將有很大的幫助。因此,在計(jì)算機(jī)專(zhuān)業(yè)開(kāi)設(shè)“計(jì)算幾何”這門(mén)課程具有十分重要的意義,尤其是對(duì)即將從事專(zhuān)業(yè)研究的研究生。

目前國(guó)際知名大學(xué)(如Brown University,Carnegie Mellon University,Duke University,University of Maryland,University of Illinois,香港科技大學(xué)等)的計(jì)算機(jī)系早已將“計(jì)算幾何”作為碩士生或高年級(jí)本科生的專(zhuān)業(yè)基礎(chǔ)課程。

比較起來(lái),國(guó)內(nèi)對(duì)計(jì)算幾何的研究起步較晚,研究人員少,開(kāi)課大學(xué)少(只有清華大學(xué)、北京航空航天大學(xué)等有限的幾所大學(xué)開(kāi)設(shè)此課程),這與計(jì)算幾何學(xué)科所處的地位十分不稱(chēng)。目前已有許多人認(rèn)識(shí)到“計(jì)算幾何”學(xué)科的重要性,相信在不久的將來(lái)這種局面一定會(huì)改變。

值得注意的是,由于歷史的原因,還有一門(mén)在國(guó)外被稱(chēng)為“計(jì)算機(jī)輔助幾何設(shè)計(jì)”(Computer Aided Geometric Design,簡(jiǎn)稱(chēng)CAGD)的學(xué)科,國(guó)內(nèi)也稱(chēng)為計(jì)算幾何,專(zhuān)門(mén)研究幾何圖形信息(曲面和三維實(shí)體)的計(jì)算機(jī)表示、分析、修改和綜合,與CAD/CAM關(guān)系十分密切,一般在機(jī)械系和數(shù)學(xué)系開(kāi)設(shè)。

1.3關(guān)于CGAL

計(jì)算幾何近年來(lái)最大的發(fā)展是由歐洲和以色列的多個(gè)科研院所合作開(kāi)發(fā)的計(jì)算幾何算法庫(kù)(Computational Geometry Algorithms Library,簡(jiǎn)稱(chēng)CGAL)。CGAL已經(jīng)開(kāi)源發(fā)布多年,并取得巨大成功。作為一套開(kāi)源、內(nèi)容全面、實(shí)現(xiàn)穩(wěn)定的計(jì)算幾何算法庫(kù),CGAL的出現(xiàn)正在影響并將改變計(jì)算幾何的教學(xué)和學(xué)習(xí)方法,具體體現(xiàn)在如下三個(gè)方面:(1)CGAL作為計(jì)算幾何的準(zhǔn)標(biāo)準(zhǔn)實(shí)現(xiàn),使大家有了一個(gè)通用的教學(xué)和學(xué)習(xí)交流平臺(tái);(2)以前只能在理論上討論的算法,現(xiàn)在可以直接觀察算法的動(dòng)態(tài)運(yùn)行過(guò)程和結(jié)果;(3)進(jìn)一步可以通過(guò)閱讀算法實(shí)現(xiàn)源代碼來(lái)學(xué)習(xí)算法。

2課程大綱建議

2.1課程描述

課程名稱(chēng):計(jì)算幾何

課程類(lèi)型:計(jì)算機(jī)系本科高年級(jí)學(xué)生和研究生選修課

學(xué)時(shí)學(xué)分:36學(xué)時(shí),2學(xué)分

先修要求:計(jì)算引論,數(shù)據(jù)結(jié)構(gòu),程序設(shè)計(jì),高等數(shù)學(xué),線性代數(shù)

2.2基本目的

設(shè)置本課程的目的就在于讓學(xué)生掌握必要的計(jì)算幾何概念、幾何問(wèn)題的典型算法、數(shù)據(jù)結(jié)構(gòu)和幾何范式,熟悉計(jì)算幾何解決的經(jīng)典問(wèn)題,了解計(jì)算幾何的應(yīng)用領(lǐng)域。

2.3課程內(nèi)容和課時(shí)安排

“計(jì)算幾何”包括的內(nèi)容十分豐富,本課程想要涵蓋所有的內(nèi)容是不可能的。本課程選材主要從算法和應(yīng)用的角度出發(fā),精心挑選計(jì)算幾何中比較有代表性以及實(shí)用性強(qiáng)的內(nèi)容進(jìn)行講授。推薦內(nèi)容和課時(shí)如下。

(1) 計(jì)算幾何概述(2課時(shí))

介紹計(jì)算幾何的簡(jiǎn)單歷史,相關(guān)基礎(chǔ)知識(shí),主要研究?jī)?nèi)容,當(dāng)前的研究動(dòng)態(tài)。

(2)CGAL介紹(2課時(shí))

介紹與CGAL有關(guān)的C++知識(shí)(template,STL等),CGAL的基本組成和結(jié)構(gòu),CGAL的編譯、運(yùn)行和調(diào)試環(huán)境等。

(3) 線段求交(Line Segment intersection) (2課時(shí))

講授求解“給定一個(gè)線段的集合,求出線段的所有交點(diǎn)”的問(wèn)題的掃描線算法(Plane Sweep Algorithm)。此問(wèn)題有廣泛的應(yīng)用背景,例如GIS中的地圖疊合計(jì)算,計(jì)算機(jī)圖形學(xué)中隱藏面消除的物空間算法等。

(4) 簡(jiǎn)單多邊形(Simple Polygons) (2課時(shí))

結(jié)合經(jīng)典的畫(huà)廊問(wèn)題(Art-Ggllery Problem)講授簡(jiǎn)單多邊形的三角化算法。

(5) 凸包(Convex Hulls) (2課時(shí))

講授點(diǎn)集的凸包算法。凸包問(wèn)題是計(jì)算幾何中研究最早的一個(gè)問(wèn)題,是計(jì)算幾何中最基礎(chǔ)的結(jié)構(gòu),點(diǎn)的三角化等問(wèn)題都可以轉(zhuǎn)化為凸包問(wèn)題。

(6) 點(diǎn)定位問(wèn)題(Point Location) (2課時(shí))

講授點(diǎn)的定位算法。點(diǎn)的定位問(wèn)題是一類(lèi)最基本的查詢(xún)問(wèn)題,應(yīng)用十分廣泛,例如地圖上的鼠標(biāo)位置定位問(wèn)題。

(7) 范圍查找(Range Searching) (2課時(shí))

講授范圍查找算法。范圍查找問(wèn)題是點(diǎn)定位問(wèn)題的對(duì)偶問(wèn)題,范圍查找問(wèn)題的定義如下:指定d維空間的一個(gè)域D(稱(chēng)為查詢(xún)域),范圍查找時(shí)報(bào)告點(diǎn)集S包含在D中的子集S,或者計(jì)算點(diǎn)集S位于D內(nèi)的元素個(gè)數(shù)。數(shù)據(jù)庫(kù)查詢(xún)問(wèn)題即為一個(gè)典型的范圍查找問(wèn)題。

(8)Voronoi圖(Voronoi Diagram) (2課時(shí))

講授點(diǎn)集的Voronoi圖構(gòu)造算法。Voronoi圖是計(jì)算幾何的一種基礎(chǔ)性的結(jié)構(gòu),在許多應(yīng)用中扮演了關(guān)鍵性的角色,例如郵局問(wèn)題(post office problem)。

(9)Delaunay三角化(Delaunay Triangulation)(2課時(shí))

講授點(diǎn)集的Delaunay三角化構(gòu)造算法。Delaunay三角化是Voronoi圖的對(duì)偶圖,也是計(jì)算幾何的一種基礎(chǔ)性的結(jié)構(gòu),應(yīng)用及其廣泛。

(10) 線性規(guī)劃(linear Programming) (2課時(shí))

講授線性規(guī)劃方法及其應(yīng)用。線性規(guī)劃為解決多類(lèi)問(wèn)題的一種有名的算法技術(shù),許多幾何問(wèn)題能夠表述為變量較少的線性規(guī)劃問(wèn)題,例如最小半徑球問(wèn)題(給定空間的一個(gè)點(diǎn)集,計(jì)算包含所有點(diǎn)的最小半徑球)。

(11) 排列(Arrangement) (2課時(shí))

講授排列及其應(yīng)用。一個(gè)線段和多邊形的集合對(duì)平面的劃分,稱(chēng)為一個(gè)排列(an arrangement)。排列可以用來(lái)解決多類(lèi)問(wèn)題,因此排列的算法和復(fù)雜性問(wèn)題十分重要。機(jī)器人的路徑規(guī)劃問(wèn)題可以表述為排列問(wèn)題。

(12) 路徑規(guī)劃(Motion Planning) (2課時(shí))

結(jié)合機(jī)器人的最短路徑問(wèn)題講授路徑規(guī)劃算法。

(13) 幾何數(shù)據(jù)結(jié)構(gòu)Geometric Data Structures) (2課時(shí))

講授DCEL(Doubly-Connected Edge List),Quad-tree, K-d tree, Interval Trees, Priority Search Trees, Segment Trees等數(shù)據(jù)結(jié)構(gòu)。

(14) 幾何算法設(shè)計(jì)范式(Geometric Algorithm Paradigms) (2課時(shí))

講授分治法(Divide and Conquer Algorithm)、掃描法(Sweep Algorithm)、幾何變換法(Geometric Transformation Algorithm)、隨機(jī)增量法(Randomized Incremental Algorithm)等。

(15) 學(xué)生上機(jī)(8課時(shí))

學(xué)生上機(jī)時(shí)間可以穿插到上述內(nèi)容中間。

3教材和參考書(shū)推薦

《計(jì)算幾何導(dǎo)論》是F. P.Preparata和M. I. Shamos 80年代初在M. I. Shamos的博士論文的基礎(chǔ)上寫(xiě)成的專(zhuān)著,是計(jì)算幾何領(lǐng)域的第一本標(biāo)準(zhǔn)教材,雖然其內(nèi)容已經(jīng)多年沒(méi)有更新,但仍然為公認(rèn)的計(jì)算幾何參考書(shū)?？茖W(xué)出版社于1998年將其翻譯為中本出版,應(yīng)該說(shuō)具有獨(dú)到的眼見(jiàn)。

Joseph O'Rourke的《Computational geometry in C》也是一本比較公認(rèn)的好教材,其內(nèi)容比較經(jīng)典,特別注重實(shí)踐環(huán)節(jié),所有算法都給出了C語(yǔ)言實(shí)現(xiàn)。

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

Schwarzkopf著的《計(jì)算幾何:算法與應(yīng)用》(第2版)是目前公認(rèn)的計(jì)算幾何領(lǐng)域的經(jīng)典教材。該教材準(zhǔn)確地講述了計(jì)算幾何的基本概念,注重實(shí)踐環(huán)節(jié),每章都設(shè)有“注釋及評(píng)論”和“習(xí)題”,擴(kuò)大讀者視野、啟迪讀者思維,及時(shí)反映了該學(xué)科領(lǐng)域的發(fā)展動(dòng)向。國(guó)際知名大學(xué)開(kāi)設(shè)的“計(jì)算幾何”課程一般都會(huì)指定此書(shū)作為教材。該書(shū)已由清華大學(xué)鄧俊輝副教授翻譯為中文經(jīng)清華大學(xué)出版社出版。

周培德教授著的《計(jì)算幾何:算法分析與設(shè)計(jì)》是國(guó)內(nèi)出版的第一本中文版計(jì)算幾何專(zhuān)著,是一本較好的計(jì)算幾何參考書(shū)。作者周培德教授多年來(lái)一直從事計(jì)算幾何算法研究,是多部教材和專(zhuān)著的作者。

上述幾本教材由于多種原因也存在一定的局限性。《計(jì)算幾何導(dǎo)論》于1985年寫(xiě)成,雖然經(jīng)典,但沒(méi)有反映近20年來(lái)計(jì)算幾何的最新成果。《Computational geometry in C》雖然注重實(shí)現(xiàn),但是用C實(shí)現(xiàn)的,沒(méi)有使用CGAL,這會(huì)加重學(xué)習(xí)負(fù)擔(dān)?！队?jì)算幾何:算法與應(yīng)用》和《計(jì)算幾何:算法分析與設(shè)計(jì)》的第1版成書(shū)在2000年以前,第2版除了對(duì)舊版進(jìn)行勘誤、增加新的內(nèi)容外,編撰思路和書(shū)的結(jié)構(gòu)等基本沒(méi)有改變。由于當(dāng)時(shí)CGAL還沒(méi)有流行,使得以上教材不可能十分注算法實(shí)現(xiàn)。

由于計(jì)算幾何領(lǐng)域近年來(lái)發(fā)展顯著(如CGAL的出現(xiàn)),新的算法和應(yīng)用領(lǐng)域不斷出現(xiàn),計(jì)算幾何領(lǐng)域僅有上述描述的幾部教材還遠(yuǎn)不能滿(mǎn)足實(shí)際的需求。因此,如果能夠提供新的借鑒已有教材優(yōu)點(diǎn)、反映計(jì)算幾何最新的研究成果、強(qiáng)調(diào)實(shí)現(xiàn)的教材,將會(huì)很有吸引力。與其他計(jì)算機(jī)學(xué)科動(dòng)輒幾十部甚至上百部教材相比,確實(shí)需要有關(guān)方面的研究人員多出幾部精品教材,滿(mǎn)足各類(lèi)讀者的需求,希望國(guó)內(nèi)學(xué)者將來(lái)能寫(xiě)出有影響的教材來(lái)。

4結(jié)論

計(jì)算幾何已經(jīng)是一個(gè)成熟的學(xué)科,主要研究與幾何問(wèn)題有關(guān)的算法,典型的應(yīng)用領(lǐng)域包括計(jì)算機(jī)圖形學(xué)、圖像處理、地理信息系統(tǒng)(GIS)、機(jī)器人學(xué)和CAD/CAM等。國(guó)外許多知名大學(xué)早已將計(jì)算幾何作為碩士生或高年級(jí)本科生的專(zhuān)業(yè)基礎(chǔ)課程。鑒于計(jì)算幾何學(xué)科的基礎(chǔ)性和應(yīng)用的廣泛性,建議國(guó)內(nèi)的計(jì)算機(jī)系開(kāi)設(shè)此課程。

參考文獻(xiàn):

[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. 計(jì)算幾何:算法與應(yīng)用[M]. 鄧俊輝,譯. 2版. 北京:清華大學(xué)出版社,2005.

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

[4][美]F.P.普雷帕拉塔,M.I.沙莫斯. 計(jì)算幾何導(dǎo)論[M]. 莊心谷,譯. 北京:科學(xué)出版社,1998.

[5] 周培德. 計(jì)算幾何:算法分析與設(shè)計(jì)[M]. 2版. 北京:清華大學(xué)出版社,2004.