計算幾何

前言

　　20世紀70年代末，計算幾何學（computationalgeometry）從算法設計與分析中孕育而生。今天，它不僅擁有自己的學術(shù)刊物和學術(shù)會議，而且形成了一個由眾多活躍的研究人員組成的學術(shù)群體，因此已經(jīng)成長為一個被廣泛認同的學科。該領(lǐng)域作為一個研究學科之所以會取得成功，一方面是由于其涉及的問題及其解答本身所具有的美感，而另一方面，也是由于在（諸如計算機圖形學、地理信息系統(tǒng)和機器人學等）眾多的應用領(lǐng)域中，幾何算法都發(fā)揮了重要的作用。　　許多解決幾何問題的早期算法，要么速度很慢，要么難于理解與實現(xiàn)。隨著近年來一些新的算法技術(shù)的發(fā)展，此前的很多方法都得到了改進與簡化。這本教材力圖使得這些現(xiàn)代的算法能夠為更廣泛的讀者理解和接受。本書既是面向計算幾何課程的一本教材，同時也可用于自學?！　”緯慕Y(jié)構(gòu)。除導言外，這16章中的每一章都從來自應用領(lǐng)域的某一實際問題入手。這個問題將被轉(zhuǎn)化為一個純粹的幾何問題，進而通過計算幾何所提供的方法加以解決。每章所討論的，實質(zhì)上就是對應的那個幾何問題，以及解決該問題所需要的概念與方法。我們根據(jù)所希望覆蓋的計算幾何專題，來選取有關(guān)的應用；而就具體的應用領(lǐng)域而言，這些介紹還遠遠不夠全面。引入這些應用的目的，只是為了激發(fā)讀者的興趣；而各章本身的目的，并不在于為這些問題提供現(xiàn)成可用的解決方法。雖然如此，我們還是認為，為有效地解決應用中的幾何問題，計算幾何方面的知識是非常重要的。希望本書不僅能夠吸引來自算法學術(shù)圈的那些人，而且對來自應用領(lǐng)域的人們亦是如此。

內(nèi)容概要

計算幾何是計算機理論科學的一個重要分支，自20世紀70年代末從算法設計與分析中獨立出來起，已經(jīng)有了巨大的發(fā)展，不僅產(chǎn)生了一系列重要的理論成果，也在眾多實際領(lǐng)域中得到了廣泛的應用。    本書的前4章對幾何算法進行了討論，包括幾何求交、三角剖分、線性規(guī)劃等，其中涉及的隨機算法也是本書的一個鮮明特點。第5章至第10章介紹了多種幾何結(jié)構(gòu)，包括幾何查找、kd樹、區(qū)域樹、梯形圖、Voronoi圖、排列、Delaunay三角剖分、區(qū)間樹、優(yōu)先查找樹以及線段樹等。第11章至第16章結(jié)合實際問題，繼續(xù)討論了若干幾何算法及其數(shù)據(jù)結(jié)構(gòu)，包括高維凸包、空間二分及BSP樹、運動規(guī)劃、網(wǎng)格生成及四叉樹、最短路徑查找及可見性圖、單純性區(qū)域查找及劃分樹和切分樹等，這些也是對前10章內(nèi)容的進一步深化。    本書不僅內(nèi)容全面，而且緊扣實際應用，重點突出，既有深入的講解，同時每章都設有“注釋及評論”和“習題”，方便讀者更深入的理解，被世界眾多大學作為教材。

書籍目錄

前言1 計算幾何：導言  1.1 凸包的例子  1.2 退化及魯棒性  1.3 應用領(lǐng)域    1.3.1 計算機圖形學    1.3.2 機器人學    1.3.3 地理信息系統(tǒng)    1.3.4 CAD／CAM    1.3.5 其他應用領(lǐng)域  1.4 注釋及評論2 線段求交：專題圖疊合  2.1 線段求交  2.2 雙向鏈接邊表  2.3 計算子區(qū)域劃分的疊合  2.4 布爾運算  2.5 注釋及評論  習題3 多邊形三角剖分：畫廊看守  3.1 看守與三角剖分  3.2 多邊形的單調(diào)塊劃分  3.3 單調(diào)多邊形的三角剖分  3.4 注釋及評論  習題4 線性規(guī)劃：鑄模制造  4.1 鑄造中的幾何  4.2 半平面求交  4.3 遞增式線性規(guī)劃  4.4 隨機線性規(guī)劃  4.5 無界線性規(guī)劃問題  4.6 高維空間中的線性規(guī)劃  4.7 最小包圍圓  4.8 注釋及評論  習題5 正交區(qū)域查找：數(shù)據(jù)庫查詢  5.1 一維區(qū)域查找  5.2 kd-樹  5.3 區(qū)域樹  5.4 高維區(qū)域樹  5.5 一般性點集  5.6 分散層疊  5.7 注釋及評論  習題6 點定位：找到自己的位置  6.1 點定位及梯形圖  6.2 隨機增量式算法  6.3 退化情況的處理  6.4 木尾分析  6.5 注釋及評論  習題7 Voronoi圖：郵局問題  7.1 定義及基本性質(zhì)  7.2 構(gòu)造Voronoi圖  7.3 線段集Voronoi圖  7.4 最遠點Voronoi圖  7.5 注釋及評論  習題8 排列與對偶：光線跟蹤超采樣  8.1 差異值的計算  8.2 對偶變換  8.3 直線的排列  ……9 Delaunay三角剖分：高度插值10 更多幾何數(shù)據(jù)結(jié)構(gòu)：截窗11 凸包：混合物12 空間二分：畫家算法13 機器人運動規(guī)劃：隨意所之14 四叉樹：非均勻網(wǎng)格生成15 可見性圖：求最短路徑16 單純形區(qū)域查找：再論截窗參考文獻圖表索引觀察結(jié)論、引理、定理及推論索引關(guān)鍵詞索引

章節(jié)摘錄

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

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    計算幾何 PDF格式下載

---