空间分析算法最短路径算法

由图论的知识可知，地图上的点构成一带权无向图(有向图可视为特例的一种)，要找出任意两地间的最短路径,对地图中的所有点，首先要建立一个邻接矩阵，它表示图中任意两地间的邻接关系及其权值(若两地间无任何连接关系则设为无穷大)，易知该矩阵为对称矩阵。从该矩阵出发，可以利用图论中的迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法等求出最短路径。

Dijkstra算法

Dijkstra算法的基本思路是：首先，引进一个辅助向量Dist，它的每个分量Dist [i]表示当前找到的从始点V到每个终点Vi 的最短路径的长度。它的初始值为:若从V到Vi有弧，则Dist [i]为弧上的权值;否则置Dist[i]为无穷大。显然，长度为Dist[i]=Min{Dist[i]|Vi

Dijkstra算法描述为：

(1) 假设用带权的邻接矩阵Cost来表示带权有向图，Cost[i,j]表示弧(Vi , V j)上权值。若(Vi,Vj)不存在，则置Cost[i,j]为无穷大。S为已找到从V出发的最短路径的终点的集合，它的初始状态为空集。

(2) 选择Vj，使得Dist [i] =Min {Dist [i] |Vi 不

(4) 重复操作(2) , (3)共N-1次。由此求得从V到图上其余各顶点的最短路径是依路径长度递增的序列。

弗洛伊德算法

弗洛伊德算法能够求得每一对顶点之间的最短路径，其基本思想是：假设从顶点Vi到Vj的最短路径。若从Vi到Vj有弧，则从Vi到Vj存在一条长度为COST [ i, j]的路径，该路径不一定是最短路径，尚需进行n次试探。首先考虑路径(Vi, V1, Vj)是否存在(即判别弧(Vi, V1)和弧(V1, Vj)是否存在)。如果存在，则比较(Vi, Vj)和(Vi, V1, Vj)的路径长度，较短者为从Vi到Vj的中点顶点的序号不大于1的最短路径。假如在路径上再增加一个顶点V2，也就是说，若(Vi，…，V2)和(V2，...，Vj)分别是当前找到的中间顶点的序号不大于1的最短路径，那么(Vi，...，V2，...，Vj)就有可能是从Vi到Vj的中间顶点的序号不大于2的最短路径。将它和已经得到的从Vi 到Vj的中间顶点的序号不大于1的最短路径相比较，从中选出中间顶点的序号不大于2的最短路径之后，再增加一个顶点V3，继续进行试探。依次类推，在经过n次比较之后，最后求得的必是从Vi 到Vj的最短路径。按此方法，可同时求得各对顶点间的最短路径。算法共需3层循环，总的时间复杂度是O(

平面点集 S 的凸包是包含 S 中所有点的最小凸多边形，其顶点为 S 中的点。

设多边形 Q 的顶点是给定平面内的点

设二维点集 S = {

许多空间分析问题都可以归结为凸包问题，求取凸包的算法有增量法、格雷厄姆扫描法、卷包裹法和分治法等。

(1) 增量法：首先取几个点，形成初始凸包，然后不断寻找当前凸包外的新顶点来更新凸包，直到所有的点都在凸包内。其计算复杂度为 O(

(2) 格雷厄姆扫描法：首先找到最小 Y 坐标点，接着按照其它点和该极值点的连线与 x 轴的夹角的角度值排序，通过判断连续 3 个点的空间关系，从而得到逆时针排列的凸包顶点。其计算复杂度为 O(nlogn)。

(3) 卷包裹法：以某极值点作为开始点，根据其他点都位于相邻顶点连线同侧的原则，找到所有的顶点。其计算复杂度为 O(nh)，这里 n 和 h 分别为点数和凸包边界数。

(4) 分治法：先按坐标将点集分成 2 个子集 L 和 R，使得 L 中所有的点在 R的左边，递归地找到 L 和 R 的凸包，通过子凸包的公切线对其合并。其计算复杂度为 O(nlogn)。

所有这些算法的计算复杂度都大于或等于 O(nlogn)，凸包算法时间复杂度的下限为 O(nlogn)，虽然有些算法在特殊情况下可以达到线性时间的复杂度，不过在最坏的情况下，计算复杂度仍不低于 O(nlogn)。

平面扫描算法的主要内容是对空间对象进行一遍扫描，并在扫描过程中完成对空间对象的性质或空间对象之间的关系的分析。在扫描过程中，扫描线自左向右移动，依一定顺序遍历所有与扫描线相交的空间元素，判断它们之间的顺序和其他空间拓扑关系，依照一定规则进行分析。图1中给出了平面扫描算法的示意，其中粗线段表示和扫描线相交的线段。

任何平面扫描算法的基本要素都包括：事件点列表，扫描线状态，事件点触发的动作。 其中，事件点列表 指依照系统确定的空间排序关系，事先确定或在扫描过程中计算出的算法感兴趣的空间元素的有序序列；扫描线状态指依照确定的排序规则记录当前与扫描线相交的空间元素的有序表 ；事件点触发的动作指扫描到事件点时做出的分析或操作。

事先确定的事件点列表在扫描过程中不再变化，称为静态事件点列表；需要在扫描过程中计算的事件点列表称为动态事件点列表。和扫描线相交的线段以及落在扫描线上的点是扫描线状态的组成元素。事件点可以是任何分析算法感兴趣的空间元素，包括对象之间交点和特定线段元素等。

可以将扫描线状态看成一种抽象数据类型，记为 Sweep_Status，它拥有自己的数据组织方式、排序规则和操作方法。扫描线状态中的排序规则是按照各个空间元素和扫描线交点的 Y 坐标的大小来排序，在这种排序关系的组织下可以对一个与扫描线相交的空间元素取前驱或则后继。图1中标号 1 到 4 给出了与扫描线相交的线段的排序顺序。

平面扫描算法是一个算法框架，给定上述三个要素的具体实现，就可以给定一个具有一定的功能的空间分析算法。下面 S 是 Sweep_Status 类型的变量，s 是空间线段，对扫描线状态定义一系列操作。

关于扫描线状态的操作：

(1) new_sweep()，生成一个新的扫描线状态的数据结构，返回 Sweep_Status类型的变量；

(2) add_left(S,s)，当扫描过程中遇到左半线段类型的事件点的时候，向 S 中插入一个左半线段对应的线段元素 s，操作返回一个插入线段后的扫描线状态；

(3) del_right(S,s)，当扫描过程中遇到右半线段类型的事件点的时候，在扫描线中删除右半线段对应的线段元素， S、s 及返回值的定义同 add_left(S,s)；

(4) pred_of(S,elem)，在扫描线状态中定位空间元素 elem 的前驱，即确定存在于S中且按照扫描线的排序规则比elem小的元素的集合中最大的元素的位置，操作结果设置 S 的数据项 current 指向 elem 的前驱，current = 0 表示前驱不存在，返回 current 被设置后的扫描线状态；

(5) current_exists(S)，当 S 的数据项 current = 0，返回 FALSE，否则返回 TRUE；

(6) set_attr(S，attr)设置 S 中 current 所指的空间元素的属性，attr 是属性集合；

(7) get_attr(S)取 S 中 current 所指的空间元素的属性，返回属性集合；

InsideAbove 是区域类型对象 R 中的线段的一个属性，它表示这个线段的上方或者左侧是区域的内部。可以用平面扫描算法判断并设置 R 中的线段 s 是否具有属性 InsideAbove：如果它在扫描线状态中的序号为奇数，则 s 具有属性InsideAbove；否则不具备这种属性。这种判断和设置在建立空间对象的时候完成，图1中给出了示例。

地理信息系统(Geographic Information System，简称GIS)是采集、处理、存储、查询、分析和显示与地球表面空间相关的数据的计算机系统。对于具体应用来说，它是利用计算机科学管理和综合分析现实世界与空间位置相关的地理数据，为规划、管理、研究等提供辅助决策的信息系统。

空间分析是建立在对空间数据的有效管理之上的，是地理信息系统区别于一般信息系统的主要功能特征，也成为评价一个空间信息系统功能的主要指标之一。空间分析是基于空间对象的位置和形态特征的空间数据分析技术，其目的在于提取和传输空间信息。利用空间分析技术，通过对原始数据模型的观察和实验，用户可以获得新的经验和知识，并以此作为空间行为的决策依据。空间分析在水污染监测、城市规划与管理、地震灾害和损失估计、洪水灾害分析、矿产资源评价、道路交通管理、地形地貌分析和军事领域等领域都有广泛应用。

《计算机算法设计与分析（第5版）》修正了第4版中发现的一些错误，并将各章的习题分为算法分析题和算法实现题两部分，增加了算法实践性内容，增加了有关串和序列的算法内容。

该教材各章的论述中，首先介绍一种算法设计策略的基本思想，然后从解决计算机科学和应用中的实际问题入手，描述几个算法。同时对每个算法所需的时间和空间进行分析，使读者既能学到一些常用的算法，也能通过对算法设计策略的反复应用，牢固掌握这些算法设计的基本策略。该教材选择某些问题，通过对解同一问题的不同算法的比较，使读者体会到每种算法的设计要点。

该教材采用面向对象的C 语言作为算法描述手段，在保持C 优点的同时，尽量使算法描述简明、清晰。每章的章首为学习要点提示，章末配有难易适度的习题，分为算法分析题和算法实现题两部分，以强化实践环节 。

空间分析是地理信息系统的主要功能特征。《空间分析（第2版）》以全新的思路，将各种空间分析的方法与模型区分为基本分析方法和专门应用模型两个层次，以空间信息的构成为主体框架，组织和阐述了空间分析的基本内容。全书共分为七章，着重叙述了空间分布、空间位置、空间形态、空间距离，以及空间方位、拓扑、相似和相关等分析的基本理论和算法实现。

《空间分析（第2版）》可作为有关专业研究生的教学用书，亦可用作有关专业本科生的选修课教材或教学参考书，同时也适合于地理、测绘、土地、城建、规划等领域从事地理信息处理与分析的研究人员和工程技术人员阅读参考。学习或阅读《空间分析（第2版）》最好先具备地理信息系统方面的基础知识。

• 配套教材

《计算机算法设计与分析（第5版）》有配套教材——《计算机算法设计与分析习题解答（第5版）》 。