**章 GIS算法概述
**节 算法与GIS算法
一、基本概念
算法（algorithm）通常指的是解决某个具体问题的思路和方案，具体来看是一系列解决问题的步骤，体现在计算机中就是一连串的指令。把算法使用一种计算机语言写成程序，则要求算法程序针对一定的输入数据，能在有限的时间内计算出所需要的输出数据。输出数据代表了解决某个问题的可行方案。
所谓GIS算法，指的是GIS领域特定的算法，这些算法所要解决的通常就是与空间位置有关的应用问题。GIS软件如ArcGIS、QGIS、SuperMap等通常都是这些GIS算法的集合。
例如，从某一个地点开始，沿着道路行走，要去到另一个地点。这个问题中往往存在多种不同的行走路线。如果需要从所有的可行路线中找一条路程*短的路线，这个应用问题的解决就需要运用某种求*短路径的算法。例如，常见的一种迪杰斯特拉算法就是解决在道路网上从某个起点出发，到另一个终点结束的*短路径的算法。把迪杰斯特拉算法的思想写成计算机程序，就可以在GIS软件或手机的导航应用程序中帮助人们在实际的道路网上寻找从一个地点到另一个地点的*佳的行走路线。
一个算法通常应该具有以下五个特征，对于GIS算法也是如此。
（1）有穷性：指算法必须能够在执行有限个步骤之后终止，即要么得到解决问题的结果而结束算法，要么问题无解而结束算法。GIS中的算法通常都可以在有限个步骤之后结束。
（2）确切性：算法的每一步骤必须有确切的定义，即每一个步骤的解决办法都明确无误，没有模棱两可的歧义。GIS算法中的每一步也都是对空间数据内容的确切的处理。
（3）输入项：算法需要有输入数据，输入数据用来表达实际问题的初始状态或初始条件。GIS算法的输入数据通常就是矢量形式或栅格形式的空间数据，其中包括空间实体的位置（坐标）数据和属性数据。
（4）输出项：算法需要有输出数据，输出数据用来反映对输入数据经过若干步骤的运算处理后所得到的结果，该结果有助于对具体问题的解决。GIS算法的输出数据通常是和输入数据相关的空间数据，主要是空间实体的位置数据，也有些GIS算法是生成空间要素的属性数据，如空间统计分析等。
（5）可行性：也称为有效性，算法中执行的任何计算步骤都可以被分解为基本的可执行的操作步骤，每个计算步骤都可以在有限时间内完成。这些步骤可以通过人工计算来实现，也可以编写成计算机程序，由计算机执行来实现。无论是人工计算实现还是计算机程序执行来实现，其结果都是相同的。
实际情况下，对同一个应用问题的解决，往往可以有多种不同的算法实现。这些不同的算法之间的区别*先在于它们解决问题的思路不同，而相同之处则是它们解决问题的结果通常都一样。也就是说使用不同的算法，*终都能得到相同的正确结果。
这些不同的算法中有的算法执行效率比较高，可以在较短的时间内得到结果。这对于有时间要求的应用比较有利，即某个应用问题要求在尽可能短的时间内就能得到算法的结果，则时间效率较高的算法比较好。另外，有的算法使用的计算机资源比较节省，如使用的内存数量比较小，这对于数据量大的应用来说相对比较有利，不容易出现计算机内存紧张的问题。因此，对算法的评价通常可以从时间复杂度和空间复杂度两方面来考虑。
时间复杂度：通常在衡量一个算法的时间复杂度时，并不是看这个算法在实际的计算机上运行所要花费的时间，而是考虑随着输入数据量的增加，该算法所要执行的步骤将会以什么样的速度增加。这是因为，对于输入数据量非常小的应用问题，通常在计算机上运行不同的算法，其消耗的运行时间相差无几。这时候考虑时间复杂度就没有太大的意义。只有在输入数据量巨大的情况下，不同算法之间才会体现出执行时间上的较大差异。
一般而言，计算机算法的时间复杂度可以看成是问题规模的一个函数，问题的规模往往就是数据量的体现。在GIS算法中，数据的规模可以用一个空间数据层中全部点要素的数量来衡量，也可以用一个栅格数据中栅格单元的数量来衡量。对于具体的算法，问题的规模随着具体应用的不同而变化。
因此，一旦确定了问题的规模，假设是数值n，那么随着问题规模n的增大，算法执行的步骤和时间也会随之增大，时间复杂度就可以用相对于n的一个函数来表示。一般把这个函数写成O(n)的形式，如假设O(log2n)和O(n2)是解决某一问题的两个不同算法的时间复杂度，**个算法随着规模n的增大，计算步骤按log2n这样的数量递增；而第二个算法的计算步骤按n2的数量递增。在n数值比较大的时候，n2远远大于log2n，所以第二个算法的时间开销要大于**个算法。
空间复杂度：算法的空间复杂度是指算法需要消耗的内存空间的数量。其计算和表示方法与时间复杂度类似，也是问题规模的函数形式。与时间复杂度相比，空间复杂度的分析相对简单。
二、GIS算法的特点
与其他领域的算法相比，GIS算法的特点表现在以下两个方面：①GIS算法都是基于地理空间数据的算法；②GIS算法常常是多学科交叉的产物。
*先，GIS算法处理的输入和输出数据通常都是地理空间数据，都是处于地球上某一特定位置的数据，都表现为在地理空间范围内的空间分布，所以，GIS算法*先要解决的问题就是如何表达地理空间数据，也就是要研究和GIS算法所对应的空间数据结构。由此来解决如何把地理空间数据这种特殊形式的数据在计算机中进行存储和计算的问题。这也是需要*先解决的问题，所以从第二章开始，我们要*先建立地理空间数据模型和空间数据结构。
其次，由于GIS本身就是一个多学科交叉的产物，所以GIS算法同样体现出强烈的多学科交叉性质。要实现GIS算法，除了计算机领域的编程语言和数据结构等知识以外，还要具备微积分（如第九章的地图投影算法）、线性代数（如第十章的几何变换算法）、统计学（如第十一、第十二章的空间插值算法和第十三章的栅格统计算法）、地貌学（如第十四章的数字地形分析算法和第十五章的流域水文分析算法）、计算机图形学（如第四、第五章的空间数据可视化）等方面的知识。
第二节 GIS算法的分类
一个GIS软件中的GIS算法往往数量众多，不过可以将它们按照所起的作用分为以下四个不同的类别。
一、GIS数据输入输出算法
GIS算法处理的地理空间数据通常数据结构都比较复杂，所以在实现了空间数据结构以后，就要实现GIS数据的输入和输出算法。“输入”指的是把GIS空间数据从常见的空间数据文件（或者数据库）中读取到计算机内存，这是进一步进行空间数据处理和分析以及数据可视化的前提。“输出”指的是把经过处理和分析计算之后得到的新的空间数据从内存写入到空间数据文件中，使得分析结果得以保存。
GIS空间数据文件和空间数据库种类繁多，我们选择了其中*为常用的ESRI Shapefile空间数据文件格式作为矢量数据的实例，ESRI GRID文本文件和BIL二进制文件作为栅格数据的实例，以及Shapefile所使用的dBASE数据库文件格式作为属性数据的实例，实现其数据的输入和输出算法。
二、GIS数据处理算法
在地理空间数据输入到计算机内存中以后，下一个步骤通常是GIS的空间数据处理阶段。这一阶段包括空间坐标系的转换以及地图投影的变换算法、几何变换如仿射变换等算法、空间索引与空间查询算法，以及多种空间插值算法等。
三、GIS空间分析算法
GIS的空间分析是GIS的精髓所在，这一部分构成了GIS*为重要的功能。这一部分着重介绍栅格数据数字地形分析中的各种地形因子计算方法、流域水文分析算法、栅格统计算法、自然距离算法、成本距离算法以及成本路径算法等。
四、GIS可视化算法
GIS软件通常是一个图形用户界面的软件，在界面上要显示各种地理空间数据的地图图形，甚至是三维空间模型的形象，这通常被称为GIS可视化。这一部分通常要实现在计算机屏幕上如何显示矢量或栅格地图的图形、地图符号、各种颜色、图案等功能。GIS可视化大量地借助于计算机图形学方面的知识，既有二维图形学的相关知识，也涉及三维图形学的内容。
第三节 GIS算法实现的软硬件需求
一、编程语言
GIS通常需要处理大量的空间数据，还要在计算机屏幕上显示复杂的地图图形以及三维空间模型，所以对于底层的基础算法在时间效率方面的要求通常比较高。因此，目前大多数GIS软件是基于C语言或C++语言开发的，包括ArcGIS、QGIS等较为著名的GIS软件。而其他的编程语言往往在执行效率上不及C与C++。所以，本教材决定采用C++。
而从GIS软件本身的复杂性来看，通常一个GIS软件是一个大型的软件系统，安装ArcGIS软件要占用好几个吉字节（GB）的计算机硬盘空间，就连比较轻量级的开源QGIS软件，在Windows上的安装包也超过1 GB的大小。对于如此规模和复杂的软件系统，选择具备面向对象编程功能的C++编程语言，有助于错综复杂的算法的组织和实现。
C++还是一种不断更新迭代、一直在与时俱进的编程语言，从*早的官方标准C++ 98版本，发展到现在的C++ 20版本，可以说越来越吸取了当代编程语言的精华。它既有传统的典雅，又有现代的简约；既能深入计算机幽深的底层硬件，又能扩展到广阔无垠的应用高空；既能以*直率的方式将复杂的思路表达清晰，又能够聚沙成塔构建起复杂系统的鸿篇巨制。所以，几十年来，虽然各种计算机语言层出不穷，但C++语言一直处于无可替代的地位。这也是本教材决定采用C++语言的原因之一。只有这样，才能保证在一个较长的时期内，我们讨论的GIS算法不至于因为计算机语言的兴衰而落后于时代，被学生们所抛弃。
此外，平台无关性也是要考虑的一个因素，特别是在当前阶段下，我们若要发展自主知识产权的GIS软件系统，就不能因为编程语言的限制而只局限在某些操作系统上面。随着我国自主研发的操作系统等基础软件的不断完善，我们需要将GIS软件构建在自己的操作系统之上，而不依赖于像Windows这样的软件。因此，选用*立于系统平台的C++编程语言，是一个比较好的实现方案。
二、编译系统和开发环境
由于选择了C++编程语言，本教材后面所有的算法编写都基于C++来实现。如果是在Windows操作系统中实现本教材的算法，则可以采用微软的C++编译系统和集成开发环境，即Visual Studio支持的C++编译系统和集成开发环境。学生们可以去微软的Visual Studio网站，免费下载使用Visual Studio软件的社区版本。这个版本具备了基础的C++项目编程功能，包括创建项目、编辑代码、编译修改、运行调试等，都集成在一个软件中，非常适合初学者使用，如图1-1所示。
图1-1 微软Visual Studio的C++编译器和集成开发环境
如果使用Linux系列的操作系统，包括国产的操作系统进行编程实验，则可以使用Qt Creator免费的社区版本作为C++语言的集成开发环境，如图1-2所示。编译器自然就可以采用GNU的GCC。
图1-2 Qt Creator社区版本C++语言的集成开发环境
三、编程规范
由于本教材主要是讲述GIS算法的基本原理，所以在算法的代码实现上通常并不追求时间复杂度和空间复杂度方面的优秀设计，如对于大量的栅格运算没有采用常见的多线程并行算法来实现，也不过多使用一些C++语言方面的技巧和优化，以免对算法理解方面增加不必要的难度。同样，算法也不注重全面性，这表现在算法既没有全面地处理各种特殊情况，也不考虑异常的处理，包括检验文件是否存在、数组是否越界、堆内存是否申请成功等问题，从而造成代码过长，占用太多的版面而影响对算法本身的理解。学生们在实际上机编写源代码时，则需要考虑这些方方面面的细节，以免
展开
