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

內(nèi)容概要

　　《計算幾何及應(yīng)用》比較全面地介紹了計算幾何的基本問題、基礎(chǔ)理論和算法。《計算幾何及應(yīng)用》前12章分別介紹了凸包、Voronoi圖、三角剖分、多邊形剖分、幾何搜索、相交計算、排列、可見性計算、路徑規(guī)劃等基本計算幾何問題和算法，第13、14章則分別探討了若干隨機(jī)和并行的計算幾何算法，最后一章給出了關(guān)于計算幾何的幾個實(shí)際研究和應(yīng)用中的例子?！队嬎銕缀渭皯?yīng)用》在注重介紹計算幾何基礎(chǔ)理論的同時，也注意介紹簡潔、實(shí)用和易編程的算法，力求易讀、易懂，并使讀者能夠應(yīng)用這些理論和算法。為便于消化和理解書中內(nèi)容，每章末附有習(xí)題，以及大量參考文獻(xiàn)。
　　《計算幾何及應(yīng)用》可作為高等院校計算機(jī)及應(yīng)用數(shù)學(xué)等學(xué)科的本科生、研究生學(xué)習(xí)計算幾何的教材，也可作為從事計算幾何研究或應(yīng)用的其他科技工作者的參考用書。

書籍目錄

前言
第一章 引論
　1.1 幾何基礎(chǔ)知識
　1.1.1 基本概念
　1.1.2 幾何對偶
　1.2 算法的復(fù)雜度
　1.2.1 算法復(fù)雜度的度量方法
　1.2.2 排序時間復(fù)雜度的下界
　1.3 數(shù)據(jù)結(jié)構(gòu)
　習(xí)題
　參考文獻(xiàn)　
第二章 二維凸包
　2.1 凸包的定義
　2.2 極端點(diǎn)和極端邊
　2.3 禮品包裹算法
　2.4 凸包的快速算法
　2.5 Graham算法
　2.5.1 基于堆棧的初步算法
　2.5.2 算法實(shí)現(xiàn)細(xì)節(jié)的討論
　2.5.3 改進(jìn)的Graham算法
　2.6 下限
　2.7 增量算法
　2.8 分而治之算法
　2.8.1 算法描述
　2.8.2 算法分析
　習(xí)題
　參考文獻(xiàn)　
第三章 凸包擴(kuò)展
　3.1 多面體
　3.1.1 引言
　3.1.2 正則多面體
　3.1.3 多面體的歐拉公式
　3.2 三維凸包算法
　3.2.1 禮品包裹算法
　3.2.2 分而治之算法
　3.2.3 增量算法
　3.3 簡單多邊形的凸包計算
　3.3.1 計算簡單多邊形凸包的局部凸算法
　3.3.2 簡單多邊形凸包計算的“陷阱”算法
　3.3.3 簡單多邊形凸包的Melkman算法
　3.4 凸包的近似算法
　3.4.1 凸包的近似算法
　3.4.2 二維凸包近似算法精度的討論及其在三維擴(kuò)展
　3.4.3 近似凸包算法的應(yīng)用
　3.5 點(diǎn)集的Maxima
　3.6 a-shapes
　3.7 點(diǎn)集的相關(guān)幾何圖結(jié)構(gòu)
　習(xí)題
　參考文獻(xiàn)　
第四章 Voronoi圖
　4.1 基本概念
　4.2 半平面
　4.3 Voronoi圖的基本性質(zhì)
　4.4 Voronoi圖的構(gòu)造方法
　4.4.1 增量法
　4.4.2 分而治之法
　4.4.3 掃描線法
　習(xí)題
　參考文獻(xiàn)　
第五章 廣義Voronoi圖
　5.1 加權(quán)Voronoi圖
　5.1.1 能量圖
　5.1.2 加法加權(quán)Voronoi圖
　5.1.3 乘法加權(quán)Voronoi圖
　5.1.4 圓與球的Voronoi圖
　5.2 高階Voronoi圖
　5.2.1 基本概念
　5.2.2 基本性質(zhì)
　5.3 最遠(yuǎn)點(diǎn)Voronoi圖
　5.3.1 基本概念
　5.3.2 基本性質(zhì)
第六章 點(diǎn)集的Delaunay三角剖分
第七章 多邊形剖分
第八章 幾何搜索
第九章 相交計算
第十一章 可見多邊形與可見圖
第十二章 機(jī)器人運(yùn)動規(guī)劃
第十三章 隨機(jī)算法第十章 排列
第十四章 并行計算幾何
第十五章 計算幾何研究和應(yīng)用舉例
　　

章節(jié)摘錄

　　從多邊形的定義可知（見第一章）一個多邊形只有一條邊界。在本章中，我們稱之為單邊界多邊形。另外，我們將由多條簡單的、封閉的、不相交的曲線圍成的平面區(qū)域稱為多邊界多邊形。這些曲線都是它的邊界。一個多邊界多邊形有多個邊界?！　≡诒菊轮?，我們研究兩種類型的多邊界多邊形：　　1）第一類多邊界多邊形是一些分離的單邊界多邊形的集合被另一個單邊界多邊形所包圍，這一個最外面的邊界，稱之為外邊界，其他的單邊界多邊形都在它的內(nèi)部，我們稱之為內(nèi)邊界。根據(jù)單邊界多邊形的定義，這些多邊形內(nèi)部不存在任何多邊形。內(nèi)邊界和外邊界之間的部分是我們感興趣的部分，被稱為多邊形的關(guān)注區(qū)域，也是要繪制Voronoi圖的區(qū)域?！　∵@類多邊界多邊形在機(jī)械加工中被稱為pocket[6]　?。╝）中實(shí)線部分。在數(shù)學(xué)上被稱為多連通多邊形。　　2）第二類多邊界多邊形可以想象成第一類多邊界多邊形外邊界被不斷放大并移向無窮，在平面上留下若干個分離的單邊界多邊形的集合[圖5.2 1（b）中實(shí)線部分]。這些多邊形的外部并延伸至無限的部分則是我們感興趣的部分，被稱為多邊形的關(guān)注區(qū)域，也是要繪制Voronoi圖的區(qū)域?！　∠鄳?yīng)的，對于多邊界多邊形的Voronoi圖也分為兩類：　　1）對于第一類多邊界多邊形，其Voronoi圖位于外邊界的內(nèi)部和所有內(nèi)邊界的外部，并將這部分平面區(qū)域分割成許多單元。我們將這類多邊界多邊形的Voronoi圖稱為第一類Voronoi圖。　　2）對第二類多邊界多邊形，其Voronoi圖位于所有邊界的外部，并將這部分平面區(qū)域分割成許多單元。我們將這類多邊界多邊形的Voronoi圖稱為第二類Voronoi圖?！　D5.2 1（a）給出了第一類多邊界多邊形（實(shí)線部分）和它的Voronoi圖（虛線部分），圖5.2 1（b）中給出了第二類多邊界多邊形（實(shí)線部分）和它的Voronoi圖（虛線部分）。 　　……

編輯推薦

　　《計算幾何及應(yīng)用》可作為高等院校計算機(jī)及應(yīng)用數(shù)學(xué)等學(xué)科的本科生、研究生學(xué)習(xí)計算幾何的教材，也可作為從事計算幾何研究或應(yīng)用的其他科技工作者的參考用書。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    計算幾何及應(yīng)用 PDF格式下載

---