GIS数据结构与算法基础

　　目译者的话前言致谢第1章 引言 11.1 计算机如何解决问题 11.2 计算机如何存储空间数据：矢量和栅格数据模型 41.3 本书结构 81.4 伪代码 10延伸阅读 13第2章 矢量数据结构 152.1 点和线的存储 152.2 区域边界的存储 192.3 存储区域的边界：拓扑法 212.4 什么是拓扑学 232.5 如何使用拓扑学？以DIME为例 25延伸阅读 27第3章 线的矢量算法 293.1 简单的线相交算法 293.2 为什么简单的直线相交算法无效：一个更好的算法 323.3 波形线的处理 363.4 有关直线上的计算：一条直线有多长 39延伸阅读 43第4章 区域的矢量算法 444.1 有关区域的计算：单一多边形 444.2 有关区域的计算：多重多边形 464.3 多边形的点：简单算法 484.4 利用拓扑的好算法 51延伸阅读 53第5章 算法效率 545.1 如何评估算法的有效性 545.2 直线相交算法的有效性 565.3 算法有效性的吏多知识 57延伸阅读 59第6章 栅格数据结构 606.1 栅格数据结构：数组 606.2 节省空间：行程长度编码和四叉树 64延伸阅读 67第7章 栅格算法 697.1 栅格算法：对行程编码数据的属性查询 697.2 栅格算法：四叉树中的属性查询 717.3 栅格算法：面积计算 77延伸阅读 82第8章 空间索引 838.1 二叉查找树 838.2 使用k-d树索引数据 878.3 采用四叉树结构索引向量数据 908.4 采用莫顿排序索引栅格数据 94延伸阅读 97第9章 表面数据结构 989.1 表面数据模型 989.2 创建格网表面模型的算法 1029.3 产生不规则三角网的算法 1069.4 格网划分修正 111延伸阅读 113第10章 表面算法 11510.1 高度、坡度和坡向 11510.2 用TIN做水文分析 12010.3 用格网DEM决定流向 12210.4 用流动方向做水文分析 124延伸阅读 129第11章 网络的数据结构和算法 13111.1 采用矢量和栅格模型中的网络 13111.2 最短路径算法 13311.3 网络数据的数据结构 13811.4 旅行商问题 144延伸阅读 149结语 150词汇表 151参考文献 155图目录图1.1 查兹沃斯庄园的迷宫 2图1.2 用左手规则通过迷宫的路线 2图1.3 简单算法不能破解的迷宫 3图1.4 图1.3的路径简图 3图1.5 基于Worbovs(1995)的数据建模步骤 4图1.6 虚构的地形图 6图1.7 图1.6中地图的部分栅格版本 6图1.8 图1.6中的地形图矢量版本 7图2.1 虚构的地形图 15图2.2 点的属性数据 16图2.3 线的坐标数据 16图2.4 通过一系列直线段逼近一条曲线 17图2.5 线的属性数据 17图2.6 将线的位置信息添加到属性表格当中 17图2.7 将线的位置信息添加到属性表格当中的替代方法 18图2.8 建筑物的位置数据 18图2.9 建筑物的属性信息 19图2.10 路的修正后属性表格 19图2.11 区域特征的存储 19图2.12 土地利用图示例（多个区域） 20图2.13 土地利用图的属性信息 20图2.14 两次数字化同一条直线时造成的多边形碎片 21图2.15 通过多边形消除操作产生的城市区与非城市区区域地图 21图2.16 拓扑GIS中存储的土地利用图 22图2.17 一个连接和节点数据结构中存储的连接信息 22图2.18 哥尼斯堡桥问题 24图2.19 哥尼斯堡桥问题的图形 24图2.20 用来说明地图的Poincare双重图形模型的虚构城区 25图2.21 虚拟城市地图的DIME数据结构 25图2.22 DIME文件中与街区5有关的记录 26图2.23 DIME文件中与相交点5有关的记录 26图2.24 修改DIME文件中与交汇点5有关的记录，使得街道的终点是交汇点5 27图2.25 DIME数据结构中地址信息的存储 27图3.1 线的相交问题 29图3.2 两条相交线段的相交检测 29图3.3 线段的坐标值 30图3.4 线相交问题：每组线可以通过相同的数学方程来定义 33图3.5 垂直直线的相交问题 35图3.6 检测直线的相交 37图3.7 直线的最小外接矩形 37图3.8 最小外接矩形角顶点的定义 37图3.9 单调线段 38图3.10 通过一系列直线段逼近曲线 40图3.11 利用勾股定理计算两点之间的距离 40图4.1 单一多边形 44图4.2 计算多边形面积：上面线段以下的部分面积减去下面线段以下的面积 44图4.3 单一线段以下的面积计算 45图4.4 多边形上部分和下部分线段以下部分的面积 45图4.5 使用连接和节点数据结构存储两个相邻的多边形 46图4.6 多边形检测中的点 48图4.7 点的MER在多边形检测中的应用 49图4.8 初始检测选择的X坐标线段 50图4.9 一个点直接位于乡边形边界顶点下方的特殊情况 50图4.10 多个多边形中的点检测 51图4.11 平面强化规则的结果 52图4.12 检测哪一个多边形位于一个连接的下方 53图5.1 一些常用来说明算法复杂度的函数值 56图5.9 直线相交的例子 56图5.3 使用MER的直线相交检测 57图5.4 例证为什么n+nlogn+logn是O(nlogn) 58图5.5 n的三种函数图 59图6.1 计算机内存中数组的存储 62图6.2 简单栅格数组的例子 62图6.3 计算机内存中数组的存储 63图6.4 一个字节整数存储的例子 64图6.5 简单栅格阵列例子 65图6.6 行程长度编码图层在计算机内存中的存储 65图6.7 图6.5中图层的四叉树划分 66图6.8 内存中四叉树的存储 66图6.9 四叉树的图形表示 67图7.1 简单栅格数组的例子 69图7.2 计算机内存中数组的存储 70图7.3 在计算机内存中行程编码的图像的存储 70图7.4 图6.5给出的图层的四叉树划分 71图7.5 四叉树在内存中的存储 72图7.6 栅格图层例子 78图7.7 采用行程长度编码形式存储图层 78图7.8 两种获得行程数的方法 79图7.9 线性四叉树形式下图层的存储 80图7.10 栅格图像（图7.6）的四叉树表示 80图8.1 折半查找法的运行 83图8.2 二叉查找树 85图8.3 存储为二叉链表的查找树 85图8.4 沿一条单独的线分布的十个点，二叉查找树建立在这些点的X坐标的基础上 88图8.5 k-d树 88图8.6 自然保护区地图的四叉树划分及其叶节点的莫顿地址 90图8.7 采用莫顿地址顺序来存储像素时的序列 95图8.8 显示像素莫顿地址的栅格图层 96图9.1 商铺顾客位置采样点 99图9.2 山脉高度采样点 99图9.3 采用点数据来解决表面查询操作的问魉 99图9.4 格网模型中的规则格网与采样点 100图9.5 表面数据的不规则三角网模型 101图9.6 基于等高线的表面数据模型 101图9.7 等高线及数字高度模型格网点的小山峰等高线图 103图9.8 点插值中分配权重的两个函数 103图9.9 指数衰减曲线中改变指数的效果 104图9.10 数字化等高线当中反距离权重函数的应用 105图9.11 采用反距离权重法生成等高线的格网化DEM 106图9.12 表明三角划分算法的采样点 106图9.13 分别经过五步和六步操作后得到的三角形 107图9.14 采样点的Voronoi镶嵌 108图9.15 四个采样点的Delaunav三角划分 108图9.16 产生Delaunav三角划分过程中边的变化情况 109图9.17 对一个Delaunav三角划分添加一个点 110图9.18 不规则三角网如何对表面进行建模 111图9.19 不同阶多项式的图形 112图9.20 不同拟合方法产生的DEM格网 112图9.21 采用Delaunav三角划分拟合的DEM格网 113图10.1 图表z=ax 116图10.2 图表z=ax+b 117图10.3 用于估算点表面特性的3×3窗口单元格位置 118图10.4 过三个点的线 119图10.5 用两个不同的DEM估算的斜面朝向 119图10.6 水流通过一个虚构的代表河谷的TIN的一部分 120图10.7 细分水流穿过三角形E 121图10.8 在TIN上确定排水沟时出现的无限循环 121图10.9 虚构的DEM 122图10.10 DEM单元格中方向的编码表示 122图10.11 水流的十进制和二进制代码 123图10.12 代表从各个邻居流动到某个单元格的编码 123图10.13 将2存储到8bit字节 124图10.14 虚构的DEM中的流动方向 125图10.15 三次重复运算的集水区 125图10.16 DEM的高度及流动方向与流量聚集值 126图11.1 虚拟道路网络 131图11.2 简单的网络 133图11.3 图11.2添加一些额外的链接以后的网络 133图11.4 二次增加和指数增加的对比 134图11.5 标识连接的简单网络 138图11.6 简单网络的连接和节点表示 138图11.7 网络的节点表 139图11.8 采用分开的节点和连接表来存储网络信息 140图11.9 堆 141图11.10 交换节点2和节点4以后的堆 141图11.11 图11.9中的二叉堆在一个数组当中的存储 142图11.12 交换节点4和节点9以后的堆 143图11.13 去掉根节点以后的堆 143图11.14 图11.13经过两次交换以后的堆 144图11.15 针对四个点的TSP解答和MST解答 145图11.16 为什么MST不能形成一个TSP最优解的证明 146图11.17 TSP道路网络 146图11.18 每个点仅遍历一次的网络路径 146图11.19 根据选定的3个点由增量启发法形成

　　朱定局，北京大学博士后，中国科学院计算技术研究所博士，中国科学院深圳先进技术研究院智慧计算与信息科学实验室主任。曾任胜利油田地质科学研究院科研人员，美国Texas State University地理系访问学者。

　　《GIS数据结构与算法基础》是Stephen Wise撰写的GIS Basics一书的翻译版。内容涉及GIS的核心数据结构和核心算法，详细介绍了各种矢量、栅格、索引、表面、网络相关的数据结构与算法。《GIS数据结构与算法基础》包含了大量所述数据结构与算法的伪代码，同时每章末配有延伸阅读，可帮助读者对《GIS数据结构与算法基础》内容进行更深入地理解。