關于計算機系開設“計算幾何”課程的建議

吳壯志

摘要:本文主要討論了在大學計算機系開設“計算幾何”課程的可行性和必要性,對“計算幾何”這門學科進行了概略的介紹,給出了課程大綱的具體建議,并對推薦的教材和參考書進行了詳細分析。

關鍵詞:計算幾何;幾何算法;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.