GIS算法基础重点.doc

... ... 一、算法的时间复杂性 T(n) :利用某算法处理一个问题规模为 n的输入所需要的时间。空间: 为了解求问题的实例而执行的计算步骤所需要额内存空间(或字) 数目, 不包括用来存储输入的空间。算法空间复杂性不可能超过运行时间的复杂性。元运算: 对于任何计算步骤,不管输入数据或执行的算法,它的代价总是以一个时间常量为上界, 则称该计算步骤为元运算。基于比较的排序问题的最优算法: 我们通常把在 O(nlgn) 时间内用元素比较法排序的任何算法,称为基于比较的排序问题的最优算法。一般来说,如果可以证明任何一个求解问题 A 的算法必定是Ω(f(n)), 那么我们把在 O(f(n)) 时间内求解任何问题A 的任何算法都称为问题A 的最优算法。算法设计原则: 正确性确定性清晰性。算法的要素: 1. 待解问题的描述 2. 算法设计的任务 3. 算法分析。二、关系运算: 指的是用于检验两个几何对象的特定的拓扑空间关系的逻辑方法。两步确定两条线段是否相交: 1. 快速排斥实验( 矩形不相交) 2. 跨立实验( 判断线段 P1P2 是否和 Q1Q2 跨立依据是: (P1-Q1)*(Q2-Q1)*(Q2-Q1)*(P2-Q1)>=0. ) 判断点是否在多边形内常用算法: 1. 射线法( 又叫奇偶测试法) 2. 转角法。线段在多边形内的一个重要条件是线段的两个端点都在多边形内, 第二个必要条件是线段和多边形的所有边都不内交。线段在多边形内判断步骤: 1. 先求出所有和线段相交的多边形的顶点 2. 然后按照 X-Y 坐标排序(X 坐标小... ... 的排在前面, 对于 X 坐标相同的点,Y 坐标小的排在前面, 这种排序准则也是为了保证水平和垂直情况的判断正确) ,这样相邻的两个点就是在线段上相邻的两交点,如果任意相邻两点的中点也在多边形内, 则该线段一定在多边形内。计算线段或直线与线段的交点: 设一条线段为 L0=P1P2 , 另一条线段或直线为 L1=Q1Q2 , 要计算的就是 L0 和 L1 的交点:第一步:首先判断 L0和 L1 是否相交 L1 不平行与Y轴, 则交点横坐标为 P1 的横坐标, 代入到 L1 的直线方程中可以计算出交点纵坐标。第三步:若 L1 平行于 y轴, 则第四步:若 L0平行于 x 轴,有 2 种情况,第五步:若 L1 平行于 x 轴,则,第六步: 若 L1和 L0 斜率均存在,则。中心点的计算: 多边形的中心点( 又叫质心或重心) 可以通过将多边形分割成为三角形, 求取三角形的中心点, 然后将三角形的中心点加权求和取得。三点画圆: 算法关键是求取圆心和园半径: 第一步: 求取圆心, 第二步: 求取半径 R, R=(( xa-xp ) ^2+(ya-yp)^2 ) ^1/2 。p 是圆心。四、矢量线栅格化三种方法: 八方向栅格化、全路径栅格化、恒密度栅格化。矢量面格式向栅格面格式转换又称为多边形填充, 就是在矢量表示的多边形边界内部的所有栅格点上赋以相应的多边形编码,从而形成栅格数据阵列。方法有:内部点扩散算法(种子,八方向扩散) 、射线算法和扫描算法、边界代数算法(积分、拓扑) 。栅格数据矢量化有4 个基本步骤: 1. 边界提取 2. 边界线追踪 3. 拓扑关系生成 4. 去除多余点及曲线圆滑。细化算法: 栅格数据需要细化, 以提取其中轴线, 因为: 1. 中轴线是栅格数据曲线的标准化存储形式 2. 实现细化是将栅格曲线矢量化的前提 3. ... ... 在有些算法中可以提高计算精度。细化算法可分两大类: 第一大类是基于距离变换, 首先得到骨架像元, 然后跟踪距离变换图中的“山脊线”,并将其作为中轴线;第二类是基于在不破坏栅格拓扑连通性的前提下, 按对称的原则删除影像边缘的栅格点。四例: ( 减细) 2. 最大数值计算法(V值4、1) 3. 经典的细化算法 4. 边缘跟踪剥皮法. 多边形栅格转矢量的双边界搜索算法: 基本思想: 通过边界提取, 将左右多边形信息保存在边界点上, 每条边界弧段由两个并行的边界链组成, 分别记录该边界弧段的左右多边形编号。具体步骤: 1. 边界点和结点提取 2. 边界线搜索与左右多边形信息记录 3. 多余点去除。多边形栅格转矢量的单边界搜索算法: 单边界搜索算法时通过对传统的区域跟踪算法进行改进而形成的, 传统区域跟踪算法中, 对区域的描述由两部分组成: 区域外轮廓和内部孔洞。单边界搜索算法流程: 1. 跟踪、搜索第一层所有的区域并记录外轮廓和内部孔洞信息 2. 根据跟踪到的孔洞信息找出下一层中未跟踪过的区域的外轮廓跟踪起始点( 即找出一个新区域) 3. 跟踪找到的新区域并记录其外轮廓和内部孔洞信息 4. 重复 23 步,直到该层所有区域都已被跟踪