計(jì)算幾何及應(yīng)用

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

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

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

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

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

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

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

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

8、用和　·ii·計(jì)算幾何及應(yīng)用易編程的算法，力求讓讀者