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

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

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

2、易讀、易懂，并使讀者能夠應(yīng)用這些理論和算法。為便于消化和理解書(shū)中內(nèi)容，每章末附有習(xí)題，以及大量參考文獻(xiàn)。本書(shū)可作為高等院校計(jì)算機(jī)及應(yīng)用數(shù)學(xué)等學(xué)科的本科生、研究生學(xué)習(xí)計(jì)算幾何的教材，也可作為從事計(jì)算幾何研究或應(yīng)用的其他科技工作者的參考用書(shū)。圖書(shū)在版編目（CIP）數(shù)據(jù)計(jì)算幾何及應(yīng)用／汪嘉業(yè)等編著．—北京：科學(xué)出版社，２０１１?。ㄖ袆?chuàng)軟件叢書(shū)）ISBN９７８‐７‐０３‐０３２２５７‐９?、駮尝儆?jì)?　Ⅱ暢①汪??、髸尝儆?jì)算幾何②計(jì)算機(jī)算法?、魰尝伲埃保涪赥P３０１暢６中國(guó)版本圖書(shū)館CIP數(shù)據(jù)核字（２０１１

3、）第１７８４５７號(hào)責(zé)任編輯：鞠麗娜／責(zé)任校對(duì)：耿耘責(zé)任印制：呂春珉／封面設(shè)計(jì)：三函設(shè)計(jì)出版北京東黃城根北街１６號(hào)郵政編碼：１００７１７http：／／www．sciencep．com科學(xué)出版社印刷科學(xué)出版社發(fā)行各地新華書(shū)店經(jīng)銷(xiāo)倡２０１１年９月第一版開(kāi)本：７８７×１０９２?。保保叮玻埃保蹦辏乖碌谝淮斡∷⒂垼海保梗保猜毥碳夹g(shù)出版中心印數(shù)：１—３０００字?jǐn)?shù)：４４２０００www.abook.cn定價(jià)：46暢00元（如有印裝質(zhì)量問(wèn)題，我社負(fù)責(zé)調(diào)換枙　　枛）銷(xiāo)售部電話：０１０‐６２１３４９８８　編輯部電話

4、０１０‐６２１３８９７８‐８００２版權(quán)所有，侵權(quán)必究舉報(bào)電話：０１０‐６４０３０２２９；０１０‐６４０３４３１５；１３５０１１５１３０３前言在２０世紀(jì)７０年代，“計(jì)算幾何”這個(gè)名詞曾經(jīng)被不同學(xué)術(shù)領(lǐng)域如模式識(shí)別、自由曲線曲面設(shè)計(jì)以及離散幾何問(wèn)題的算法設(shè)計(jì)與分析等使用過(guò)。１９７８年，M暢I暢Shamos在其博士論文“ComputationalGeometry”中歸納和提出了一百多個(gè)離散幾何問(wèn)題及其算法。此后，計(jì)算幾何被公認(rèn)為是“離散幾何問(wèn)題的算法設(shè)計(jì)與分析”這一學(xué)術(shù)領(lǐng)域的名稱(chēng)。經(jīng)過(guò)近３０多年的快速發(fā)展

5、，其研究?jī)?nèi)容不斷擴(kuò)大，涉及了凸包、Voronoi圖、三角剖分、多邊形剖分、幾何搜索、求交、可見(jiàn)性計(jì)算、路徑規(guī)劃、碰撞檢測(cè)等眾多內(nèi)容。計(jì)算幾何所研究的這些基本問(wèn)題大都是歐幾里德幾何問(wèn)題。它們之所以到現(xiàn)在才被提出來(lái)并研究其算法，是因?yàn)樗鼈兩婕傲舜罅康挠?jì)算，所以只有在使用計(jì)算機(jī)的時(shí)代才會(huì)被提出來(lái)并要求解決。同時(shí)，這些問(wèn)題有著廣泛的應(yīng)用背景。如在計(jì)算機(jī)圖形學(xué)及虛擬現(xiàn)實(shí)中，從建模到繪制幾乎都會(huì)用到計(jì)算幾何的算法；幾何搜索可為數(shù)據(jù)庫(kù)的搜索提供有效算法；機(jī)器人運(yùn)動(dòng)規(guī)劃、碰撞計(jì)算等計(jì)算幾何的重要內(nèi)容也為大規(guī)模集成

6、電路設(shè)計(jì)、機(jī)械加工、虛擬裝配、GIS等提供了必不可少的實(shí)踐和理論基礎(chǔ)。此外，計(jì)算幾何還為線性規(guī)劃、聚類(lèi)分析、概率統(tǒng)計(jì)方法等提供新的算法。由于這個(gè)領(lǐng)域有著非常廣泛的應(yīng)用背景及深入探討的理論價(jià)值，因此在國(guó)際上很快成為學(xué)術(shù)研究的熱點(diǎn)，受到廣泛重視。如在美國(guó)斯坦福大學(xué)、普林斯頓大學(xué)等國(guó)際著名學(xué)府都有專(zhuān)門(mén)的計(jì)算幾何研究團(tuán)隊(duì)；目前已有多個(gè)計(jì)算幾何的國(guó)際學(xué)術(shù)期刊；每年也召開(kāi)若干個(gè)國(guó)際學(xué)術(shù)會(huì)議。在國(guó)際上熱火朝天地研究計(jì)算幾何的３０年中，這門(mén)學(xué)科在我國(guó)幾乎是被冷落的，很少有人系統(tǒng)地對(duì)其進(jìn)行研究，開(kāi)設(shè)這門(mén)課程的也僅有

7、清華大學(xué)、浙江大學(xué)、山東大學(xué)等少數(shù)幾個(gè)單位。一般地，研究算法的學(xué)者多熱衷于圖論算法的設(shè)計(jì)與分析；而對(duì)研究與計(jì)算有關(guān)的幾何問(wèn)題的學(xué)者而言，在連續(xù)的曲線曲面上做研究更是得心應(yīng)手。然而，人們?cè)诤芏鄳?yīng)用中又不可避免地會(huì)碰到各種各樣的計(jì)算幾何問(wèn)題。盡管在我國(guó)的學(xué)術(shù)刊物上也偶爾會(huì)刊登與應(yīng)用有密切關(guān)聯(lián)的討論離散幾何的文章，但由于國(guó)內(nèi)缺乏對(duì)該學(xué)科的系統(tǒng)研究和教學(xué)的環(huán)境，研究水平與國(guó)外相比還有一定差距。為此，我們?cè)诙嗄陱氖掠?jì)算幾何科研、教學(xué)工作的基礎(chǔ)上出版了本書(shū)，力爭(zhēng)比較全面地介紹計(jì)算幾何的基本問(wèn)題、基礎(chǔ)理論和算法

8、，以促進(jìn)國(guó)內(nèi)計(jì)算幾何的研究和教學(xué)工作。本書(shū)適合作為研究生的教材。若為碩士生上課，可以講授其中部分章節(jié)，如第一章～第九章。對(duì)于計(jì)算機(jī)專(zhuān)業(yè)的學(xué)生，由于較少學(xué)習(xí)具有嚴(yán)格邏輯推理的課程，所以可通過(guò)本書(shū)的學(xué)習(xí)，彌補(bǔ)這方面能力培養(yǎng)的不足。對(duì)于數(shù)學(xué)或其他專(zhuān)業(yè)的學(xué)生，通過(guò)本書(shū)的學(xué)習(xí)，可以對(duì)計(jì)算機(jī)算法的研究方法有所了解。本書(shū)也可作為從事計(jì)算幾何研究或應(yīng)用的其他科技工作者的參考用書(shū)。本書(shū)的寫(xiě)作特色是在注重介紹計(jì)算幾何基礎(chǔ)理論的同時(shí)，也注意介紹簡(jiǎn)潔、實(shí)用和　·ii·計(jì)算幾何及應(yīng)用易編程的算法，力求讓讀者