GIS算法基础重点要点.pdf
《GIS算法基础重点要点.pdf》由会员分享,可在线阅读,更多相关《GIS算法基础重点要点.pdf(17页珍藏版)》请在三一文库上搜索。
1、一、算法的时间复杂性T(n) :利用某算法处理一个问题规模为n 的 输入所需要的时间。 空间:为了解求问题的实例而执行的计算步骤所需要额内存空间(或 字)数目,不包括用来存储输入的空间。算法空间复杂性不可能超过 运行时间的复杂性。 元运算 : 对于任何计算步骤,不管输入数据或执行的算法,它的代价 总是以一个时间常量为上界, 则称该计算步骤为元运算。 基于比较的 排序问题的最优算法: 我们通常把在 O(nlgn) 时间内用元素比较法排 序的任何算法,称为基于比较的排序问题的最优算法。一般来说,如 果可以证明任何一个求解问题A的算法必定是 (f(n),那么我们把 在 O(f(n)时间内求解任何问题
2、A的任何算法都称为问题A的最优算 法。算法设计原则 :正确性确定性 清晰性。 算法的要素 :1. 待解问 题的描述 2. 算法设计的任务 3. 算法分析。 二、关系运算 :指的是用于检验两个几何对象的特定的拓扑空间关系 的逻辑方法。 两步确定两条线段是否相交:1. 快速排斥实验 (矩形不相交) 2. 跨立 实 验 ( 判 断 线 段P1P2 是 否 和Q1Q2 跨 立 依 据 是 : (P1-Q1)*(Q2-Q1)*(Q2-Q1)*(P2-Q1)=0.)判断 点是否在多边形内 常 用算法:1. 射线法(又叫奇偶测试法) 2. 转角法。线段在多边形内 的 一个重要条件是线段的两个端点都在多边形内
3、,第二个必要条件是线 段和多边形的所有边都不内交。线段在多边形内判断步骤:1. 先求出 所有和线段相交的多边形的顶点2. 然后按照 X-Y 坐标排序(X坐标小 的排在前面,对于X坐标相同的点, Y坐标小的排在前面,这种排序 准则也是为了保证水平和垂直情况的判断正确),这样相邻的两个点 就是在线段上相邻的两交点,如果任意相邻两点的中点也在多边形 内,则该线段一定在多边形内。 计算线段或直线与线段的交点:设一 条线段为 L0=P1P2 ,另一条线段或直线为L1=Q1Q2 ,要计算的就是 L0 和 L1 的交点:第一步:首先判断L0 和 L1 是否相交 2. 若 L1 不平行 与 Y轴,则交点横坐标
4、为 P1的横坐标,代入到 L1的直线方程中可以 计算出交点纵坐标。第三步:若L1 平行于 y 轴,则第四步:若 L0 平 行于 x 轴,有 2 种情况,第五步:若L1 平行于 x 轴,则,第六步: 若 L1 和 L0 斜率均存在,则。 中心点的计算 :多边形的中心点(又叫 质心或重心) 可以通过将多边形分割成为三角形,求取三角形的中心 点,然后将三角形的中心点加权求和取得。三点画圆:算法关键是求 取圆心和园半径:第一步:求取圆心,第二步:求取半径 R, R= ( (xa-xp ) 2+(ya-yp)2 )1/2 。p 是圆心。四、 矢量线栅格化三种方法 :八方 向栅格化、 全路径栅格化、 恒密
5、度栅格化。 矢量面格式向栅格面格式 转换又称为多边形填充, 就是在矢量表示的多边形边界内部的所有栅 格点上赋以相应的多边形编码,从而形成栅格数据阵列。方法有:内 部点扩散算法(种子,八方向扩散) 、射线算法和扫描算法、边界代 数算法(积分、拓扑) 。栅格数据矢量化 有 4 个基本步骤: 1. 边界提 取 2. 边界线追踪 3. 拓扑关系生成 4.去除多余点及曲线圆滑。 细化算 法:栅格数据需要细化,以提取其中轴线,因为:1. 中轴线是栅格数 据曲线的标准化存储形式2. 实现细化是将栅格曲线矢量化的前提3. 在有些算法中可以提高计算精度。细化算法可分两大类 :第一大类是 基于距离变换,首先得到骨
6、架像元,然后跟踪距离变换图中的“山脊 线” ,并将其作为中轴线;第二类是基于在不破坏栅格拓扑连通性的 前提下,按对称的原则删除影像边缘的栅格点。四例:1. 用距离变换 法搜寻中轴线(减细) 2. 最大数值计算法( V值 4、1)3. 经典的细化 算法 4. 边缘跟踪剥皮法 . 多边形栅格转矢量的双边界搜索算法:基本 思想:通过边界提取,将左右多边形信息保存在边界点上,每条边界 弧段由两个并行的边界链组成, 分别记录该边界弧段的左右多边形编 号。具体步骤 :1. 边界点和结点提取2. 边界线搜索与左右多边形信 息记录 3. 多余点去除。 多边形栅格转矢量的单边界搜索算法:单边 界搜索算法时通过对
7、传统的区域跟踪算法进行改进而形成的,传统区 域跟踪算法中,对区域的描述由两部分组成: 区域外轮廓和内部孔洞。 单边界搜索算法流程 :1. 跟踪、搜索第一层所有的区域并记录外轮廓 和内部孔洞信息2. 根据跟踪到的孔洞信息找出下一层中未跟踪过的 区域的外轮廓跟踪起始点 (即找出一个新区域) 3. 跟踪找到的新区域 并记录其外轮廓和内部孔洞信息4. 重复 23 步,直到该层所有区域 都已被跟踪完毕 5 重复 2 到 3 步,直到整幅图像内所有区域都已被跟 踪完毕。五、 道格拉斯 -普克法优点 是具有最小的线性位移,压缩效 果占优,缺点是需对整条曲线完成数字化后方能进行压缩,且计算工 作量较大。 光栏
8、法原理: 它按照预先定义的一个扇形( “喇叭口”) , 根据曲线上各节点是在扇形外还是在扇形内,决定节点是保留还是舍 去。其优点是光栏法不仅算法严密,能按给定阈值保留曲线特征点, 并按时处理,运算量小,占用内存少。链式编码 :多边形边界可定义 为:由某一原点开始并按某些基本方向确定的单位矢量链。(东 0 东 南 1 东北 7)游程长度编码 :游程指相邻同值网格的数量,游程长度 编码结构是逐行将相邻同值的网格合并,并记录合并后网格的值及合 并网格的长度,其目的是压缩栅格数据量,消除数据间的冗余。块式 编码:块式编码是将游程长度编码扩大到二维的情况,把多边形范围 划分成由像元组成的正方形, 然后对
9、各个正方形进行编码。 差分映射 法:就是选择某一参照值对有关栅格的属性值进行求差运算,根据差 值得到一个新的栅格数据层。 (分行选取和全区选取)拓扑关系左转 算法描述如下 :1. 顺序取一个结点作为起始结点,取完为止;取过该 结点的方位角最小的未使用过的或仅使用一次,且使用过的方向与本 次相反的弧段作为起始弧段。 2. 取这条弧段的另一个结点, 找这个结 点关联的弧段集合中的本条弧段的下一条弧段,如果本条弧段是最后 一条弧段,则取弧段集合的第一条弧段,作为下一条弧段。3.判断是 否回到起点,如果是,则形成了一个多边形,记录下它,并且根据弧 段的方向,设置组成该多边形的左右多边形信息;否则转2。
10、4. 取起 始点上开始的,刚才所形成多边形的最后一条边作为新的起始弧段, 转 2;若这条弧段已经使用过两次,即形成了两个多边形,转1。岛 的判断问题算法如下 :1. 计算所有多边形的面积2. 分别对面积为正 的多边形和面积为负的多边形排序,分别形成正多边形和负多边形集 合。3. 如果负多边形集合的个数为1,结束程序;否则,从面积为正 的多边形集合中, 顺序取出一个多边形, 如果正多边形已经都被访问 过,则程序结束。 4. 依次从负多边形集合中取出负多边形,判断当前 取出的正多边形是否包含该多边形,如果包含,就将该负多边形加入 当前取出的正多边形中, 形成复杂多边形, 设置负多边形的组成弧段 的
11、拓扑信息, 并从负多边形集合中删除该负多边形。当所有负多边形 都 被 访 问 一 遍 后 转3. 六 、 直 线 方 程 的 所 有 形 式 : P(t)=P0+tVl=P0+t(P1-P0)=(1-t)P0+tP1。 (y0-y1)x+(x1-x0)y+(x0y1-x1y0)=0。P(t)=(x0+tcos,y0+tsin) 点到直线距离计算公 式 : d(P,L)=(y0-y1)x+(x1-x0)y+(x0y1-x1y0)/(x1-x0)2+(y1-y0 )2)1/2.三 角 形 面 积 计 算 公 式 :A=1/2*bh,A=1/2*absin , A=(s(s-a)(s-b)(s-c)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- GIS 算法 基础 重点 要点
链接地址:https://www.31doc.com/p-5197025.html