GIS算法基础重点要点.pdf

一、算法的时间复杂性 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 是否相交 2. 若 L1 不平行 与 Y 轴，则交点横坐标为 P1 的横坐标，代入到 L1 的直线方程中可以 计算出交点纵坐标。第三步：若 L1 平行于 y 轴，则第四步：若 L0 平 行于 x 轴，有 2 种情况，第五步：若 L1 平行于 x 轴，则，第六步： 若 L1 和 L0 斜率均存在，则。 中心点的计算 ：多边形的中心点（又叫 质心或重心） 可以通过将多边形分割成为三角形， 求取三角形的中心 点，然后将三角形的中心点加权求和取得。三点画圆：算法关键是求 取圆心和园半径： 第一步：求取圆心，第二步：求取半径 R，R=（（xa-xp ） ^2+(ya-yp)^2 ）^1/2 。p 是圆心。四、 矢量线栅格化三种方法 ：八方 向栅格化、 全路径栅格化、 恒