一、算法的时间复杂性T(n):利用某算法处理一个问题规模为n的输入所需要的时间。空间:为了解求问题的实例而执行的计算步骤所需要额内存空间(或字)。算法空间复杂性不可能超过运行时间的复杂性。元运算:。基于比较的排序问题的最优算法:我们通常把在O(nlgn)。(f(n)),那么我们把在O(f(n))时间内求解任何问题A的任何算法都称为问题A的最优算法。算法设计原则:正确性确定性清晰性。算法的要素:。二、关系运算:指的是用于检验两个几何对象的特定的拓扑空间关系的逻辑方法。两步确定两条线段是否相交:(矩形不相交)(判断线段P1P2是否和Q1Q2跨立依据是:(P1-Q1)*(Q2-Q1)*(Q2-Q1)*(P2-Q1)>=0.)判断点是否在多边形内常用算法:(又叫奇偶测试法)。。线段在多边形内判断步骤:-Y坐标排序().。计算线段或直线与线段的交点:设一条线段为L0==:第一步:。第三步::::。中心点的计算:多边形的中心点(又叫质心或重心)。三点画圆:算法关键是求取圆心和园半径:第一步::=((xa-xp)^2+(ya-yp)^2)^1/2。p是圆心。四、矢量线栅格化三种方法:八方向栅格化、全路径栅格化、恒密度栅格化。。方法有:内部点扩散算法()、射线算法和扫描算法、边界代数算法(积分、拓扑)。栅格数据矢量化有4个基本步骤:。细化算法::。细化算法可分两大类:“山脊线”.并将其作为中轴线;。四例:(减细)(V值4、1):基本思想:。具体步骤:。多边形栅格转矢量的单边界搜索算法::区域外轮廓和内部孔洞。单边界搜索算法流程:、(即找出一个新区域)。五、道格拉斯-。光栏法原理:它按照预先定义的一个扇形(“喇叭口”).。。链式编码:多边形边界
gis算法基础重点 来自淘豆网m.daumloan.com转载请标明出处.
