GIS算法_.docx

GIS算法_根据教师PPT非常粗略整理出来的，还有未涉及到的重点大家本人增加第一章算法是一系列解决问题的明晰指令，也就是讲，能够对一定规范的输入，在有限时间内获得所要求的输出算法特性：有穷性、确定性、可行性、有输入、有输出。算法设计的原则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=TDIM(C)0,1,2,即交集C包含有点、线、面;2)P=FDIM(C)=-1,即交集C为空;3)P=*DIM(C)-1,0,1,2,即两目的交集既有点、线、面,又含有某些部分的交为空的情形,该情况在关系判别时,一般不予以考虑;4)P=0DIM(C)=0;5)P=1DIM(C)=1;6)P=2DIM(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对于有公共端点的线段p0p1和p1p2，通过计算(p2-p0)×(p1-p0)的符号便能够确定折线段的拐向：(1)若(p2-p0)×(p1-p0)>0,则p0p1在p1点拐向右侧后得到p1p2。(2)若(p2-p0)×(p1-p0)第六章形状量算：几个指标形状比(FORMRATIO)形状比=A/L2其中，A为区域面积，L为区域最长轴的长度。该指标能反映城市的带状特征，城市的带状特征越明显则形状比越小。显然，假如城市为狭长带状分布，其长轴两端的联络是不便捷的。伸延率(ELONGATIONRATIO)伸延率=L/L式中，L为区域最长轴长度，L为区域最短轴长度。该指标反映城市的带状延伸程度，带状延伸越明显则延伸率越大，反映城市的离散程度越大。紧凑度(COMPACTNESSRATIO)紧凑度有三个不同的计算公式。公式1：紧凑度=其中，A为面积，P为周长。该指标反映城市的紧凑程度，其中圆形区域被以为最紧凑，紧凑度为1。其它形状的区域，其离散程度越大则紧凑度越低。公式2：紧凑度指数=A/A其中，A为区域面积，A为该区域最小外接圆面积。该指标同样以为圆形区域最紧凑，其紧凑度为1。在计算中采用最小外接圆面积作为衡量城市形状的标准。公式3：紧凑度=1.273A/L2其中，L为最长轴长度，A为区域面积。该指标也以为圆形为标准形状，但它只考虑最长轴长度，只能概略地反映城市形状。放射状指数(RADIALSHAPEINDEX)放射状指数有两个不同的计算公式，较常使用的计算公式为：放射状指数=式中，di是城市中心到第i地段或小区中心的距离，n为地段或小区数量。这一指标不单纯是从抽象的形状入手，而是综合了城市内部各小区的位置特征。通过距离能够结合时间、阻力等线路因素反映城市中心与区内各部分之间的详细联络。标准面积指数式中：S为标准面积指数；A为区域面积；As为与区域面积相等的等边三角形面积。该指标把等边三角形作为标准形状。计算时，先换算出等边三角形，把等边三角形叠置在区域范围上，求出区域范围与等边三角形的交与并的面积，计算交与并的面积的比值S，0第七章空间索引是指根据空间要素的地理位置、形状或空间对象之间的某种空间关系，按一定的顺序排列的一种数据构造，一般包括空间要素标识，外包络矩形以及指向空间要素的指针。2.空间索引的作用为了GIS系统中快速定位到所选中的空间要素，进而提高空间操作的速度和效率。空间索引的技术和方法是GIS关键技术之一，是快速高效的查询、检索和显示地理空间数据的重要指标，他的优劣直接影响空间数据库和GIS系统的整体性能。空间索引就是指根据空间对象的位置和形状或空间对象之间的某种空间关系按一定的顺序排列的一种数据构造，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指针。作为一种辅助性的空间数据构造，空间索引介于空间操作算法和空间对象之间，它通过挑选作用，大量与特定空间操作无关的空间对象被排除，进而提高空间操作的速度和效率。空间索引的性能的优劣直接影响空间数据库和地理信息系统的整体性能，它是空间数据库和地理信息系统的一项关键技术。缓冲区分析矢量边界生成算法角平分线法和凸角圆弧法参见（地理信息算法基础）P188、P193自相交多边形分为两种情况：岛屿多边形和重叠多边形。岛屿多边形是缓冲区边线的有效组成部分；重叠多边形不是缓冲区边线的有效组成，不介入缓冲区边线的最终重构。对于岛屿多边形和重叠多边形的自动判别方法：1首先定义轴线坐标点序为其方向，缓冲区双线分成左右边线，左右边线自相交多边形的判别情形恰好对称。2对于左边线，岛屿自相交多边形呈逆时针方向，重叠自相交多边形呈顺时针方向；对于右边线，岛屿多边形呈顺时针方向，重叠多边形呈逆时针方向。3当存在岛屿和重叠自相交多边形时，最终计算的边线被分为外部边线和若干岛屿。对于缓冲区边线绘制，只要把外围边线和岛屿轮廓绘出即可。对于缓冲区检索，在外边线所形成的多边形检索后，要再扣除所有岛屿多边形的检索结果。注意下列图边界方向第十一章Dijkstra算法参考（地理信息系统原理）详解第十三章数据挖掘，又称为数据库中知识发现KnowledgeDiscoveryinDatabases或知识发现，它是一个从大量数据中抽取挖掘出未知的、有价值的形式或规律等知识的非平凡经过，它与数据仓库有着密切的联络。数据挖掘是从存放在数据集中的大量数据挖掘出有趣知识的经过。数据挖掘的步骤1数据清理消除噪音或不一致数据，补缺；2数据集成多种数据源能够组合在一起；3数据选择从数据库中提取相关的数据；4数据变换变换成合适挖掘的形式；5数据挖掘使用智能方法提取数据形式；6形式评估识别提供知识的真正有趣形式；7知识表示可视化和知识表示技术。空间数据挖掘和普通数据挖掘的区别？