《GIS數據結構與算法基礎》是Stephen Wise撰寫的GIS Basics一書的翻譯版。內容涉及GIS的核心數據結構和核心算法，詳細介紹了各種矢量、柵格、索引、表面、網路相關的數據結構與算法。書中包含了大量所述數據結構與算法的偽代碼，同時每章末配有延伸閱讀，可幫助讀者對書中內容進行更深入地理解。
《GIS數據結構與算法基礎》可作為地理信息領域、計算機科學領域高等院校師生的專業基礎課程教材，也可作為相關技術人員的參考用書。
基本介紹
- 書名：GIS數據結構與算法基礎
- 類型：計算機與網際網路
- 出版日期：2012年2月1日
- 語種：簡體中文
- ISBN：9787030333094
- 作者：懷斯（Stephen Wise） 張雪英
- 出版社：科學出版社
- 頁數：158頁
- 開本：16
- 品牌：科學出版社
基本介紹,內容簡介,作者簡介,圖書目錄,
基本介紹
內容簡介
《GIS數據結構與算法基礎》編輯推薦：地理信息系統（GIS）是一種用於空間數據存儲、顯示和分析的計算機系統。20多年來，GIS不僅在政府、商業和學術中的套用快速增長，還可以套用於設施規劃的管理、普查數據的處理、新超市的選址等。
StephenWise是Geo Europe的定期撰稿人，他的系列連載文章《回到基礎》向非專業讀者簡明扼要地介紹了GIS的內部工作機制。在《GIS數據結構與算法基礎》中，他以新的材料重現了他的系列原創文章，內容涵蓋了GIS的兩大主要類型——矢量系統和柵格系統。
希望改善GIs知識結構的在校師生和專業人士，通過《GIS數據結構與算法基礎》能更深入地理解GIS內部的運作方式。例如，計算機是如何存儲空間數據的，不同的方法如何影響GIS的性能，基本操作是如何執行的，以及算法的選擇如何影響系統的運行速度。
Stephen Wise在倫敦和巴斯的大學計算中心做過多年的電腦程式員，從1990年他開始在The University of Sheffield地理系從事本科生和研究生的教學工作。他的研究興趣包括數字地面模型的誤差傳播、GIs中設施的空間分析和地圖掃描數據化。
StephenWise是Geo Europe的定期撰稿人，他的系列連載文章《回到基礎》向非專業讀者簡明扼要地介紹了GIS的內部工作機制。在《GIS數據結構與算法基礎》中，他以新的材料重現了他的系列原創文章，內容涵蓋了GIS的兩大主要類型——矢量系統和柵格系統。
希望改善GIs知識結構的在校師生和專業人士，通過《GIS數據結構與算法基礎》能更深入地理解GIS內部的運作方式。例如，計算機是如何存儲空間數據的，不同的方法如何影響GIS的性能，基本操作是如何執行的，以及算法的選擇如何影響系統的運行速度。
Stephen Wise在倫敦和巴斯的大學計算中心做過多年的電腦程式員，從1990年他開始在The University of Sheffield地理系從事本科生和研究生的教學工作。他的研究興趣包括數字地面模型的誤差傳播、GIs中設施的空間分析和地圖掃描數據化。
作者簡介
作者：(英國)懷斯(Stephen Wise) 譯者：朱定局 合著者：張雪英
朱定局，北京大學博士後，中國科學院計算技術研究所博士，中國科學院深圳先進技術研究院智慧計算與信息科學實驗室主任。曾任勝利油田地質科學研究院科研人員，美國Texas State University地理系訪問學者。
朱定局，北京大學博士後，中國科學院計算技術研究所博士，中國科學院深圳先進技術研究院智慧計算與信息科學實驗室主任。曾任勝利油田地質科學研究院科研人員，美國Texas State University地理系訪問學者。
圖書目錄
譯者的話
前言
致謝
第1章 引言
1.1 計算機如何解決問題
1.2 計算機如何存儲空間數據:矢量和柵格數據模型
1.3 本書結構
1.4 偽代碼
延伸閱讀
第2章 矢量數據結構
2.1 點和線的存儲
2.2 區域邊界的存儲
2.3 存儲區域的邊界:拓撲法
2.4 什麼是拓撲學
2.5 如何使用拓撲學？以DIME為例
延伸閱讀
第3章 線的矢量算法
3.1 簡單的線相交算法
3.2 為什麼簡單的直線相交算法無效:一個更好的算法
3.3 波形線的處理
3.4 有關直線上的計算:一條直線有多長
延伸閱讀
第4章 區域的矢量算法
4.1 有關區域的計算:單一多邊形
4.2 有關區域的計算:多重多邊形
4.3 多邊形的點:簡單算法
4.4 利用拓撲的好算法
延伸閱讀
第5章 算法效率
5.1 如何評估算法的有效性
5.2 直線相交算法的有效性
5.3 算法有效性的更多知識
延伸閱讀
第6章 柵格數據結構
6.1 柵格數據結構:數組
6.2 節省空間:行程長度編碼和四叉樹
延伸閱讀
第7章 柵格算法
7.1 柵格算法:對行程編碼數據的屬性查詢
7.2 柵格算法:四叉樹中的屬性查詢
7.3 柵格算法:面積計算
延伸閱讀
第8章 空間索引
8.1 二叉查找樹
8.2 使用k^d樹索引數據
8.3 採用四叉樹結構索引向量數據
8.4 採用莫頓排序索引柵格數據
延伸閱讀
第9章 表面數據結構
9.1 表面數據模型
9.2 創建格網表面模型的算法
9.3 產生不規則三角網的算法
9.4 格網劃分修正
延伸閱讀
第10章 表面算法
10.1 高度、坡度和坡向
10.2 用TIN做水文分析
10.3 用格網DEM決定流向
10.4 用流動方向做水文分析
延伸閱讀
第11章 網路的數據結構和算法
11.1 採用矢量和柵格模型中的網路
11.2 最短路徑算法
11.3 網路數據的數據結構
11.4 旅行商問題
延伸閱讀
結語
辭彙表
參考文獻
圖目錄
圖1.1 查茲沃斯莊園的迷宮
圖1.2 用左手規則通過迷宮的路線
圖1.3 簡單算法不能破解的迷宮
圖1.4 圖1.3的路徑簡圖
圖1.5 基於Worboys(1995)的數據建模步驟
圖1.6 虛構的地形圖
圖1.7 圖1.6中地圖的部分柵格版本
圖1.8 圖1.6中的地形圖矢量版本
圖2.1 虛構的地形圖
圖2.2 點的屬性數據
圖2.3 線的坐標數據
圖2.4 通過一系列直線段逼近一條曲線
圖2.5 線的屬性數據
圖2.6 將線的位置信息添加到屬性表格當中
圖2.7 將線的位置信息添加到屬性表格當中的替代方法
圖2.8 建築物的位置數據
圖2.9 建築物的屬性信息
圖2.10 路的修正後屬性表格
圖2.11 區域特徵的存儲
圖2.12 土地利用圖示例(多個區域)
圖2.13 土地利用圖的屬性信息
圖2.14 兩次數位化同一條直線時造成的多邊形碎片
圖2.15 通過多邊形消除操作產生的城市區與非城市區區域地圖
圖2.16 拓撲GIS中存儲的土地利用圖
圖2.17 一個連線和節點數據結構中存儲的連線信息
圖2.18 哥尼斯堡橋問題
圖2.19 哥尼斯堡橋問題的圖形
圖2.20 用來說明地圖的Poincaré雙重圖形模型的虛構城區
圖2.21 虛擬城市地圖的DIME數據結構
圖2.22 DIME檔案中與街區5有關的記錄
圖2.23 DIME檔案中與相交點5有關的記錄
圖2.24 修改DIME檔案中與交匯點5有關的記錄,使得街道的終點是交匯點5
圖2.25 DIME數據結構中地址信息的存儲
圖3.1 線的相交問題
圖3.2 兩條相交線段的相交檢測
圖3.3 線段的坐標值
圖3.4 線相交問題:每組線可以通過相同的數學方程來定義
圖3.5 垂直直線的相交問題
圖3.6 檢測直線的相交
圖3.7 直線的最小外接矩形
圖3.8 最小外接矩形角頂點的定義
圖3.9 單調線段
圖3.10 通過一系列直線段逼近曲線
圖3.11 利用勾股定理計算兩點之間的距離
圖4.1 單一多邊形
圖4.2 計算多邊形面積:上面線段以下的部分面積減去下面線段以下的面積
圖4.3 單一線段以下的面積計算
圖4.4 多邊形上部分和下部分線段以下部分的面積
圖4.5 使用連線和節點數據結構存儲兩個相鄰的多邊形
圖4.6 多邊形檢測中的點
圖4.7 點的MER在多邊形檢測中的套用
圖4.8 初始檢測選擇的X坐標線段
圖4.9 一個點直接位於多邊形邊界頂點下方的特殊情況
圖4.10 多個多邊形中的點檢測
圖4.11 平面強化規則的結果
圖4.12 檢測哪一個多邊形位於一個連線的下方
圖5.1 一些常用來說明算法複雜度的函式值
圖5.2 直線相交的例子
圖5.3 使用MER的直線相交檢測
圖5.4 例證為什麼n+nlogn+logn是O(nlogn)
圖5.5 n的三種函式圖
圖6.1 計算機記憶體中數組的存儲
圖6.2 簡單柵格數組的例子
圖6.3 計算機記憶體中數組的存儲
圖6.4 一個位元組整數存儲的例子
圖6.5 簡單柵格陣列例子
圖6.6 行程長度編碼圖層在計算機記憶體中的存儲
圖6.7 圖6.5中圖層的四叉樹劃分
圖6.8 記憶體中四叉樹的存儲
圖6.9 四叉樹的圖形表示
圖7.1 簡單柵格數組的例子
圖7.2 計算機記憶體中數組的存儲
圖7.3 在計算機記憶體中行程編碼的圖像的存儲
圖7.4 圖6.5給出的圖層的四叉樹劃分
圖7.5 四叉樹在記憶體中的存儲
圖7.6 柵格圖層例子
圖7.7 採用行程長度編碼形式存儲圖層
圖7.8 兩種獲得行程數的方法
圖7.9 線性四叉樹形式下圖層的存儲
圖7.10 柵格圖像(圖7.6)的四叉樹表示
圖8.1 折半查找法的運行
圖8.2 二叉查找樹
圖8.3 存儲為二叉鍊表的查找樹
圖8.4 沿一條單獨的線分布的十個點,二叉查找樹建立在這些點的X坐標的基礎上
圖8.5 k^d樹
圖8.6 自然保護區地圖的四叉樹劃分及其葉節點的莫頓地址
圖8.7 採用莫頓地址順序來存儲像素時的序列
圖8.8 顯示像素莫頓地址的柵格圖層
圖9.1 商鋪顧客位置採樣點
圖9.2 山脈高度採樣點
圖9.3 採用點數據來解決表面查詢操作的問題
圖9.4 格網模型中的規則格網與採樣點
圖9.5 表面數據的不規則三角網模型
圖9.6 基於等高線的表面數據模型
圖9.7 等高線及數字高度模型格網點的小山峰等高線圖
圖9.8 點插值中分配權重的兩個函式
圖9.9 指數衰減曲線中改變指數的效果
圖9.10 數位化等高線當中反距離權重函式的套用
圖9.11 採用反距離權重法生成等高線的格網化DEM
圖9.12 表明三角劃分算法的採樣點
圖9.13 分別經過五步和六步操作後得到的三角形
圖9.14 採樣點的Voronoi鑲嵌
圖9.15 四個採樣點的Delaunay三角劃分
圖9.16 產生Delaunay三角劃分過程中邊的變化情況
圖9.17 對一個Delaunay三角劃分添加一個點
圖9.18 不規則三角網如何對表面進行建模
圖9.19 不同階多項式的圖形
圖9.20 不同擬合方法產生的DEM格網
圖9.21 採用Delaunay三角劃分擬合的DEM格網
圖10.1 圖表z=ax
圖10.2 圖表z=ax+b
圖10.3 用於估算點表面特性的3×3視窗單元格位置
圖10.4 過三個點的線
圖10.5 用兩個不同的DEM估算的斜面朝向
圖10.6 水流通過一個虛構的代表河谷的TIN的一部分
圖10.7 細分水流穿過三角形E
圖10.8 在TIN上確定排水溝時出現的無限循環
圖10.9 虛構的DEM
圖10.10 DEM單元格中方向的編碼表示
圖10.11 水流的十進制和二進制代碼
圖10.12 代表從各個鄰居流動到某個單元格的編碼
圖10.13 將2存儲到8bit位元組
圖10.14 虛構的DEM中的流動方向
圖10.15 三次重複運算的集水區
圖10.16 DEM的高度及流動方向與流量聚集值
圖11.1 虛擬道路網路
圖11.2 簡單的網路
圖11.3 圖11.2添加一些額外的連結以後的網路
圖11.4 二次增加和指數增加的對比
圖11.5 標識連線的簡單網路
圖11.6 簡單網路的連線和節點表示
圖11.7 網路的節點表
圖11.8 採用分開的節點和連線表來存儲網路信息
圖11.9 堆
圖11.10 交換節點2和節點4以後的堆
圖11.11 圖11.9中的二叉堆在一個數組當中的存儲
圖11.12 交換節點4和節點9以後的堆
圖11.13 去掉根節點以後的堆
圖11.14 圖11.13經過兩次交換以後的堆
圖11.15 針對四個點的TSP解答和MST解答
圖11.16 為什麼MST不能形成一個TSP最優解的證明
圖11.17 TSP道路網路
圖11.18 每個點僅遍歷一次的網路路徑
圖11.19 根據選定的3個點由增量啟發法形成的路徑
圖11.20 根據選定的5個點由增量啟發法形成的路徑
圖11.21 連線所有最外圍的點形成的路徑
圖11.22 對圖11.21所示的外層路徑添加所有的點以後形成的路徑
前言
致謝
第1章 引言
1.1 計算機如何解決問題
1.2 計算機如何存儲空間數據:矢量和柵格數據模型
1.3 本書結構
1.4 偽代碼
延伸閱讀
第2章 矢量數據結構
2.1 點和線的存儲
2.2 區域邊界的存儲
2.3 存儲區域的邊界:拓撲法
2.4 什麼是拓撲學
2.5 如何使用拓撲學？以DIME為例
延伸閱讀
第3章 線的矢量算法
3.1 簡單的線相交算法
3.2 為什麼簡單的直線相交算法無效:一個更好的算法
3.3 波形線的處理
3.4 有關直線上的計算:一條直線有多長
延伸閱讀
第4章 區域的矢量算法
4.1 有關區域的計算:單一多邊形
4.2 有關區域的計算:多重多邊形
4.3 多邊形的點:簡單算法
4.4 利用拓撲的好算法
延伸閱讀
第5章 算法效率
5.1 如何評估算法的有效性
5.2 直線相交算法的有效性
5.3 算法有效性的更多知識
延伸閱讀
第6章 柵格數據結構
6.1 柵格數據結構:數組
6.2 節省空間:行程長度編碼和四叉樹
延伸閱讀
第7章 柵格算法
7.1 柵格算法:對行程編碼數據的屬性查詢
7.2 柵格算法:四叉樹中的屬性查詢
7.3 柵格算法:面積計算
延伸閱讀
第8章 空間索引
8.1 二叉查找樹
8.2 使用k^d樹索引數據
8.3 採用四叉樹結構索引向量數據
8.4 採用莫頓排序索引柵格數據
延伸閱讀
第9章 表面數據結構
9.1 表面數據模型
9.2 創建格網表面模型的算法
9.3 產生不規則三角網的算法
9.4 格網劃分修正
延伸閱讀
第10章 表面算法
10.1 高度、坡度和坡向
10.2 用TIN做水文分析
10.3 用格網DEM決定流向
10.4 用流動方向做水文分析
延伸閱讀
第11章 網路的數據結構和算法
11.1 採用矢量和柵格模型中的網路
11.2 最短路徑算法
11.3 網路數據的數據結構
11.4 旅行商問題
延伸閱讀
結語
辭彙表
參考文獻
圖目錄
圖1.1 查茲沃斯莊園的迷宮
圖1.2 用左手規則通過迷宮的路線
圖1.3 簡單算法不能破解的迷宮
圖1.4 圖1.3的路徑簡圖
圖1.5 基於Worboys(1995)的數據建模步驟
圖1.6 虛構的地形圖
圖1.7 圖1.6中地圖的部分柵格版本
圖1.8 圖1.6中的地形圖矢量版本
圖2.1 虛構的地形圖
圖2.2 點的屬性數據
圖2.3 線的坐標數據
圖2.4 通過一系列直線段逼近一條曲線
圖2.5 線的屬性數據
圖2.6 將線的位置信息添加到屬性表格當中
圖2.7 將線的位置信息添加到屬性表格當中的替代方法
圖2.8 建築物的位置數據
圖2.9 建築物的屬性信息
圖2.10 路的修正後屬性表格
圖2.11 區域特徵的存儲
圖2.12 土地利用圖示例(多個區域)
圖2.13 土地利用圖的屬性信息
圖2.14 兩次數位化同一條直線時造成的多邊形碎片
圖2.15 通過多邊形消除操作產生的城市區與非城市區區域地圖
圖2.16 拓撲GIS中存儲的土地利用圖
圖2.17 一個連線和節點數據結構中存儲的連線信息
圖2.18 哥尼斯堡橋問題
圖2.19 哥尼斯堡橋問題的圖形
圖2.20 用來說明地圖的Poincaré雙重圖形模型的虛構城區
圖2.21 虛擬城市地圖的DIME數據結構
圖2.22 DIME檔案中與街區5有關的記錄
圖2.23 DIME檔案中與相交點5有關的記錄
圖2.24 修改DIME檔案中與交匯點5有關的記錄,使得街道的終點是交匯點5
圖2.25 DIME數據結構中地址信息的存儲
圖3.1 線的相交問題
圖3.2 兩條相交線段的相交檢測
圖3.3 線段的坐標值
圖3.4 線相交問題:每組線可以通過相同的數學方程來定義
圖3.5 垂直直線的相交問題
圖3.6 檢測直線的相交
圖3.7 直線的最小外接矩形
圖3.8 最小外接矩形角頂點的定義
圖3.9 單調線段
圖3.10 通過一系列直線段逼近曲線
圖3.11 利用勾股定理計算兩點之間的距離
圖4.1 單一多邊形
圖4.2 計算多邊形面積:上面線段以下的部分面積減去下面線段以下的面積
圖4.3 單一線段以下的面積計算
圖4.4 多邊形上部分和下部分線段以下部分的面積
圖4.5 使用連線和節點數據結構存儲兩個相鄰的多邊形
圖4.6 多邊形檢測中的點
圖4.7 點的MER在多邊形檢測中的套用
圖4.8 初始檢測選擇的X坐標線段
圖4.9 一個點直接位於多邊形邊界頂點下方的特殊情況
圖4.10 多個多邊形中的點檢測
圖4.11 平面強化規則的結果
圖4.12 檢測哪一個多邊形位於一個連線的下方
圖5.1 一些常用來說明算法複雜度的函式值
圖5.2 直線相交的例子
圖5.3 使用MER的直線相交檢測
圖5.4 例證為什麼n+nlogn+logn是O(nlogn)
圖5.5 n的三種函式圖
圖6.1 計算機記憶體中數組的存儲
圖6.2 簡單柵格數組的例子
圖6.3 計算機記憶體中數組的存儲
圖6.4 一個位元組整數存儲的例子
圖6.5 簡單柵格陣列例子
圖6.6 行程長度編碼圖層在計算機記憶體中的存儲
圖6.7 圖6.5中圖層的四叉樹劃分
圖6.8 記憶體中四叉樹的存儲
圖6.9 四叉樹的圖形表示
圖7.1 簡單柵格數組的例子
圖7.2 計算機記憶體中數組的存儲
圖7.3 在計算機記憶體中行程編碼的圖像的存儲
圖7.4 圖6.5給出的圖層的四叉樹劃分
圖7.5 四叉樹在記憶體中的存儲
圖7.6 柵格圖層例子
圖7.7 採用行程長度編碼形式存儲圖層
圖7.8 兩種獲得行程數的方法
圖7.9 線性四叉樹形式下圖層的存儲
圖7.10 柵格圖像(圖7.6)的四叉樹表示
圖8.1 折半查找法的運行
圖8.2 二叉查找樹
圖8.3 存儲為二叉鍊表的查找樹
圖8.4 沿一條單獨的線分布的十個點,二叉查找樹建立在這些點的X坐標的基礎上
圖8.5 k^d樹
圖8.6 自然保護區地圖的四叉樹劃分及其葉節點的莫頓地址
圖8.7 採用莫頓地址順序來存儲像素時的序列
圖8.8 顯示像素莫頓地址的柵格圖層
圖9.1 商鋪顧客位置採樣點
圖9.2 山脈高度採樣點
圖9.3 採用點數據來解決表面查詢操作的問題
圖9.4 格網模型中的規則格網與採樣點
圖9.5 表面數據的不規則三角網模型
圖9.6 基於等高線的表面數據模型
圖9.7 等高線及數字高度模型格網點的小山峰等高線圖
圖9.8 點插值中分配權重的兩個函式
圖9.9 指數衰減曲線中改變指數的效果
圖9.10 數位化等高線當中反距離權重函式的套用
圖9.11 採用反距離權重法生成等高線的格網化DEM
圖9.12 表明三角劃分算法的採樣點
圖9.13 分別經過五步和六步操作後得到的三角形
圖9.14 採樣點的Voronoi鑲嵌
圖9.15 四個採樣點的Delaunay三角劃分
圖9.16 產生Delaunay三角劃分過程中邊的變化情況
圖9.17 對一個Delaunay三角劃分添加一個點
圖9.18 不規則三角網如何對表面進行建模
圖9.19 不同階多項式的圖形
圖9.20 不同擬合方法產生的DEM格網
圖9.21 採用Delaunay三角劃分擬合的DEM格網
圖10.1 圖表z=ax
圖10.2 圖表z=ax+b
圖10.3 用於估算點表面特性的3×3視窗單元格位置
圖10.4 過三個點的線
圖10.5 用兩個不同的DEM估算的斜面朝向
圖10.6 水流通過一個虛構的代表河谷的TIN的一部分
圖10.7 細分水流穿過三角形E
圖10.8 在TIN上確定排水溝時出現的無限循環
圖10.9 虛構的DEM
圖10.10 DEM單元格中方向的編碼表示
圖10.11 水流的十進制和二進制代碼
圖10.12 代表從各個鄰居流動到某個單元格的編碼
圖10.13 將2存儲到8bit位元組
圖10.14 虛構的DEM中的流動方向
圖10.15 三次重複運算的集水區
圖10.16 DEM的高度及流動方向與流量聚集值
圖11.1 虛擬道路網路
圖11.2 簡單的網路
圖11.3 圖11.2添加一些額外的連結以後的網路
圖11.4 二次增加和指數增加的對比
圖11.5 標識連線的簡單網路
圖11.6 簡單網路的連線和節點表示
圖11.7 網路的節點表
圖11.8 採用分開的節點和連線表來存儲網路信息
圖11.9 堆
圖11.10 交換節點2和節點4以後的堆
圖11.11 圖11.9中的二叉堆在一個數組當中的存儲
圖11.12 交換節點4和節點9以後的堆
圖11.13 去掉根節點以後的堆
圖11.14 圖11.13經過兩次交換以後的堆
圖11.15 針對四個點的TSP解答和MST解答
圖11.16 為什麼MST不能形成一個TSP最優解的證明
圖11.17 TSP道路網路
圖11.18 每個點僅遍歷一次的網路路徑
圖11.19 根據選定的3個點由增量啟發法形成的路徑
圖11.20 根據選定的5個點由增量啟發法形成的路徑
圖11.21 連線所有最外圍的點形成的路徑
圖11.22 對圖11.21所示的外層路徑添加所有的點以後形成的路徑
