空间分析算法( 二 ) _生活百科

文章插图
，如果线段

文章插图
（i ≠ j，1 ≤ i ≤ n，1 ≤ j ≤ n）总不在多边形 Q 外，则称 Q 为凸多边形。设二维点集 S = {

文章插图
│1 ≤ i ≤ n, 1 ≤ j ≤ n, |s| = n}由给定平面内的点构成。如果凸多边形 Q 的任意顶点

文章插图
，且 Q 是可覆盖 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) 。最短路径算法由图论的知识可知，地图上的点构成一带权无向图(有向图可视为特例的一种)，要找出任意两地间的最短路径,对地图中的所有点，首先要建立一个邻接矩阵，它表示图中任意两地间的邻接关係及其权值(若两地间无任何连线关係则设为无穷大)，易知该矩阵为对称矩阵。从该矩阵出发，可以利用图论中的迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法等求出最短路径。Dijkstra算法Dijkstra算法的基本思路是：首先，引进一个辅助向量Dist，它的每个分量Dist [i]表示当前找到的从始点V到每个终点Vi 的最短路径的长度。它的初始值为:若从V到Vi有弧，则Dist [i]为弧上的权值;否则置Dist[i]为无穷大。显然，长度为Dist[i]=Min{Dist[i]|Vi

文章插图
V}的路径就是从V出发的长度最短的一条路径。此路径为(V, V j ) 。一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径(设其终点为X)或者是弧(V, X)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的最短路径的长度为：Dist[i]=Min{Dist[i]|Vi

文章插图
S}，其中Dist[i]或者是弧(V, Vi)上权值，或者是Dist[k] (Vk

文章插图
S)和弧(Vk, 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 不