面對棘手的構造性幾何問題，怎麼辦？
從本書中可以找到有效方法，幫助你排憂解難！
《計算幾何--算法設計與分析(第4版)》(作者周培德)繫統地介紹了計算幾何中的基本概念、求解諸多問題的算法及復雜性分析，概括了求解幾何問題所特有的許多思想方法、幾何結構與數據結構。

《計算幾何--算法設計與分析(第4版)》(作者周培德)繫統地介紹了計 算幾何中的基本概念、求解諸多問題的算法及復雜性分析，概括了求解幾何 問題所特有的許多思想方法、幾何結構與數據結構。全書共分10章，包括： 預備知識，幾何查找(檢索)，多邊形，凸殼及其應用，Voronoi圖、三角剖 分及其應用，交與並及其應用，多邊形的獲取及相關問題，幾何體的劃分與 等分，路徑與回路，幾何拓撲網絡設計等。 《計算幾何--算法設計與分析(第4版)》可作為高等院校計算機、自動 化等專業研究生或本科高年級學生的教材或教學參考書，也可供軟件開發人 員、相關專業科技工作者參考。

第0章 預備知識
0．1 算法與數據結構
0．1．1 算法
0．1．2 數據結構
0．2 相關的幾何知識
0．2．1 基本定義
0．2．2 線性變換群下的不變量
0．2．3 幾何對偶性
0．3 計算模型
第1章 幾何查找(檢索)
1．1 點定位問題
1．1．1 點□是否在多邊形P內
1．1．2 確定點□在平面剖分中的位置
1．1．3 Z□算法(判定點q在哪個三角形的算法)
1．2 判定點集是否在多邊形內
1．3 平面網絡的處理與點q的定位
1．4 平面上鏈的處理與點q的定位
1．5 平面上線段的處理與點q的定位
1．6 判定點是否在多邊形內部的新算法
第2章 多邊形
2．1 凸多邊形
2．2 簡單多邊形
2．3 多邊形的三角剖分
2．4 多邊形的凸劃分
2．5 對多邊形鏈的監視
2．6 線段劃分多邊形
2．7 凸多邊形的內接*大三角形及外切*小三角形
第3章 凸殼及其應用
3．1 凸殼的基本概念
3．2 計算平面點集凸殼的算法
3．3 計算平面多邊形頂點凸殼的算法
3．4 計算平面多邊形鏈頂點凸殼的算法
3．4．1 概念、算法思想與描述
3．4．2 解釋與時間復雜性
3．5 計算平面線段集凸殼的算法
3．6 計算三維空間點集凸殼的算法
3．6．1 基本概念
3．6．2 Z粥算法(三維凸殼)
3．7 時間復雜性低於下界O(nlogn)的凸殼算法
3．8 凸殼的應用
3．8．1 確定任意多邊形的凸、凹頂點
3．8．2 利用凸殼求解貨郎擔問題
3．8．3 凸多邊形直徑
3．8．4 連接兩個多邊形成一條回路
第4章 Voronoi圖、三角剖分及其應用
4．1 Voronoi圖的基本概念
4．2 構造Voronoi圖的算法
4．2．1 z□算法(計算平面點集的Voronoi圖)
4．2．2 構造*遠點意義下Voronoi圖的算法
4．3 平面點集的三角剖分
4．3．1 Delaunay三角剖分與多邊形內部點集的三角剖分
4．3．2 平面點集三角剖分的算法
4．4 平面線段集的三角剖分
4．5 平面點線集的三角剖分
4．6 平面點集的偽三角剖分
4．7 偽三角形的產生
4．8 三角剖分的表示
4．9 推廣及應用
4．9．1 *近鄰近
4．9．2 *大化*小角的三角剖分
4．9．3 *大空圓
4．9．4 *小生成樹
4．9．5 貨郎擔問題
4．9．6 中軸
4．9．7 Voronoi圖與凸殼的關繫
4．9．8 Voronoi圖的推廣
4．9．9 有約束的Voronoi圖
4．9．10 線段集的Voronoi圖
4．9．11 關聯於多邊形的Voronoi圖
4．9．12 點線集的Voronoi圖
4．9．13 點、水平、垂直正交線段集的Voronoi圖
4．9．14 幾何數據壓縮
4．9．15 車輛定位導航繫統的新定位算法
4．9．16 調色
4．9．17 點集增(刪)點之後的三角剖分
第5章 交與並及其應用
5．1 線段交的算法
5．2 多邊形的交
5．2．1 凸多邊形交的算法
5．2．2 星形多邊形交的算法
5．2．3 任意簡單多邊形交的算法
5．3 半平面的交及其應用
5．3．1 半平面的交
5．3．2 兩個變量的線性規劃
5．4 多邊形的並
5．5 凸多面體的交
5．6 應用
5．6．1 地圖匹配
5．6．2 地圖數據的處理
5．6．3 線段與凸多面體面的交
5．6．4 與線段集中線段均相交的直線及其存在區域
5．6．5 特定射線詢問
第6章 多邊形的獲取及相關問題
6．1 連接不相交線段成簡單多邊形(鏈)
6．2 紅外圖像邊緣提取
6．3 提取可見光圖像的邊緣
6．4 圖像邊界點行排列轉換為順序排列
6．5 數字圖像中目標邊界的多邊形表示
6．6 包含密集點、線集多邊形的獲取
6．7 滿足特定條件的多邊形劃分
6．8 多邊形與多邊形鏈
6．9 圓弧、直線段組成的多邊形頂點凸、凹性的確定
6．10 多邊形放大、縮小及移動
6．11 帶狀多邊形的處理
6．12 下料問題(1)
6．13 下料問題(2)
6．14 下料問題(3)
6．15 線鋸問題
6．16 多邊形(鏈)的匹配(1)
6．17 多邊形(鏈)的匹配(2)
6．18 構造凸多邊形
6．19 具有屬性點集的控制區域
6．20 多邊形內區域的劃分及多邊形(點集)中心點的確定
6．21 滿足一定條件的多邊形劃分
6．22 特定條件下凸多邊形的縮小與放大
第7章 幾何體的劃分與等分
7．1 平面上不同類型點集的劃分
7．2 多邊形內不同類型點集的等分
7．3 平面上不同類型線段集的劃分
7．4 平面上不同類型線段集的等分
7．5 平面上不同類型點線集的劃分與等分
7．6 鏈、多邊形的劃分與等分
第8章 路徑與回路
8．1 *短路徑
8．1．1 可視圖及其構造
8．1．2 Z□算法(尋求網絡中任意兩點間*短路徑的算法
8．1．3 多面體面上任意兩點之間的*短路徑
8．1．4 貨運汽車調度及行駛路徑問題
8．2 *短路徑問題的變型
8．3 滿足一定條件的運動規劃
8．4 多邊形內點之間的可視圖
8．5 多邊形內任意兩點之間的*短路徑
8．6 自主車自動定位及確定行車方向
8．7 迷宮問題
8．8 棋盤上的路徑與回路
8．9 選擇道路及判定道路的通過能力
8．10 多邊形內中心區域的確定
第9章 幾何拓撲網絡設計
9．1 G(S)問題
9．1．1 *大間隙問題(MAX G)
9．1．2 點集中*大空凸多邊形問題及*大空矩形問題
9．1．3 線段集中*大空凸多邊形問題
9．1．4 點線集中*大空凸多邊形問題
9．1．5 *小覆蓋問題(MIN C)
9．1．6 包含平面點集的*小正方形
9．1．7 子點集包含問題
9．1．8 2-中心問題
9．1．9 k-中心問題
9．1．10 *近對問題(CPP)
9．1．11 所有*近鄰近問題(ANNP)
9．1．12 郵局問題(POFP)
9．1．13 尋找具有屬性點集的*近點對或點團
9．2 G(E)問題
9．2．1 EMST問題
9．2．2 線段集、點線集的*小生成樹
9．2．3 直線*小生成樹及其相關問題
9．2．4 歐幾裡得TSP
9．2．5 歐幾裡得*大生成樹問題(EMXT)
9．2．6 *小生成網絡
9．3 G(S，E)問題
9．3．1 歐幾裡得Steiner*小樹問題(ESMT)
9．3．2 直線Steiner*小樹問題(RSMT)
9．3．3 求解ESMT問題的算法
9．4 G(□)問題
9．4．1 有障礙物的*大空隙問題(MAX G(□))
9．4．2 多邊形集中*大空隙問題
9．4．3 具有障礙物的歐幾裡得*短路徑問題(ESPO)
9．4．4 求解E3中ESPO問題的算法
9．4．5 具有障礙物的Steiner*小樹問題(ESMTO)
待解決的問題
算法一覽
參考文獻
名詞索引