計算幾何及應用

《計算幾何及應用》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在工程資料-天天文庫。

1、科學出版社職教技術出版中心www.abook.cn中創(chuàng)軟件叢書計算幾何及應用汪嘉業(yè)王文平屠長河楊承磊編著北京內(nèi)容簡介本書比較全面地介紹了計算幾何的基本問題、基礎理論和算法。本書前１２章分別介紹了凸包、Voronoi圖、三角剖分、多邊形剖分、幾何搜索、相交計算、排列、可見性計算、路徑規(guī)劃等基本計算幾何問題和算法，第１３、１４章則分別探討了若干隨機和并行的計算幾何算法，最后一章給出了關于計算幾何的幾個實際研究和應用中的例子。本書在注重介紹計算幾何基礎理論的同時，也注意介紹簡潔、實用和易編程的算法，力求易讀、易懂，并使讀者能夠應用這些理論和算法。為便于消化和理解書

2、中內(nèi)容，每章末附有習題，以及大量參考文獻。本書可作為高等院校計算機及應用數(shù)學等學科的本科生、研究生學習計算幾何的教材，也可作為從事計算幾何研究或應用的其他科技工作者的參考用書。圖書在版編目（CIP）數(shù)據(jù)計算幾何及應用／汪嘉業(yè)等編著．—北京：科學出版社，２０１１?。ㄖ袆?chuàng)軟件叢書）ISBN９７８‐７‐０３‐０３２２５７‐９　Ⅰ暢①計??、驎尝偻??、髸尝儆嬎銕缀微谟嬎銠C算法?、魰尝伲埃保涪赥P３０１暢６中國版本圖書館CIP數(shù)據(jù)核字（２０１１）第１７８４５７號責任編輯：鞠麗娜／責任校對：耿耘責任印制：呂春珉／封面設計：三函設計出版北京東黃城根北街１６號郵政編碼：１

3、００７１７http：／／www．sciencep．com科學出版社印刷科學出版社發(fā)行各地新華書店經(jīng)銷倡２０１１年９月第一版開本：７８７×１０９２?。保保叮玻埃保蹦辏乖碌谝淮斡∷⒂垼海保梗保猜毥碳夹g出版中心印數(shù)：１—３０００字數(shù)：４４２０００www.abook.cn定價：46暢00元（如有印裝質量問題，我社負責調換枙　　枛）銷售部電話：０１０‐６２１３４９８８　編輯部電話０１０‐６２１３８９７８‐８００２版權所有，侵權必究舉報電話：０１０‐６４０３０２２９；０１０‐６４０３４３１５；１３５０１１５１３０３前言在２０世紀７０年代，“計算幾何”這個名詞曾經(jīng)被

4、不同學術領域如模式識別、自由曲線曲面設計以及離散幾何問題的算法設計與分析等使用過。１９７８年，M暢I暢Shamos在其博士論文“ComputationalGeometry”中歸納和提出了一百多個離散幾何問題及其算法。此后，計算幾何被公認為是“離散幾何問題的算法設計與分析”這一學術領域的名稱。經(jīng)過近３０多年的快速發(fā)展，其研究內(nèi)容不斷擴大，涉及了凸包、Voronoi圖、三角剖分、多邊形剖分、幾何搜索、求交、可見性計算、路徑規(guī)劃、碰撞檢測等眾多內(nèi)容。計算幾何所研究的這些基本問題大都是歐幾里德幾何問題。它們之所以到現(xiàn)在才被提出來并研究其算法，是因為它們涉及了大量的計

5、算，所以只有在使用計算機的時代才會被提出來并要求解決。同時，這些問題有著廣泛的應用背景。如在計算機圖形學及虛擬現(xiàn)實中，從建模到繪制幾乎都會用到計算幾何的算法；幾何搜索可為數(shù)據(jù)庫的搜索提供有效算法；機器人運動規(guī)劃、碰撞計算等計算幾何的重要內(nèi)容也為大規(guī)模集成電路設計、機械加工、虛擬裝配、GIS等提供了必不可少的實踐和理論基礎。此外，計算幾何還為線性規(guī)劃、聚類分析、概率統(tǒng)計方法等提供新的算法。由于這個領域有著非常廣泛的應用背景及深入探討的理論價值，因此在國際上很快成為學術研究的熱點，受到廣泛重視。如在美國斯坦福大學、普林斯頓大學等國際著名學府都有專門的計算幾何研究

6、團隊；目前已有多個計算幾何的國際學術期刊；每年也召開若干個國際學術會議。在國際上熱火朝天地研究計算幾何的３０年中，這門學科在我國幾乎是被冷落的，很少有人系統(tǒng)地對其進行研究，開設這門課程的也僅有清華大學、浙江大學、山東大學等少數(shù)幾個單位。一般地，研究算法的學者多熱衷于圖論算法的設計與分析；而對研究與計算有關的幾何問題的學者而言，在連續(xù)的曲線曲面上做研究更是得心應手。然而，人們在很多應用中又不可避免地會碰到各種各樣的計算幾何問題。盡管在我國的學術刊物上也偶爾會刊登與應用有密切關聯(lián)的討論離散幾何的文章，但由于國內(nèi)缺乏對該學科的系統(tǒng)研究和教學的環(huán)境，研究水平與國外相

7、比還有一定差距。為此，我們在多年從事計算幾何科研、教學工作的基礎上出版了本書，力爭比較全面地介紹計算幾何的基本問題、基礎理論和算法，以促進國內(nèi)計算幾何的研究和教學工作。本書適合作為研究生的教材。若為碩士生上課，可以講授其中部分章節(jié)，如第一章～第九章。對于計算機專業(yè)的學生，由于較少學習具有嚴格邏輯推理的課程，所以可通過本書的學習，彌補這方面能力培養(yǎng)的不足。對于數(shù)學或其他專業(yè)的學生，通過本書的學習，可以對計算機算法的研究方法有所了解。本書也可作為從事計算幾何研究或應用的其他科技工作者的參考用書。本書的寫作特色是在注重介紹計算幾何基礎理論的同時，也注意介紹簡潔、實

8、用和　·ii·計算幾何及應用易編程的算法，力求讓讀者