目錄
序
前言
第1章 算法設(shè)計(jì)和分析 （1）
1.1 概述 （1）
1.2 算法設(shè)計(jì)原則 （1）
1.3 算法復(fù)雜性的度量 （2）
1.3.1 時(shí)間復(fù)雜性 （2）
1.3.2 空間復(fù)雜性 （8）
1.4 最優(yōu)算法 （8）
1.5 算法的評(píng)價(jià) （9）
1.5.1 如何估計(jì)算法運(yùn)行時(shí)間 （9）
1.5.2 最壞情況和平均情況的分析 （11）
1.5.3 平攤分析 （13）
1.5.4 輸人大小和問(wèn)題實(shí)例 （13）
思考題 （14）
第2章 GIS算法的計(jì)算幾何基礎(chǔ) （15）
2.1 維數(shù)擴(kuò)展的9交集模型 （15）
2.1.1 概述 （15）
2.1.2 模型介紹 （15）
2.1.3 空間關(guān)系的判定 （17）
2.2 矢量的概念 （21）
2.2.1 矢量加減法 （21）
2.2.2 矢量叉積 （22）
2.3 折線段的拐向判斷 （22）
2.4 判斷點(diǎn)是否在線段上 （23）
2.5 判斷兩線段是否相交 （23）
2.6 判斷矩形是否包含點(diǎn) （25）
2.7 判斷線段、折線、多邊形是否在矩形中 （25）
2.8 判斷矩形是否在矩形中 （25）
2.9 判斷圓是否在矩形中 （25）
2.10 判斷點(diǎn)是否在多邊形內(nèi) （25）
2.10.1 射線法 （26）
2.10.2 轉(zhuǎn)角法 （28）
2.11 判斷線段是否在多邊形內(nèi) （30）
2.12 判斷折線是否在多邊形內(nèi) （32）
2.13 判斷多邊形是否在多邊形內(nèi) （32）
2.14 判斷矩形是否在多邊形內(nèi) （33）
2.15 判斷圓是否在多邊形內(nèi) （33）
2.16 判斷點(diǎn)是否在圓內(nèi) （33）
2.17 判斷線段、折線、矩形、多邊形是否在圓內(nèi) （33）
2.18 判斷圓是否在圓內(nèi) （33）
2.19 計(jì)算兩條共線的線段的交點(diǎn) （33）
2.20 計(jì)算線段或直線與線段的交點(diǎn) （34）
2.21 求線段或直線與圓的交點(diǎn) （35）
2.22 中心點(diǎn)的計(jì)算 （36）
2.23 過(guò)點(diǎn)作垂線 （37）
2.24 作平行線 （37）
2.25 過(guò)點(diǎn)作平行線 （38）
2.26 線段延長(zhǎng) （38）
2.27 三點(diǎn)畫圓 （39）
2.28 線段打斷 （39）
2.29 前方交會(huì) （40）
2.30 距離交會(huì) （41）
2.31 極坐標(biāo)作點(diǎn) （43）
思考題 （44）
第3章 空間數(shù)據(jù)的變換算法 （45）
3.1 平面坐標(biāo)變換 （45）
3.1.1 平面直角坐標(biāo)系的建立 （45）
3.1.2 平面坐標(biāo)變換矩陣 （45）
3.1.3 平移變換 （46）
3.1.4 比例變換 （47）
3.1.5 對(duì)稱變換 （47）
3.1.6 旋轉(zhuǎn)變換 （47）
3.1.7 錯(cuò)切變換 （48）
3.1.8 復(fù)合變換 （48）
3.1.9 棚對(duì)（xf，yf）點(diǎn)的比例變換 （49）
3.1.10 相對(duì)（zf，yf）點(diǎn)的旋轉(zhuǎn)變換 （49）
3.1.11 幾點(diǎn)說(shuō)明 （50）
3.2 球面坐標(biāo)變換 （50）
3.2.1 球面坐標(biāo)系的建立 （50）
3.2.2 確定新極Q地理坐標(biāo)中*、λ0 （51）
3.3 仿射變換 （54）
3.4 地圖投影變換 （55）
3.4.1 概述 （55）
3.4.2 地球橢球體的相關(guān)公式 （57）
3.4.3 蘭勃特投影 （62）
3.4.4 墨卡托投影 （64）
3.4.5 高斯克呂格投影 （65）
3.4.6 通用橫軸墨卡托投影 （68）
思考題 （69）
第4章 空間數(shù)據(jù)轉(zhuǎn)換算法 （70）
4.1 矢量數(shù)據(jù)向柵格數(shù)據(jù)轉(zhuǎn)換 （70）
4.1.1 矢量點(diǎn)的柵格化 （70）
4.1.2 矢量線的柵格化 （71）
4.1.3 矢量面的柵格化 （73）
4.2 柵格數(shù)據(jù)向矢量數(shù)據(jù)轉(zhuǎn)換 （77）
4.2.1 柵格點(diǎn)坐標(biāo)與矢量點(diǎn)坐標(biāo)的關(guān)系 （77）
4.2.2 柵格數(shù)據(jù)矢量化的基本步驟 （78）
4.2.3 線狀柵格數(shù)據(jù)的細(xì)化 （78）
4.2.4 多邊形柵格轉(zhuǎn)矢量的雙邊界搜索算法 （84）
4.2.5 多邊形柵格轉(zhuǎn)矢量的單邊界搜索算法 （86）
思考題 （89）
第5章 空間數(shù)據(jù)組織算法 （90）
5.1 矢量數(shù)據(jù)的壓縮 （90）
5.1.1 間隔取點(diǎn)法 （90）
5.1.2 垂距法和偏角法 （90）
5.1.3 道格拉斯-普克法 （91）
5.1.4 光欄法 （93）
5.1.5 曲線壓縮算法的比較 （95）
5.1.6 面域的數(shù)據(jù)壓縮算法 （96）
5.2 柵格數(shù)據(jù)的壓縮 （98）
5.2.1 鏈?zhǔn)骄幋a （98）
5.2.2 游程長(zhǎng)度編碼 （99）
5.2.3 塊式編碼 （101）
5.2.4 差分映射法 （101）
5.2.5 四叉樹(shù)編碼 （102）
5.3 拓?fù)潢P(guān)系的生成 （102）
5.3.1 基本數(shù)據(jù)結(jié)構(gòu) （103）
5.3.2 弧段的預(yù)處理 （106）
5.3.3 結(jié)點(diǎn)匹配算法 （112）
5.3.4 建立拓?fù)浠鹣?（114）
思考題 （117）
第6章 空間度量算法 （118）
6.1 直線和距離 （118）
6.1.1 直線 （118）
6.1.2 直線方程 （119）
6.1.3 點(diǎn)到直線的距離 （120）
6.2 角度量算 （125）
6.3 多邊形面積的量算 （125）
6.3.1 三角形面積量算 （125）
6.3.2 四邊形面積量算 （127）
6.3.3 任意二維平面多邊形面積量算 （129）
6.3.4 任意三維平面多邊形面積量算 （131）
思考題 （134）
第7章 空間數(shù)據(jù)索引算法 （135）
7.1 B樹(shù)與B+樹(shù) （135）
7.1.1 B樹(shù)索引結(jié)構(gòu) （136）
7.1.2 B+樹(shù)索引結(jié)構(gòu) （140）
7.2 R樹(shù)結(jié)構(gòu) （141）
7.2.1 R樹(shù)定義 （141）
7.2.2 R樹(shù)索引的主要操作算法 （142）
7.2.3 R*樹(shù)算法 （146）
7.3 四叉樹(shù)結(jié)構(gòu) （147）
7.3.1 常規(guī)四叉樹(shù) （147）
7.3.2 線性四叉樹(shù) （149）
7.3.3 線性四叉樹(shù)的編碼 （149）
7.3.4 Z曲線和Hibert曲線算法 （155）
思考題 （158）
第8章 空間數(shù)據(jù)內(nèi)插算法 （159）
8.1 概述 （159）
8.1.1 幾何方法 （159）
8.1.2 統(tǒng)計(jì)方法 （159）
8.1.3 空間統(tǒng)計(jì)方法 （160）
8.1.4 函數(shù)方法 （160）
8.1.5 隨機(jī)模擬方法 （160）
8.1.6 確定性模擬 （161）
8.1.7 綜合方法 （161）
8.2 分段圓弧法 （161）
8.3 分段j次多項(xiàng)式插值法 （162）
8.3.1 三點(diǎn)法 （162）
8.3.2 五點(diǎn)法 （162）
8.4 趨勢(shì)面插值算法 （163）
8.5 反距離權(quán)重插值算法 （166）
8.6 雙線性插值算法 （166）
8.7 薄板樣條函數(shù)法 （167）
8.7.1 薄板樣條函數(shù)法 （167）
8.7.2 規(guī)則樣條函數(shù) （168）
8.7.3 薄板張力樣條法 （168）
8.8 克里金法 （169）
8.8.1 普通克里金法 （169）
8.8.2 通用克里金法 （171）
思考題 （171）
第9章 Delaunay三角網(wǎng)與Voronoi圖算法 （172）
9.1 概述 （172）
9.2 Voronoi圖 （173）
9.3 Delaunay三角形 （174）
9.4 Voronoi圖生成算法 （174）
9.4.1 半平面的交 （174）
9.4.2 增量構(gòu)造方法 （175）
9.4.3 分治算法 （178）
9.4.4 減量算法 （180）
9.4.5 平面掃描算法 （182）
思考題 （184）
第10章 緩沖區(qū)分析算法 （185）
10.1 概述 （185）
10.2 緩沖區(qū)邊界生成算法基礎(chǔ) （185）
10.3 點(diǎn)緩沖區(qū)邊界生成算法 （187）
10.4 線緩沖區(qū)邊界生成算法 （188）
10.5 面緩沖區(qū)邊界生成算法 （195）
10.6 多目標(biāo)緩沖區(qū)合并算法 （195）
思考題 （200）
第11章 網(wǎng)絡(luò)分析算法 （201）
11.1 概述 （201）
11.2 網(wǎng)絡(luò)數(shù)據(jù)模型 （201）
11.3 路徑分析算法 （203）
11.3.1 單源點(diǎn)的最短路徑 （204）
11.3.2 單目標(biāo)最短路徑問(wèn)題 （208）
11.3.3 單結(jié)點(diǎn)對(duì)間最短路徑問(wèn)題 （208）
11.3.4 多結(jié)點(diǎn)對(duì)間最短路徑問(wèn)題 （209）
11.3.5 次短路徑求解算法 （209）
11.4 最佳路徑算法 （210）
11.4.1 最大可靠路徑 （210）
11.4.2 最大容量路徑 （211）
11.5 連通性分析算法 （212）
11.5.1 Prim算法 （212）
11.5.2 Kruskal算法 （214）
11.6 資源分配算法 （216）
思考題 （218）
第12章 地形分析算法 （219）
12.1 數(shù)字地面模型的生成算法 （219）
12.1.1 基于離散點(diǎn)的DEM規(guī)則網(wǎng)格的生成 （219）
12.1.2 基于不規(guī)則三角網(wǎng)的DEM生成 （221）
12.1.3 DEM數(shù)據(jù)結(jié)構(gòu)的相互轉(zhuǎn)換 （221）
12.2 基本地形因子分析算法 （235）
12.2.1 坡面因子提取的算法基礎(chǔ) （235）
12.2.2 坡度、坡向 （239）
12.2.3 坡形 （241）
12.3 地形特征提取算法 （244）
12.3.1 地形特征點(diǎn)的提取 （245）
12.3.2 基于規(guī)則格網(wǎng)DEM數(shù)據(jù)提取山脊與山谷線的典型算法 （246）
12.4 通視分析算法 （248）
12.4.1 判斷兩點(diǎn)之間的可視性的算法 （248）
12.4.2 計(jì)算可視域的算法 （248）
思考題 （249）
第13章 空間數(shù)據(jù)挖掘算法 （250）
13.1 概述 （250）
13.2 分類算法 （250）
13.2.1 數(shù)據(jù)分類的基本過(guò)程 （250）
13.2.2 決策樹(shù)分類概述 （251）
13.2.3 決策樹(shù)的特點(diǎn) （251）
13.2.4 二叉決策樹(shù)算法與分類規(guī)則的生成 （252）
13.2.5 決策樹(shù)分類算法 （253）
13.2.6 決策樹(shù)屬性的選取 （254）
13.2.7 改進(jìn)決策樹(shù)性能的方法 （255）
13.3 泛化規(guī)則算法 （256）
13.3.1 概念層次 （256）
13.3.2 面向?qū)傩苑夯�的策略與特點(diǎn) （258）
13.3.3 基于規(guī)則的面向?qū)傩苑夯�方�?（260）
13.4 相關(guān)分析 （263）
13.4.1 兩要素間的相關(guān)分析 （263）
13.4.2 多要素之間的相關(guān)分析 （265）
13.4.3 關(guān)聯(lián)規(guī)則算法 （267）
13.5 回歸分析 （274）
13.5.1 一元線性回歸模型 （274）
13.5.2 多元線性回歸模型 （277）
13.5.3 非線性回歸模型 （281）
13.5.4 回歸分析與相關(guān)分析 （282）
13.6 系統(tǒng)聚類分析 （283）
13.6.1 概述 （283）
13.6.2 聚類要素預(yù)處理 （283）
13.6.3 分類統(tǒng)計(jì)量 （284）
13.6.4 系統(tǒng)聚類法 （286）
13.6.5 其他聚類方法概述 （292）
13.7 判別分析 （293）
13.7.1 距離判別 （294）
13.7.2 費(fèi)歇判別法 （297）
13.7.3 貝葉斯判別法 （300）
13.7.4 判別分析應(yīng)注意的問(wèn)題 （302）
13.8 主成分分析 （303）
13.8.1 主成分分析的基本原理 （303）
13.8.2 主成分分析的方法 （304）
思考題 （306）
第14章 數(shù)據(jù)輸出算法 （308）
14.1 概述 （308）
14.1.1 地圖符號(hào)構(gòu)成元素組成 （308）
14.1.2 地圖符號(hào)幾何特征 （309）
14.1.3 基于SVG的地圖符號(hào)描述模型 （310）
14.2 點(diǎn)狀地圖符號(hào)的繪制 （312）
14.2.1 網(wǎng)的繪制 （312）
14.2.2 橢圓的繪制 （314）
14.2.3 多邊形的繪制 （314）
14.2.4 五角星的繪制 （316）
14.3 線狀地圖符號(hào)的繪制 （318）
14.3.1 平行線繪制 （319）
14.3.2 虛線繪制 （321）
14.3.3 短齒線的繪制 （322）
14.3.4 鐵路線的繪制 （324）
14.3.5 境界線的繪制 （326）
14.4 面狀地圖符號(hào)的繪制 （328）
思考題 （333）
主要參考文獻(xiàn) （334）