GIS算法

算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出

算法特性：有穷性、确定性、可行性、有输入、有输出。 算法设计的原则

1.正确性：是指对于一个问题，之所以将其放在第一位是因为如果一个算法自身有缺陷，或者不适合于问题的求解，那么该算法将不会解决问题。

2.确定性：是指算法的每个步骤必须含义明确，对每种可能的情况，算法都能给出确定的操作。即采用同一种算法，在同样的条件下无论计算多少次，始终能够得到确定的结果。 3.清晰性：一个良好的算法必须思路清晰，结构合理。算法的设计要模块化。模块化的目的是使算法结构清晰，容易阅读，容易理解，容易测试，容易修改。

时间复杂度：假如，随着问题规模 n 的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：T(n)=O(f(n))称T(n)为算法的(渐近)时间复杂度。 空间复杂度：算法在运行过程中临时占用的存储空间的大小被定义为算法的空间复杂性。空间复杂性包括程序中的变量、过程或函数中的局部变量等所占用的存储空间以及系统为了实现递归所使用的堆栈两部分。算法的空间复杂性一般也以数量级的形式给出。

第二章 九交模型

设有现实世界中的两个简单实体A、B,B(A)、B(B)表示A、B的边界,I(A)、I(B)表示A、B的内部,E(A)、E(B)表示A、B外部。

dim(dimension) 的返回值：有 -1 ， 0 ， 1 ， 2.

• T: 交集存在， dim=0 ， 1 或 2 ； • F: 交集不存在， dim=-1 ；

• 0: 交集存在，但其最高维度必须是 0 ； • 1: 交集存在，但其最高维度必须为 1 ； • 2: 交集存在，但其最高维度必须为 2 ；

运用维数扩展法,将9IM进行扩展,利用点、线、面的边界、内部、余之间的交集的维数来作为空间关系描述的框架。对于几何实体的边界,它是比其更低一维的几何实体的集合。为此,点的边界为空集;线的边界为线的两个端点,当线为闭曲线时,线的边界为空;面的边界由构成面的所有线构成。

扩展结果

根据DE-9IM,对于点集拓扑空间X,当需要进行关系判别时,可对矩阵的9元取值进行分析、比较。令C为各单元交的点集,其取值P可能为｛T,F,*,0,1,2｝。各个取值的具体含义为： 1)P=T DIM(C)∈｛0,1,2｝,即交集C包含有点、线、面; 2)P=F DIM(C)=-1,即交集C为空;

3)P=* DIM(C)∈｛-1,0,1,2｝,即两目标交集既有点、线、面,又含有某些部分的交为空的情形,该情况在关系判别时,一般不予以考虑; 4)P=0 DIM(C)=0; 5)P=1 DIM(C)=1; 6)P=2 DIM(C)=2。

5种基本的空间关系:相离关系(Disjoint)、相接关系(Touch)、相交关系(Cross)、真包含关系(Within)、叠置关系(Overlap),并将这5种关系定义为空间关系的最小集,其特征为: 1) 相互之间不能进行转化; 2) 能覆盖所有的空间关系模式;

3) 能应用于同维与不同维的几何目标; 4) 每一种关系对应于唯一的DE-9IM矩阵;

5) 任何其它的DE-9IM关系可以通过用这5种基本关系进行表达。

第二章 矢量叉积

设二维矢量P=（x1,y1），Q=(x2,y2),则矢量叉积定义为：

由(0,0) 、P、Q和PQ所组成的平行四边形的带符号的面积，即：P×Q=x1·y2-x2·y1 其结果是一个标量。显然有性质：

P×Q=-(Q×P)和P×（-Q）=-(P×Q)

叉积的一个非常重要的性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系： (1)若P×Q > 0，则P在Q的顺时针方向； (2)若P×Q < 0，则P在Q的逆时针方向；

(3)若P×Q = 0，则P与Q共线，但可能同向也可能反向。 折线段的拐向判断方法可以直接由矢量叉积的性质推出。

对于有公共端点的线段p0p1和p1p2，通过计算(p2 - p0)×(p1 - p0) 的符号便可以确定折线段的拐向：

(1)若(p2 - p0) × (p1 - p0) > 0,则p0p1在p1点拐向右侧后得到p1p2。 (2)若(p2 - p0) × (p1 - p0) < 0,则p0p1在p1点拐向左侧后得到p1p2。 (3)若(p2 - p0) × (p1 - p0) = 0,则p0、p1、p2三点共线。 具体情况可参考下图：

判断点是否在多边形内参见书本P25射线法和转角法

第三章

地图投影变换的实质是建立两平场之间的一一对应关系。

实现一种地图投影点的坐标变换为另一种地图投影点的坐标就是要找出上述关系式的方法有：解析变换法、数值变换法、数值解析变换法 解析变换法：反解变换法和正解变换法

反解变换法（又称间接变换法）是一种中间过渡的方法，即先解出原地图投影点的地理坐标X、Y，对于x、y的解析关系式，将其代入新图的投影公式中求得其坐标。

正解变换法（又称直接变换法）是一种不需要反解出原地图投影点的地理坐标的解析公式，而是直接求出两种投影点的直角坐标关系式。

第五章数据组织算法（书本P91） 道格拉斯—普克法

基本思路是：对每一条曲线的首末点虚连一条直线，求所有点与直线的距离，并找出最大距离值dmax，用dmax与限差D相比：

若dmax＜D，这条曲线上的中间点全部舍去；

若dmax≥D，保留dmax对应的坐标点，并以该点为界，把曲线分为 两部分，对这两部分重复使用该方法。

第六章

形状量算：几个指标 形状比(FORM RATIO) 形状比=A/L2

其中，A为区域面积，L为区域最长轴的长度。

该指标能反映城市的带状特征，城市的带状特征越明显则形状比越小。显然，如果城市为狭长带状分布，其长轴两端的联系是不便捷的。 伸延率(ELONGATION RATIO) 伸延率=L/ L’

式中，L为区域最长轴长度，L’为区域最短轴长度。 该指标反映城市的带状延伸程度，带状延伸越明显则延伸率越大，反映城市的离散程度越大。

紧凑度(COMPACTNESS RATIO) 紧凑度有三个不同的计算公式。 公式1： 紧凑度= 2A/P 其中，A为面积，P为周长。

该指标反映城市的紧凑程度，其中圆形区域被认为最紧凑，紧凑度为1。其它形状的区域，其离散程度越大则紧凑度越低。 公式2： 紧凑度指数=A/A’

其中，A为区域面积，A’为该区域最小外接圆面积。该指标同样认为圆形区域最紧凑，其紧凑度为1。在计算中采用最小外接圆面积作为衡量城市形状的标准。 公式3： 紧凑度=1.273A/L2

其中，L为最长轴长度，A为区域面积。该指标也认为圆形为标准形状，但它只考虑最长轴长度，只能概略地反映城市形状。 放射状指数(RADIAL SHAPE INDEX)

放射状指数有两个不同的计算公式，较常使用的计算公式为： 放射状指数=

|(100d/d)(100/n)|iii1i1nn 式中，di 是城市中心到第i地段或小区中心的距离，n为地段或小区数量。

这一指标不单纯是从抽象的形状入手，而是综合了城市内部各小区的位置特征。通过距

离（可以结合时间、阻力等线路因素）反映城市中心与区内各部分之间的具体联系。 标准面积指数

AAs SAAs

式中：S为标准面积指数；A为区域面积；As为与区域面积相等的等边三角形面积。

该指标把等边三角形作为标准形状。计算时，先换算出等边三角形，把等边三角形叠置在区域范围上，求出区域范围与等边三角形的交与并的面积，计算交与并的面积的比值S，0标准面积指数能反映城市形状的破碎程度。城市形状越破碎，则其与等边三角形的交集越小而并集越大，所以其比值越小。不过，通常认为圆才是真正的紧凑形状，而并不是等边三角形。 面积量算

第七章

空间索引是指根据空间要素的地理位置、形状或空间对象之间的某种空间关系，按一定的顺序排列的一种数据结构，一般包括空间要素标识，外包络矩形以及指向空间要素的指针。 2.空间索引的作用

为了GIS系统中快速定位到所选中的空间要素，从而提高空间操作的速度和效率。

空间索引的技术和方法是GIS关键技术之一，是快速高效的查询、检索和显示地理空间数据的重要指标，他的优劣直接影响空间数据库和GIS系统的整体性能。

空间索引就是指依据空间对象的位置和形状或空间对象之间的某种空间关系按一定的顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指针。

作为一种辅助性的空间数据结构，空间索引介于空间操作算法和空间对象之间，它通过筛选作用，大量与特定空间操作无关的空间对象被排除，从而提高空间操作的速度和效率。空间索引的性能的优劣直接影响空间数据库和地理信息系统的整体性能，它是空间数据库和地理信息系统的一项关键技术。

缓冲区分析（矢量）

边界生成算法（角平分线法和凸角圆弧法） 参见《地理信息算法基础》P188、P193

自相交多边形分为两种情况：岛屿多边形和重叠多边形。 岛屿多边形是缓冲区边线的有效组成部分；重叠多边形不是缓 冲区边线的有效组成，不参与缓冲区边线的最终重构。 对于岛屿多边形和重叠多边形的自动判别方法：

（1）首先定义轴线坐标点序为其方向，缓冲区双线分成左右边线，左右边线自相交多边形的判别情形恰好对称。

（2）对于左边线，岛屿自相交多边形呈逆时针方向，重叠自相交多边形呈顺时针方向；对于右边线，岛屿多边形呈顺时针方向，重叠多边形呈逆时针方向。

（3）当存在岛屿和重叠自相交多边形时，最终计算的边线被分为外部边线和若干岛屿。对于缓冲区边线绘制，只要把外围边线和岛屿轮廓绘出即可。对于缓冲区检索，在外边线所形

成的多边形检索后，要再扣除所有岛屿多边形的检索结果。（注意下图边界方向）

第十一章

Dijkstra算法参考《地理信息系统原理》详解

第十三章

数据挖掘，又称为数据库中知识发现（Knowledge Discovery in Databases）或知识发现，它是一个从大量数据中抽取挖掘出未知的、有价值的模式或规律等知识的非平凡过程，它与数据仓库有着密切的联系。

数据挖掘是从存放在数据集中的大量数据挖掘出有趣知识的过程。

数据挖掘的步骤

（1）数据清理（消除噪音或不一致数据，补缺）； （2）数据集成（多种数据源可以组合在一起）； （3）数据选择（从数据库中提取相关的数据）； （4）数据变换（变换成适合挖掘的形式）； （5）数据挖掘（使用智能方法提取数据模式）； （6）模式评估（识别提供知识的真正有趣模式）； （7）知识表示（可视化和知识表示技术）。 空间数据挖掘和普通数据挖掘的区别？？？