計(jì)算幾何

前言

　　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ì)取得成功，一方面是由于其涉及的問題及其解答本身所具有的美感，而另一方面，也是由于在（諸如計(jì)算機(jī)圖形學(xué)、地理信息系統(tǒng)和機(jī)器人學(xué)等）眾多的應(yīng)用領(lǐng)域中，幾何算法都發(fā)揮了重要的作用。　　許多解決幾何問題的早期算法，要么速度很慢，要么難于理解與實(shí)現(xiàn)。隨著近年來一些新的算法技術(shù)的發(fā)展，此前的很多方法都得到了改進(jìn)與簡(jiǎn)化。這本教材力圖使得這些現(xiàn)代的算法能夠?yàn)楦鼜V泛的讀者理解和接受。本書既是面向計(jì)算幾何課程的一本教材，同時(shí)也可用于自學(xué)。　　本書的結(jié)構(gòu)。除導(dǎo)言外，這16章中的每一章都從來自應(yīng)用領(lǐng)域的某一實(shí)際問題入手。這個(gè)問題將被轉(zhuǎn)化為一個(gè)純粹的幾何問題，進(jìn)而通過計(jì)算幾何所提供的方法加以解決。每章所討論的，實(shí)質(zhì)上就是對(duì)應(yīng)的那個(gè)幾何問題，以及解決該問題所需要的概念與方法。我們根據(jù)所希望覆蓋的計(jì)算幾何專題，來選取有關(guān)的應(yīng)用；而就具體的應(yīng)用領(lǐng)域而言，這些介紹還遠(yuǎn)遠(yuǎn)不夠全面。引入這些應(yīng)用的目的，只是為了激發(fā)讀者的興趣；而各章本身的目的，并不在于為這些問題提供現(xiàn)成可用的解決方法。雖然如此，我們還是認(rèn)為，為有效地解決應(yīng)用中的幾何問題，計(jì)算幾何方面的知識(shí)是非常重要的。希望本書不僅能夠吸引來自算法學(xué)術(shù)圈的那些人，而且對(duì)來自應(yīng)用領(lǐng)域的人們亦是如此。

內(nèi)容概要

計(jì)算幾何是計(jì)算機(jī)理論科學(xué)的一個(gè)重要分支，自20世紀(jì)70年代末從算法設(shè)計(jì)與分析中獨(dú)立出來起，已經(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í)際問題，繼續(xù)討論了若干幾何算法及其數(shù)據(jù)結(jié)構(gòu)，包括高維凸包、空間二分及BSP樹、運(yùn)動(dòng)規(guī)劃、網(wǎng)格生成及四叉樹、最短路徑查找及可見性圖、單純性區(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 無界線性規(guī)劃問題  4.6 高維空間中的線性規(guī)劃  4.7 最小包圍圓  4.8 注釋及評(píng)論  習(xí)題5 正交區(qū)域查找：數(shù)據(jù)庫查詢  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圖：郵局問題  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 可見性圖：求最短路徑16 單純形區(qū)域查找：再論截窗參考文獻(xiàn)圖表索引觀察結(jié)論、引理、定理及推論索引關(guān)鍵詞索引

章節(jié)摘錄

　　與上例相同，這一問題的實(shí)質(zhì)也是幾何的：給定一組幾何形狀不同的障礙物，我們需要在不與任何障礙物發(fā)生碰撞的前提下，找出連接于任意兩點(diǎn)之間的最短通路。這就是所謂的運(yùn)動(dòng)規(guī)劃（motion planning），在機(jī)器人學(xué)中，這類問題的求解至關(guān)重要。第13和15章將針對(duì)運(yùn)動(dòng)規(guī)劃所需的幾何算法做一討論?！　〉谌齻€(gè)例子。假設(shè)你可以利用的不是一張而是兩張地圖：一張描述了各個(gè)建筑物，包括公用電話；另一張則畫出了校園內(nèi)的道路。為了規(guī)劃出通往公用電話的運(yùn)動(dòng)路徑，我們需要將這兩張地圖疊合（overlay）起來——也就是說，需要將這兩張地圖所提供的信息合并起來。在地理信息系統(tǒng)（geographic information system）中，地圖的疊合是基本的操作之一。這種操作涉及到某張地圖中的對(duì)象在另一張弛圖中的定位、不同特征物之間的求交計(jì)算等問題。第2章將討論這一問題?！　≡S多幾何問題的解決都要依靠精心設(shè)計(jì)的幾何算法，上面只是其中的三個(gè)例子。誕生于20世紀(jì)70年代的計(jì)算幾何（computational geometry），正是旨在解決這類幾何問題。這一學(xué)科可定義為“針對(duì)處理幾何對(duì)象的算法及數(shù)據(jù)結(jié)構(gòu)的系統(tǒng)化研究”，其重點(diǎn)在于“漸進(jìn)快速的精確算法”。由幾何問題帶來的挑戰(zhàn)吸引了眾多的研究人員。從對(duì)問題的明確表述，到得出高效而優(yōu)雅的解決方法，往往需要經(jīng)歷漫長(zhǎng)的過程，其間既要克服諸多困難，也要積累一些次優(yōu)的中間結(jié)果。今天，我們已經(jīng)掌握了功能廣泛的一整套幾何算法，它們不僅高效而且相對(duì)更易理解和實(shí)現(xiàn)?！　”緯鴮⒔榻B計(jì)算幾何中最重要的那些概念、方法、算法以及數(shù)據(jù)結(jié)構(gòu)，但愿我們的介紹方式，能夠吸引那些有志于將計(jì)算幾何的研究成果付諸實(shí)際應(yīng)用的讀者。本書的每一章都從某一實(shí)際問題入手，而這種問題的求解，都需要借助幾何算法。為了說明計(jì)算幾何之應(yīng)用范圍的廣泛性，這些問題分別選自不同的應(yīng)用領(lǐng)域：機(jī)器人學(xué)、計(jì)算機(jī)圖形學(xué)、CAD／CAM以及地理信息系統(tǒng)等。

圖書封面

圖書標(biāo)簽Tags

無

評(píng)論、評(píng)分、閱讀與下載

---

    計(jì)算幾何 PDF格式下載

---