計算幾何——算法設計與分析（第二版）

內容簡介

本書系統地介紹了計算幾何中的基本概念、求解諸多問題的算法及複雜性分析，概括了求解幾何問題所特有的許多思想方法、幾何結構與數據結構。全書共分11章，包括: 預備知識、幾何查找、多邊形、凸殼及其套用、Voronoi圖與三角剖分及其套用、交與並及其套用、矩形幾何、幾何體的排列、算法的運動規劃、幾何拓撲網路設計、隨機幾何算法與並行幾何算法等。

本書可作為高等院校計算機專業研究生或本科高年級學生的教材,也可作為相關專業科技工作者的參考書。

圖書目錄

第2版前言Ⅴ第1版前言Ⅶ

第0章預備知識1

0.1算法與數據結構2

0.1.1算法2

0.1.2數據結構5

0.2相關的幾何知識9

0.2.1基本定義9

0.2.2線性變換群下的不變數11

0.2.3幾何對偶性12

0.3計算模型13

第1章幾何查找(檢索)17

1.1點定位問題18

1.1.1點q是否在多邊形P內19

1.1.2確定點q在平面剖分中的位置24

1.1.3Z1\|3算法30

1.2範圍查找問題31

1.2.1多維二叉樹(kD樹)的方法32

1.2.2直接存取方法34[]目錄[][3][][][2][]計算幾何——算法設計與分析[] 1.2.3範圍樹方法36

1.3判定點集是否在多邊形內37

1.4平面網路的處理與點q的定位39

第2章多邊形43

2.1凸多邊形43

2.2簡單多邊形49

2.3多邊形的三角剖分54

2.4多邊形的凸劃分58

2.5連線不相交線段成簡單多邊形(鏈)66

2.6下料問題71

2.7紅外圖像邊緣提取79

2.8滿足特定條件的多邊形劃分84

2.9多邊形與多邊形鏈87

2.10圓弧、直線段組成的多邊形頂點凸、凹性的確定90

2.11多邊形放大、縮小及移動91

2.12帶狀多邊形的處理93

第3章凸殼及其套用96

3.1凸殼的基本概念96

3.2計算平麵點集凸殼的算法100

3.2.1卷包裹法100

3.2.2格雷厄姆方法101

3.2.3分治算法102

3.2.4Z3\|1算法與Z3\|2算法104

3.2.5實時凸殼算法107

3.2.6增量算法111 ...

計算幾何——算法設計與分析（第二版）

基本介紹

內容簡介

圖書目錄

熱門詞條