出版時(shí)間:2009-6 出版社:清華大學(xué)出版社 作者:(德)伯格(Berg,M.D.) 等著,鄧俊輝 譯 頁(yè)數(shù):407 字?jǐn)?shù):636000 譯者:鄧俊輝
Tag標(biāo)簽:無(wú)
前言
20世紀(jì)70年代末,計(jì)算幾何學(xué)(computationalgeometry)從算法設(shè)計(jì)與分析中孕育而生。今天,它不僅擁有自己的學(xué)術(shù)刊物和學(xué)術(shù)會(huì)議,而且形成了一個(gè)由眾多活躍的研究人員組成的學(xué)術(shù)群體,因此已經(jīng)成長(zhǎng)為一個(gè)被廣泛認(rèn)同的學(xué)科。該領(lǐng)域作為一個(gè)研究學(xué)科之所以會(huì)取得成功,一方面是由于其涉及的問(wèn)題及其解答本身所具有的美感,而另一方面,也是由于在(諸如計(jì)算機(jī)圖形學(xué)、地理信息系統(tǒng)和機(jī)器人學(xué)等)眾多的應(yīng)用領(lǐng)域中,幾何算法都發(fā)揮了重要的作用?! ≡S多解決幾何問(wèn)題的早期算法,要么速度很慢,要么難于理解與實(shí)現(xiàn)。隨著近年來(lái)一些新的算法技術(shù)的發(fā)展,此前的很多方法都得到了改進(jìn)與簡(jiǎn)化。這本教材力圖使得這些現(xiàn)代的算法能夠?yàn)楦鼜V泛的讀者理解和接受。本書既是面向計(jì)算幾何課程的一本教材,同時(shí)也可用于自學(xué)?! ”緯慕Y(jié)構(gòu)。除導(dǎo)言外,這16章中的每一章都從來(lái)自應(yīng)用領(lǐng)域的某一實(shí)際問(wèn)題入手。這個(gè)問(wèn)題將被轉(zhuǎn)化為一個(gè)純粹的幾何問(wèn)題,進(jìn)而通過(guò)計(jì)算幾何所提供的方法加以解決。每章所討論的,實(shí)質(zhì)上就是對(duì)應(yīng)的那個(gè)幾何問(wèn)題,以及解決該問(wèn)題所需要的概念與方法。我們根據(jù)所希望覆蓋的計(jì)算幾何專題,來(lái)選取有關(guān)的應(yīng)用;而就具體的應(yīng)用領(lǐng)域而言,這些介紹還遠(yuǎn)遠(yuǎn)不夠全面。引入這些應(yīng)用的目的,只是為了激發(fā)讀者的興趣;而各章本身的目的,并不在于為這些問(wèn)題提供現(xiàn)成可用的解決方法。雖然如此,我們還是認(rèn)為,為有效地解決應(yīng)用中的幾何問(wèn)題,計(jì)算幾何方面的知識(shí)是非常重要的。希望本書不僅能夠吸引來(lái)自算法學(xué)術(shù)圈的那些人,而且對(duì)來(lái)自應(yīng)用領(lǐng)域的人們亦是如此。
內(nèi)容概要
計(jì)算幾何是計(jì)算機(jī)理論科學(xué)的一個(gè)重要分支,自20世紀(jì)70年代末從算法設(shè)計(jì)與分析中獨(dú)立出來(lái)起,已經(jīng)有了巨大的發(fā)展,不僅產(chǎn)生了一系列重要的理論成果,也在眾多實(shí)際領(lǐng)域中得到了廣泛的應(yīng)用。 本書的前4章對(duì)幾何算法進(jìn)行了討論,包括幾何求交、三角剖分、線性規(guī)劃等,其中涉及的隨機(jī)算法也是本書的一個(gè)鮮明特點(diǎn)。第5章至第10章介紹了多種幾何結(jié)構(gòu),包括幾何查找、kd樹、區(qū)域樹、梯形圖、Voronoi圖、排列、Delaunay三角剖分、區(qū)間樹、優(yōu)先查找樹以及線段樹等。第11章至第16章結(jié)合實(shí)際問(wèn)題,繼續(xù)討論了若干幾何算法及其數(shù)據(jù)結(jié)構(gòu),包括高維凸包、空間二分及BSP樹、運(yùn)動(dòng)規(guī)劃、網(wǎng)格生成及四叉樹、最短路徑查找及可見(jiàn)性圖、單純性區(qū)域查找及劃分樹和切分樹等,這些也是對(duì)前10章內(nèi)容的進(jìn)一步深化。 本書不僅內(nèi)容全面,而且緊扣實(shí)際應(yīng)用,重點(diǎn)突出,既有深入的講解,同時(shí)每章都設(shè)有“注釋及評(píng)論”和“習(xí)題”,方便讀者更深入的理解,被世界眾多大學(xué)作為教材。
書籍目錄
前言1 計(jì)算幾何:導(dǎo)言 1.1 凸包的例子 1.2 退化及魯棒性 1.3 應(yīng)用領(lǐng)域 1.3.1 計(jì)算機(jī)圖形學(xué) 1.3.2 機(jī)器人學(xué) 1.3.3 地理信息系統(tǒng) 1.3.4 CAD/CAM 1.3.5 其他應(yīng)用領(lǐng)域 1.4 注釋及評(píng)論2 線段求交:專題圖疊合 2.1 線段求交 2.2 雙向鏈接邊表 2.3 計(jì)算子區(qū)域劃分的疊合 2.4 布爾運(yùn)算 2.5 注釋及評(píng)論 習(xí)題3 多邊形三角剖分:畫廊看守 3.1 看守與三角剖分 3.2 多邊形的單調(diào)塊劃分 3.3 單調(diào)多邊形的三角剖分 3.4 注釋及評(píng)論 習(xí)題4 線性規(guī)劃:鑄模制造 4.1 鑄造中的幾何 4.2 半平面求交 4.3 遞增式線性規(guī)劃 4.4 隨機(jī)線性規(guī)劃 4.5 無(wú)界線性規(guī)劃問(wèn)題 4.6 高維空間中的線性規(guī)劃 4.7 最小包圍圓 4.8 注釋及評(píng)論 習(xí)題5 正交區(qū)域查找:數(shù)據(jù)庫(kù)查詢 5.1 一維區(qū)域查找 5.2 kd-樹 5.3 區(qū)域樹 5.4 高維區(qū)域樹 5.5 一般性點(diǎn)集 5.6 分散層疊 5.7 注釋及評(píng)論 習(xí)題6 點(diǎn)定位:找到自己的位置 6.1 點(diǎn)定位及梯形圖 6.2 隨機(jī)增量式算法 6.3 退化情況的處理 6.4 木尾分析 6.5 注釋及評(píng)論 習(xí)題7 Voronoi圖:郵局問(wèn)題 7.1 定義及基本性質(zhì) 7.2 構(gòu)造Voronoi圖 7.3 線段集Voronoi圖 7.4 最遠(yuǎn)點(diǎn)Voronoi圖 7.5 注釋及評(píng)論 習(xí)題8 排列與對(duì)偶:光線跟蹤超采樣 8.1 差異值的計(jì)算 8.2 對(duì)偶變換 8.3 直線的排列 ……9 Delaunay三角剖分:高度插值10 更多幾何數(shù)據(jù)結(jié)構(gòu):截窗11 凸包:混合物12 空間二分:畫家算法13 機(jī)器人運(yùn)動(dòng)規(guī)劃:隨意所之14 四叉樹:非均勻網(wǎng)格生成15 可見(jiàn)性圖:求最短路徑16 單純形區(qū)域查找:再論截窗參考文獻(xiàn)圖表索引觀察結(jié)論、引理、定理及推論索引關(guān)鍵詞索引
章節(jié)摘錄
與上例相同,這一問(wèn)題的實(shí)質(zhì)也是幾何的:給定一組幾何形狀不同的障礙物,我們需要在不與任何障礙物發(fā)生碰撞的前提下,找出連接于任意兩點(diǎn)之間的最短通路。這就是所謂的運(yùn)動(dòng)規(guī)劃(motion planning),在機(jī)器人學(xué)中,這類問(wèn)題的求解至關(guān)重要。第13和15章將針對(duì)運(yùn)動(dòng)規(guī)劃所需的幾何算法做一討論?! 〉谌齻€(gè)例子。假設(shè)你可以利用的不是一張而是兩張地圖:一張描述了各個(gè)建筑物,包括公用電話;另一張則畫出了校園內(nèi)的道路。為了規(guī)劃出通往公用電話的運(yùn)動(dòng)路徑,我們需要將這兩張地圖疊合(overlay)起來(lái)——也就是說(shuō),需要將這兩張地圖所提供的信息合并起來(lái)。在地理信息系統(tǒng)(geographic information system)中,地圖的疊合是基本的操作之一。這種操作涉及到某張地圖中的對(duì)象在另一張弛圖中的定位、不同特征物之間的求交計(jì)算等問(wèn)題。第2章將討論這一問(wèn)題。 許多幾何問(wèn)題的解決都要依靠精心設(shè)計(jì)的幾何算法,上面只是其中的三個(gè)例子。誕生于20世紀(jì)70年代的計(jì)算幾何(computational geometry),正是旨在解決這類幾何問(wèn)題。這一學(xué)科可定義為“針對(duì)處理幾何對(duì)象的算法及數(shù)據(jù)結(jié)構(gòu)的系統(tǒng)化研究”,其重點(diǎn)在于“漸進(jìn)快速的精確算法”。由幾何問(wèn)題帶來(lái)的挑戰(zhàn)吸引了眾多的研究人員。從對(duì)問(wèn)題的明確表述,到得出高效而優(yōu)雅的解決方法,往往需要經(jīng)歷漫長(zhǎng)的過(guò)程,其間既要克服諸多困難,也要積累一些次優(yōu)的中間結(jié)果。今天,我們已經(jīng)掌握了功能廣泛的一整套幾何算法,它們不僅高效而且相對(duì)更易理解和實(shí)現(xiàn)?! ”緯鴮⒔榻B計(jì)算幾何中最重要的那些概念、方法、算法以及數(shù)據(jù)結(jié)構(gòu),但愿我們的介紹方式,能夠吸引那些有志于將計(jì)算幾何的研究成果付諸實(shí)際應(yīng)用的讀者。本書的每一章都從某一實(shí)際問(wèn)題入手,而這種問(wèn)題的求解,都需要借助幾何算法。為了說(shuō)明計(jì)算幾何之應(yīng)用范圍的廣泛性,這些問(wèn)題分別選自不同的應(yīng)用領(lǐng)域:機(jī)器人學(xué)、計(jì)算機(jī)圖形學(xué)、CAD/CAM以及地理信息系統(tǒng)等。
圖書封面
圖書標(biāo)簽Tags
無(wú)
評(píng)論、評(píng)分、閱讀與下載