内容发布更新时间 : 2024/11/17 21:49:57星期一 下面是文章的全部内容请认真阅读。
一、算法的时间复杂性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是圆心。四、矢量线栅格化三种方法：八方向栅格化、全路径栅格化、恒密度栅格化。矢量面格式向栅格面格式转换又称为多边形填充，就是在矢量表示的多边形边界内部的所有栅格点上赋以相应的多边形编码，从而形成栅格数据阵列。方法有：内部点扩散算法（种子，八方向扩散）、射线算法和扫描算法、边界代数算法（积分、拓扑）。栅格数据矢量化有4个基本步骤：1.边界提取2.边界线追踪3.拓扑关系生成4.去除多余点及曲线圆滑。细化算法：栅格数据需要细化，以提取其中轴线，因为：1.中轴线是栅格数据曲线的标准化存储形式2.实现细化是将栅格曲线
矢量化的前提3.在有些算法中可以提高计算精度。细化算法可分两大类：第一大类是基于距离变换，首先得到骨架像元，然后跟踪距离变换图中的“山脊线”，并将其作为中轴线；第二类是基于在不破坏栅格拓扑连通性的前提下，按对称的原则删除影像边缘的栅格点。四例：1.用距离变换法搜寻中轴线（减细）2.最大数值计算法（V值4、1）3.经典的细化算法4.边缘跟踪剥皮法.多边形栅格转矢量的双边界搜索算法：基本思想：通过边界提取，将左右多边形信息保存在边界点上，每条边界弧段由两个并行的边界链组成，分别记录该边界弧段的左右多边形编号。具体步骤：1.边界点和结点提取2.边界线搜索与左右多边形信息记录3.多余点去除。多边形栅格转矢量的单边界搜索算法：单边界搜索算法时通过对传统的区域跟踪算法进行改进而形成的，传统区域跟踪算法中，对区域的描述由两部分组成：区域外轮廓和内部孔洞。单边界搜索算法流程：1.跟踪、搜索第一层所有的区域并记录外轮廓和内部孔洞信息2.根据跟踪到的孔洞信息找出下一层中未跟踪过的区域的外轮廓跟踪起始点（即找出一个新区域）3.跟踪找到的新区域并记录其外轮廓和内部孔洞信息4.重复23步，直到 该层所有区域都已被跟踪完毕5重复2到3步，直到整幅图像内所有区域都已被跟踪完毕。五、道格拉斯-普克法优点是具有最小的线性位移，压缩效果占优，缺点是需对整条曲线完成数字化后方能进行压缩，且计算工作量较大。光栏法原理：它按照预先定义的一个扇形（“喇叭口”），根据曲线上各节点是在扇形外还是在扇形内，决定节点是保留还是舍去。其优点是光栏法不仅算法严密，能按给定阈值保留曲线
特征点，并按时处理，运算量小，占用内存少。链式编码：多边形边界可定义为：由某一原点开始并按某些基本方向确定的单位矢量链。（东0东南1东北7）游程长度编码：游程指相邻同值网格的数量，游程长度编码结构是逐行将相邻同值的网格合并，并记录合并后网格的值及合并网格的长度，其目的是压缩栅格数据量，消除数据间的冗余。块式编码：块式编码是将游程长度编码扩大到二维的情况，把多边形范围划分成由像元组成的正方形，然后对各个正方形进行编码。差分映射法：就是选择某一参照值对有关栅格的属性值进行求差运算，根据差值得到一个新的栅格数据层。（分行选取和全区选取）拓扑关系左转算法描述如下：1.顺序取一个结点作为起始结点，取完为止；取过该结点的方位角最小的未使用过的或仅使用一次，且使用过的方向与本次相反的弧段作为起始弧段。2.取这条弧段的另一个结点，找这个结点关联的弧段集合中的本条弧段的下一条弧段，如果本条弧段是最后一条弧段，则取弧段集合的第一条弧段，作为下一条弧段。3.判断是否回到起点，如果是，则形成了一个多边形，记录下它，并且根据弧段的方向，设置组成该多边形的左右多边形信息；否则转2。4.取起始点上开始的，刚才所形成多边形的最后一条边作为新的起始弧段，转2；若这条弧段已经使用过两次，即形成了两个多边形，转1。岛的判断问题算法如下：1.计算所有多边形的面积2.分别对面积为正的多边形和面积为负的多边形排序，分别形成正多边形和负多边形集合。3.如果负多边形集合的个数为1，结束程序；否则，从面积为正的多边形集合中，顺序取出一个多边形，如果正多边形已经都
被访问过，则程序结束。4.依次从负多边形集合中取出负多边形，判断当前取出的正多边形是否包含该多边形，如果包含，就将该负多边形加入当前取出的正多边形中，形成复杂多边形，设置负多边形的组成弧段的拓扑信息，并从负多边形集合中删除该负多边形。当所有负多边形都被访问一遍后转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))1/2,s=1/2*(a+b+c),A=1/4*(4a2b2-(a2+b2-c2)2)1/2，A=b2/2(cot
Θ
+cot
β
）
。
A=1/2|v*w|=1/2|(v1-v0)(v2-v0)|,2A=(x1-x0)(y2-y0)-(x2-x0)(y1-y0)。四边形面积计算公式：A=((s-a)(s-b)(s-c)(s-d))1/2，A(v0v1v2v3)=|(v1-v0)*(v3-v0)|，A=(x1-x0)(y3-y0)-(x3-x0)(y1-y0)，A=1/2|(v2-v0)*(v3-v1)|，2A=(x2-x0)(y3-y1)-(x3-x1)(y2-y0)。任意二维平面多边形面积计算方法与公式：A
多边形=ΣA(Δi),Δi=ΔPViVi+1，注
意：对于一个逆时针多边形，当点P在边ViVi+1的左边，则Δi的面积是正的；相反，当点P在边ViVi+1的右边，并且位于多边形外部，则Δi的面积是负的。如果是一个顺时针多边形，则符号相反，并且内部的三角形面积为负的。七、空间索引：就是指依据空间对象的位置和形状或空间对象之间的某种空间关系，按一定的顺序排列的一种数据