內容簡介
《地理信息係統算法基礎》全麵、係統地收集和整理瞭當前地理信息係統算法領域的相關資料,以地理信息係統設計與實現為綫索,內容涉及地理空間數據的描述、檢索、存儲和管理,以及地理空間信息分析基本方法的設計和實現。
《地理信息係統算法基礎》可作為地理信息係統專業的本科生和研究生教材,也可作為從事地理信息係統軟件開發和應用的人員的學習資料,並可供地理信息係統的理論研究人員參考。
內頁插圖
目錄
序
前言
第1章 算法設計和分析
1.1 概述
1.2 算法設計原則
1.3 算法復雜性的度量
1.3.1 時間復雜性
1.3.2 空間復雜性
1.4 最優算法
1.5 算法的評價
1.5.1 如何估計算法運行時間
1.5.2 最壞情況和平均情況的分析
1.5.3 平攤分析
1.5.4 輸入大小和問題實例
思考題
第2章 GIS算法的計算幾何基礎
2.1 維數擴展的9交集模型
2.1.1 概述
2.1.2 模型介紹
2.1.3 空間關係的判定
2.2 矢量的概念
2.2.1 矢量加減法
2.2.2 矢量叉積
2.3 摺綫段的拐嚮判斷
2.4 判斷點是否在綫段上
2.5 判斷兩綫段是否相交
2.6 判斷矩形是否包含點
2.7 判斷綫段、摺綫、多邊形是否在矩形中
2.8 判斷矩形是否在矩形中
2.9 判斷圓是否在矩形中
2.10 判斷點是否在多邊形內
2.10.1 射綫法
2.10.2 轉角法
2.11 判斷綫段是否在多邊形內
2.12 判斷摺綫是否在多邊形內
2.13 判斷多邊形是否在多邊形內
2.14 判斷矩形是否在多邊形內
2.15 判斷圓是否在多邊形內
2.16 判斷點是否在圓內
2.17 判斷綫段、摺綫、矩形、多邊形是否在圓內
2.18 判斷圓是否在圓內
2.19 計算兩條共綫的綫段的交點
2.20 計算綫段或直綫與綫段的交點
2.21 求綫段或直綫與圓的交點
2.22 中心點的計算
2.23 過點作垂綫
2.24 作平行綫
2.25 過點作平行綫
2.26 綫段延長
2.27 三點畫圓
2.28 綫段打斷
2.29 前方交會
2.30 距離交會
2.31 極坐標作點
思考題
第3章 空間數據的變換算法
3.1 平麵坐標變換
3.1.1 平麵直角坐標係的建立
3.1.2 平麵坐標變換矩陣
3.1.3 平移變換
3.1.4 比例變換
3.1.5 對稱變換
3.1.6 鏇轉變換
3.1.7 錯切變換
3.1.8 復閤變換
3.1.9 相對(xf,yf)點的比例變換
3.1.10 相對(xf,yf)點的鏇轉變換
3.1.11 幾點說明
3.2 球麵坐標變換
3.2.1 球麵坐標係的建立
3.2.2 確定新極Q地理坐標中φ0、λ0
3.3 仿射變換
3.4 地圖投影變換
3.4.1 概述
3.4.2 地球橢球體的相關公式
3.4.3 蘭勃特投影
3.4.4 墨卡托投影
3.4.5 高斯-剋呂格投影
3.4.6 通用橫軸墨卡托投影
思考題
第4章 空間數據轉換算法
4.1 矢量數據嚮柵格數據轉換
4.1.1 矢量點的柵格化
4.1.2 矢量綫的柵格化
4.1.3 矢量麵的柵格化
4.2 柵格數據嚮矢量數據轉換
4.2.1 柵格點坐標與矢量點坐標的關係
4.2.2 柵格數據矢量化的基本步驟
4.2.3 綫狀柵格數據的細化
4.2.4 多邊形柵格轉矢量的雙邊界搜索算法
4.2.5 多邊形柵格轉矢量的單邊界搜索算法
思考題
第5章 空間數據組織算法
5.1 矢量數據的壓縮
5.1.1 間隔取點法
5.1.2 垂距法和偏角法
5.1.3 道格拉斯-普剋法
5.1.4 光欄法
5.1.5 麯綫壓縮算法的比較
5.1.6 麵域的數據壓縮算法
5.2 柵格數據的壓縮
5.2.1 鏈式編碼
5.2.2 遊程長度編碼
5.2.3 塊式編碼
5.2.4 差分映射法
5.2.5 四叉樹編碼
5.3 拓撲關係的生成
5.3.1 基本數據結構
5.3.2 弧段的預處理
5.3.3 結點匹配算法
5.3.4 建立拓撲關係
思考題
第6章 空間度量算法
6.1 直綫和距離
6.1.1 直綫
6.1.2 直綫方程
6.1.3 點到直綫的距離
6.2 角度量算
6.3 多邊形麵積的量算
6.3.1 三角形麵積量算
6.3.2 四邊形麵積量算
6.3.3 任意二維平麵多邊形麵積量算
6.3.4 任意三維平麵多邊形麵積量算
思考題
第7章 空間數據索引算法
7.1 B樹與B+樹
7.1.1 B樹索引結構
7.1.2 B+樹索引結構
7.2 R樹結構
7.2.1 R樹定義
7.2.2 R樹索引的主要操作算法
7.2.3 R*樹算法
7.3 四叉樹結構
7.3.1 常規四叉樹
7.3.2 綫性四叉樹
7.3.3 綫性四叉樹的編碼
7.3.4 Z麯綫和Hiben麯綫算法
思考題
第8章 空間數據內插算法
8.1 概述
8.1.1 幾何方法
8.1.2 統計方法
8.1.3 空間統計方法
8.1.4 函數方法
8.1.5 隨機模擬方法
8.1.6 確定性模擬
8.1.7 綜閤方法
8.2 分段圓弧法
8.3 分段三次多項式插值法
8.3.1 三點法
8.3.2 五點法
8.4 趨勢麵插值算法
8.5 反距離權重插值算法
8.6 雙綫性插值算法
8.7 薄闆樣條函數法
8.7.1 薄闆樣條函數法
8.7.2 規則樣條函數
8.7.3 薄闆張力樣條法
8.8 剋裏金法
8.8.1 普通剋裏金法
8.8.2 通用剋裏金法
思考題
第9章 Delaunay三角網與Voronoi圖算法
9.1 概述
9.2 VoronOi圖
9.3 Delaunay三角形
9.4 Voronoi圖生成算法
9.4.1 半平麵的交
9.4.2 增量構造方法
9.4.3 分治算法
9.4.4 減量算法
9.4.5 平麵掃描算法
思考題
第10章 緩衝區分析算法
10.1 概述
10.2 緩衝區邊界生成算法基礎
10.3 點緩衝區邊界生成算法
10.4 綫緩衝區邊界生成算法
10.5 麵緩衝區邊界生成算法
10.6 多目標緩衝區閤並算法
思考題
第11章 網絡分析算法
11.1 概述
11.2 網絡數據模型
11.3 路徑分析算法
11.3.1 單源點的最短路徑
11.3.2 單目標最短路徑問題
11.3.3 單結點對間最短路徑問題
11.3.4 多結點對間最短路徑問題
11.3.5 次短路徑求解算法
11.4 最佳路徑算法
11.4.1 最大可靠路徑
11.4.2 最大容量路徑
11.5 連通性分析算法
11.5.1 Prim算法
11.5.2 Kruskal算法
11.6 資源分配算法
思考題
第12章 地形分析算法
12.1 數字地麵模型的生成算法
12.1.1 基於離散點的DEM規則網格的生成
12.1.2 基於不規則三角網的DEM生成
12.1.3 DEM數據結構的相互轉換
12.2 基本地形因子分析算法
12.2.1 坡麵因子提取的算法基礎
12.2.2 坡度、坡嚮
12.2.3 坡形
12.3 地形特徵提取算法
12.3.1 地形特徵點的提取
12.3.2 基於規則格網DEM數據提取山脊與山榖綫的典型算法
12.4 通視分析算法
12.4.1 判斷兩點之間的可視性的算法
12.4.2 計算可視域的算法
思考題
第13章 空間數據挖掘算法
13.1 概述
13.2 分類算法
13.2.1 數據分類的基本過程
13.2.2 決策樹分類概述
13.2.3 決策樹的特點
13.2.4 二叉決策樹算法與分類規則的生成
13.2.5 決策樹分類算法
13.2.6 決策樹屬性的選取
13.2.7 改進決策樹性能的方法
13.3 泛化規則算法
13.3.1 概念層次
13.3.2 麵嚮屬性泛化的策略與特點
13.3.3 基於規則的麵嚮屬性泛化方法
13.4 相關分析
13.4.1 兩要素間的相關分析
13.4.2 多要素之間的相關分析
13.4.3 關聯規則算法
13.5 迴歸分析
13.5.1 一元綫性迴歸模型
13.5.2 多元綫性迴歸模型
13.5.3 非綫性迴歸模型
13.5.4 迴歸分析與相關分析
13.6 係統聚類分析
13.6.1 概述
13.6.2 聚類要素預處理
13.6.3 分類統計量
13.6.4 係統聚類法
13.6.5 其他聚類方法概述
13.7 判彆分析
13.7.1 距離判彆
13.7.2 費歇判彆法
13.7.3 貝葉斯判彆法
13.7.4 判彆分析應注意的問題
13.8 主成分分析
13.8.1 主成分分析的基本原理
13.8.2 主成分分析的方法
思考題
第14章 數據輸齣算法
14.1 概述
14.1.1 地圖符號構成元素組成
14.1.2 地圖符號幾何特徵
14.1.3 基於SVG的地圖符號描述模型
14.2 點狀地圖符號的繪製
14.2.1 圓的繪製
14.2.2 橢圓的繪製
14.2.3 多邊形的繪製
14.2.4 五角星的繪製
14.3 綫狀地圖符號的繪製
14.3.1 平行綫繪製
14.3.2 虛綫繪製
14.3.3 短齒綫的繪製
14.3.4 鐵路綫的繪製
14.3.5 境界綫的繪製
14.4 麵狀地圖符號的繪製
思考題
主要參考文獻
前言/序言
地理信息係統(GIS)自20世紀60年代問世以來,已曆經40多個春鞦。隨著計算機技術、通信技術的普及,GIS已經走齣實驗室,在各行業內得到瞭廣泛的應用並取得瞭良好的經濟效益和社會效益。越來越多的來自不同行業、不同專業的人士開始利用GIS技術解決生産和社會實踐中的問題。
本書旨在對GIS基礎軟件、應用軟件,以及GIS應用過程中涉及的基本的GIS算法及其應用做一較為全麵係統的介紹和分析。“算法”一詞源於公元9世紀波斯數學傢比阿勒·霍瓦裏鬆的一本影響深遠的著作《代數對話錄》。英國數學傢圖靈在20世紀提齣瞭著名的圖靈論點,並抽象齣瞭一颱機器,這颱機器被我們稱為圖靈機。圖靈的思想對算法的發展起到瞭重要的作用。算法是指完成一個任務所需要的具體步驟和方法。完成同樣任務,不同的算法可能使用不同的時間和空間。算法是計算機處理信息的本質,因為計算機程序本質上是一個算法,告訴計算機確切的步驟來執行一個指定的任務。一般地,當算法在處理信息時,數據會從輸入設備讀取,寫入輸齣設備,可能保存起來以供後期使用。隨著地理信息係統在各個領域中更為廣泛的應用,對GIS算法的研究變得日益重要。GIS算法作為處理地理科學領域中各種問題的分析求解方法,有著鮮明的特點。首先,GIS算法是用來解決地學領域中的問題,但許多算法都不是孤立的,不是無源之水,無本之木,而是藉鑒和發展瞭其他學科的研究成果;其次,GIS算法處理的往往是海量的地理信息,涉及許多復雜的空間運算,不同於簡單的數據查詢、編輯操作;再次,地理信息係統與實際應用、工程開發有著密切的關係,GIS算法與一般算法很重要的一個區彆就是要處理問題的不確定性,它無法被定性、定量成一個非常明確的純算法問題。例如,標注一條河流,標注必須靠近河流但是不能與其相交,標注的走嚮與河流一緻但又不能覆蓋地圖上的其他要素,標注必須間隔一緻但又不允許太大也不能太小等,不一而足。本書將更多地從計算機算法的角度來闡述GIS算法的設計原則、分析方法、技巧以及相關的評價。
GIS與各類學科都有密切的聯係,GIS算法與地理科學、計算機科學、數學等同樣有著韆絲萬縷的關係。GIS的許多算法都是從計算幾何、計算圖形學、離散數學演化而來的。它是整個地理信息科學的核心,不管是從基本的GIS空間數據結構到空間數據模型,還是從必需的GIS空間關係的錶達與描述到各種各樣的空間拓撲關係,抑或是從高級的時態多維GIS到GIS空間數據挖掘與知識發現.GIS算法作為地理信息係統的基石當之無愧。GIS算法是一個富集優雅技術和復雜數學分析結果的領域,一個好的算法或數據結構可能使某個原來需要數月纔能完成的問題在頃刻之間得到解決。在實際的應用中,往往需要考慮各方麵的因素,可能需要利用時間來換取空間,也有可能必須犧牲效率來獲得最佳的存儲性能,換句話來說,即可能沒有放之四海而皆準的最優算法。因此掌握GIS算法的設計原則,剖析各種GIS分析方法,靈活應用一些技巧自有其用武之地。
地理信息係統算法基礎 epub pdf mobi txt 電子書 下載 2024
地理信息係統算法基礎 下載 epub mobi pdf txt 電子書