地理信息系统算法基础PDF电子书下载

1.1 概述 1

1.2 算法设计原则 1

第1章 算法设计和分析 1

1.3 算法复杂性的度量 2

1.3.1 时间复杂性 2

1.3.2 空间复杂性 8

1.4 最优算法 8

1.5 算法的评价 9

1.5.1 如何估计算法运行时间 9

1.5.2 最坏情况和平均情况的分析 11

1.5.3 平摊分析 13

1.5.4 输入大小和问题实例 13

思考题 14

2.1.1 概述 15

2.1.2 模型介绍 15

2.1 维数扩展的9交集模型 15

第2章 GIS算法的计算几何基础 15

2.1.3 空间关系的判定 17

2.2 矢量的概念 21

2.2.1 矢量加减法 21

2.2.2 矢量叉积 22

2.3 折线段的拐向判断 22

2.5 判断两线段是否相交 23

2.4 判断点是否在线段上 23

2.6 判断矩形是否包含点 25

2.7 判断线段、折线、多边形是否在矩形中 25

2.8 判断矩形是否在矩形中 25

2.9 判断圆是否在矩形中 25

2.10 判断点是否在多边形内 25

2.10.1 射线法 26

2.10.2 转角法 28

2.11 判断线段是否在多边形内 30

2.13 判断多边形是否在多边形内 32

2.12 判断折线是否在多边形内 32

2.14 判断矩形是否在多边形内 33

2.15 判断圆是否在多边形内 33

2.16 判断点是否在圆内 33

2.17 判断线段、折线、矩形、多边形是否在圆内 33

2.18 判断圆是否在圆内 33

2.19 计算两条共线的线段的交点 33

2.20 计算线段或直线与线段的交点 34

2.21 求线段或直线与圆的交点 35

2.22 中心点的计算 36

2.23 过点作垂线 37

2.24 作平行线 37

2.25 过点作平行线 38

2.26 线段延长 38

2.27 三点画圆 39

2.28 线段打断 39

2.29 前方交会 40

2.30 距离交会 41

2.31 极坐标作点 43

思考题 44

第3章 空间数据的变换算法 45

3.1 平面坐标变换 45

3.1.1 平面直角坐标系的建立 45

3.1.2 平面坐标变换矩阵 45

3.1.3 平移变换 46

3.1.4 比例变换 47

3.1.5 对称变换 47

3.1.6 旋转变换 47

3.1.7 错切变换 48

3.1.8 复合变换 48

3.1.9 相对（xf,yf）点的比例变换 49

3.1.10 相对（xf,yf）点的旋转变换 49

3.2.1 球面坐标系的建立 50

3.2 球面坐标变换 50

3.1.11 几点说明 50

3.2.2 确定新极Q地理坐标中？0、λ0 51

3.3 仿射变换 54

3.4 地图投影变换 55

3.4.1 概述 55

3.4.2 地球椭球体的相关公式 57

3.4.3 兰勃特投影 62

3.4.4 墨卡托投影 64

3.4.5 高斯-克吕格投影 65

3.4.6 通用横轴墨卡托投影 68

思考题 69

第4章 空间数据转换算法 70

4.1 矢量数据向栅格数据转换 70

4.1.1 矢量点的栅格化 70

4.1.2 矢量线的栅格化 71

4.1.3 矢量面的栅格化 73

4.2.1 栅格点坐标与矢量点坐标的关系 77

4.2 栅格数据向矢量数据转换 77

4.2.2 栅格数据矢量化的基本步骤 78

4.2.3 线状栅格数据的细化 78

4.2.4 多边形栅格转矢量的双边界搜索算法 84

4.2.5 多边形栅格转矢量的单边界搜索算法 86

思考题 89

第5章 空间数据组织算法 90

5.1 矢量数据的压缩 90

5.1.1 间隔取点法 90

5.1.2 垂距法和偏角法 90

5.1.3 道格拉斯-普克法 91

5.1.4 光栏法 93

5.1.5 曲线压缩算法的比较 95

5.1.6 面域的数据压缩算法 96

5.2 栅格数据的压缩 98

5.2.1 链式编码 98

5.2.2 游程长度编码 99

5.2.4 差分映射法 101

5.2.3 块式编码 101

5.2.5 四叉树编码 102

5.3 拓扑关系的生成 102

5.3.1 基本数据结构 103

5.3.2 弧段的预处理 106

5.3.3 结点匹配算法 112

5.3.4 建立拓扑关系 114

思考题 117

第6章 空间度量算法 118

6.1 直线和距离 118

6.1.1 直线 118

6.1.2 直线方程 119

6.1.3 点到直线的距离 120

6.3 多边形面积的量算 125

6.3.1 三角形面积量算 125

6.2 角度量算 125

6.3.2 四边形面积量算 127

6.3.3 任意二维平面多边形面积量算 129

6.3.4 任意三维平面多边形面积量算 131

思考题 134

第7章 空间数据索引算法 135

7.1 B树与B+树 135

7.1.1 B树索引结构 136

7.1.2 B+树索引结构 140

7.2 R树结构 141

7.2.1 R树定义 141

7.2.2 R树索引的主要操作算法 142

7.2.3 R*树算法 146

7.3 四叉树结构 147

7.3.1 常规四叉树 147

7.3.2 线性四叉树 149

7.3.3 线性四叉树的编码 149

7.3.4 Z曲线和Hibert曲线算法 155

思考题 158

第8章 空间数据内插算法 159

8.1 概述 159

8.1.1 几何方法 159

8.1.2 统计方法 159

8.1.3 空间统计方法 160

8.1.4 函数方法 160

8.1.5 随机模拟方法 160

8.1.6 确定性模拟 161

8.1.7 综合方法 161

8.2 分段圆弧法 161

8.3 分段三次多项式插值法 162

8.3.1 三点法 162

8.3.2 五点法 162

8.4 趋势面插值算法 163

8.6 双线性插值算法 166

8.5 反距离权重插值算法 166

8.7 薄板样条函数法 167

8.7.1 薄板样条函数法 167

8.7.2 规则样条函数 168

8.7.3 薄板张力样条法 168

8.8 克里金法 169

8.8.1 普通克里金法 169

思考题 171

8.8.2 通用克里金法 171

第9章 Delaunay三角网与Voronoi图算法 172

9.1 概述 172

9.2 Voronoi图 173

9.3 Delaunay三角形 174

9.4 Voronoi图生成算法 174

9.4.1 半平面的交 174

9.4.2 增量构造方法 175

9.4.3 分治算法 178

9.4.4 减量算法 180

9.4.5 平面扫描算法 182

思考题 184

第10章 缓冲区分析算法 185

10.1 概述 185

10.2 缓冲区边界生成算法基础 185

10.3 点缓冲区边界生成算法 187

10.4 线缓冲区边界生成算法 188

10.5 面缓冲区边界生成算法 195

10.6 多目标缓冲区合并算法 195

思考题 200

第11章 网络分析算法 201

11.1 概述 201

11.2 网络数据模型 201

11.3 路径分析算法 203

11.3.1 单源点的最短路径 204

11.3.3 单结点对间最短路径问题 208

11.3.2 单目标最短路径问题 208

11.3.4 多结点对间最短路径问题 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 数字地面模型的生成算法 219

12.1.1 基于离散点的DEM规则网格的生成 219

12.1.2 基于不规则三角网的DEM生成 221

12.1.3 DEM数据结构的相互转换 221

12.2.1 坡面因子提取的算法基础 235

12.2 基本地形因子分析算法 235

12.2.2 坡度、坡向 239

12.2.3 坡形 241

12.3 地形特征提取算法 244

12.3.1 地形特征点的提取 245

12.3.2 基于规则格网DEM数据提取山脊与山谷线的典型算法 246

12.4 通视分析算法 248

12.4.1 判断两点之间的可视性的算法 248

12.4.2 计算可视域的算法 248

思考题 249

第13章 空间数据挖掘算法 250

13.1 概述 250

13.2 分类算法 250

13.2.1 数据分类的基本过程 250

13.2.2 决策树分类概述 251

13.2.3 决策树的特点 251

13.2.4 二叉决策树算法与分类规则的生成 252

13.2.5 决策树分类算法 253

13.2.6 决策树属性的选取 254

13.2.7 改进决策树性能的方法 255

13.3 泛化规则算法 256

13.3.1 概念层次 256

13.3.2 面向属性泛化的策略与特点 258

13.3.3 基于规则的面向属性泛化方法 260

13.4 相关分析 263

13.4.1 两要素间的相关分析 263

13.4.2 多要素之间的相关分析 265

13.4.3 关联规则算法 267

13.5 回归分析 274

13.5.1 一元线性回归模型 274

13.5.2 多元线性回归模型 277

13.5.3 非线性回归模型 281

13.5.4 回归分析与相关分析 282

13.6.2 聚类要素预处理 283

13.6 系统聚类分析 283

13.6.1 概述 283

13.6.3 分类统计量 284

13.6.4 系统聚类法 286

13.6.5 其他聚类方法概述 292

13.7 判别分析 293

13.7.1 距离判别 294

13.7.2 费歇判别法 297

13.7.3 贝叶斯判别法 300

13.7.4 判别分析应注意的问题 302

13.8 主成分分析 303

13.8.1 主成分分析的基本原理 303

13.8.2 主成分分析的方法 304

思考题 306

14.1 概述 308

14.1.1 地图符号构成元素组成 308

第14章 数据输出算法 308

14.1.2 地图符号几何特征 309

14.1.3 基于SVG的地图符号描述模型 310

14.2 点状地图符号的绘制 312

14.2.1 圆的绘制 312

14.2.2 椭圆的绘制 314

14.2.3 多边形的绘制 314

14.2.4 五角星的绘制 316

14.3 线状地图符号的绘制 318

14.3.1 平行线绘制 319

14.3.2 虚线绘制 321

14.3.3 短齿线的绘制 322

14.3.4 铁路线的绘制 324

14.3.5 境界线的绘制 326

14.4 面状地图符号的绘制 328

思考题 333

主要参考文献 334