结构，其中包括空间对象的概要信息。B树的定义：一个m阶的B树，或为空树，或是为满足下列特征的m叉树。（1）树中每个结点至多有m棵子树；（2）若根结点不是叶子结点，则至少有两颗子树；（3）除根之外的所有非终端结点至少有[m/2]棵子树；（4）所有的非叶

结

点

中

包

含

下

列

信

息

数

据

：

（A0,,,...,Kn,An,Dn>）式中Ki(i=1,2…n)为关键字，且Ki称为结点的一个元素。（5）所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点查询失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。

插入算法：设将元素插入B树中。（1）首先在树中查找K，若查找到，算法结束（假定B树中不容许有相同的关键字存在）。若没有查到，设最后查到的结点为N。将关键字K插入结点N中，若结点N的元素的个数小于等于m-1，将A指向叶结点，插入结束，若结点N的元素关键字的个数为m，则需分裂结点N。（2）设插入关

键

字

K

后

的

结

点

情

况

如

下

：

（A0,,….）创建一新结点L，将N中的第[m/2 +1]以及其后的所有元素，共m-[m/2]个元素移入新结点L中。再将元素移出N，插入结点N的父结点。N的父结点还可能需要分裂，最坏的情况是分裂一直延续到根结点，

最后产生新的根结点，树高增加1。当插入操作引起了s个结点的分裂时，磁盘访问的次数为h（读取搜索路径上的结点）+2s（回写两个分裂出的新结点）+1（回写新的根结点或插入后没有导致分裂的结点）。因此，所需要的磁盘访问次数是h+2s+1，最多可达3h+1。 R树的定义:设M为结点中单元的最大数目，m（1<=m<=M/2）为非根结点中单元个数的下限。（1）每个叶子结点包含的单元个数介于m与M之间，除非它同时是根结点。（2）每个叶子结点中的单元（I,SpatialObjectID）中，I是包含该n维空间对象的MBR，SpatialObjectID是该空间对象的ID。（3）每个非叶子结点的子结点树介于m到M之间，除非它同时是跟结点。（4）每个非叶子的结点的单元（I，PointerToChild）中，I是包含子结点的MBR，PointerToChild是指向子结点的指针。通过该指针能访问到子结点。（5）根结点最少有两个字结点，除非它同时是叶子的结点。（6）所有的叶子结点都处于树的同一层上。

插入算法：新空间对象的插入操作：（1）为新的空间对象，寻找一个合适的叶子结点（2）将新的空间对象记录到叶子的结点中，（3）调整树的结构（4）生成新的根结点。选择合适的叶子结点：（1）初始化（2）判断是否为叶子结点（3）选择合适的子树。调整树的结构：（1）初始化（2）判断是否是根结点（3）调整父结点相应单元的I（4）根据需要进一步分裂父结点。常规四叉树缺点：所占的内外存空间比较大，原因在于它不仅要记录每个结点值，还需记录结点的一个前趋结点及四个后继结点，以反映结点之间的联系。对栅格数据进

行运算时，还要作遍历树结点的运算。这样就增加了操作的复杂性。线性四叉树的基本思想和优缺点：线性四叉树不像常规四叉树那样存储树中各个结点及其相互间关系，而是通过编码四叉树的叶结点来表示数据块的层次和空间关系。叶结点都具有一个反映位置的关键字，亦称位置码，表示它所处位置。实质是把原来大小相等的栅格集合转变成大小不等的正方形集合，并对不同尺寸和位置的正方形集合赋予一个位置码。缺点：位置码的位数决定分割的层数，图形越复杂，分割的层数越多，相应的位置码得位数亦越多，这种自上而下的分割方法需要大量重复运算，效率比较低。线性四又树的编码方法：基于深度和层次码的线性四叉树编码；基于四进制的线性四叉树编码；四叉树的十进制编码。

的概念：指的是完成一个任务所需要的具体步骤和方法。常用的算法有穷举搜索法，递归法，回溯法，贪心法，分治法。算法设计的原则：正确性，确定性，清晰性。时间复杂性：去除了表示算法运行时间的函数中的低阶项和首项系数，就称度量算法的渐进运行时间。空间复杂性：为了求解问题实例而执行的计算步骤所需要的内存空间数目，它不包括分配用来存储输入的空间.元运算：对于任何计算步骤，他的代价是以一个时间常量为上界，而不管输入数据或执行的算法，这个计算步骤叫做元运算。（算术，比较，逻辑，赋值）最优算法：如果可以证明任何一个求解的问题A的算法必定是Ω（f（n）），那么我

们把在o（f（n））时间内求解问题A的任何算法都称为问题A的最优算法。关系运算是指用于检验两个几何对象的特定的拓扑空间关系的逻辑方法。判断两直线相交：1）快速排斥实验，设以线段p1p2，Q1Q2为对角线的矩形不想交，则两线段不相交。2）跨立实验如果两个线段相交，则一定跨立对方运用矢量乘法乘积小于零则位于两边。判断点是不是在多边形内1）射线法，一条射线从点P开始，穿过多边形的边界的次数成为交点数目，当交点数目为偶数时，点在多边形外部，不然在内部。2）转角发，多边形环绕点P的次数成为环绕数，环绕数为零，在多边形外部，不然在内部。判断线段是不是在多边形内：线段在多边形内的必要条件是两个端点都在多边形内，线段和多边形的所有边都不内交。如果多边形的一个顶点和线段相交，还必须判断两个相邻交点之间的线段是不是包含与多边形内部。计算线段或直线与线段的交点：第一步判断两条线是不是相交，如果不像交，没有交点。第二到第五步分别判断平行与X,Y轴的情况。第六步两条线斜率都存在并且不为零。

中心点的计算：重心（分割三角形，加权求的，权重为三角形面积站的多边形面积比例）三点画圆：求圆心P，求取圆的半径。栅格数据向矢量格式的转换步骤：1）边界提取，采用高通滤波将栅格图像二值化或者以特殊值标识边界点。2）边界线追踪，对每个边界弧段由一个结点向另一个结点搜索，通常对每个已知边界点需沿除了进入方向的其他七个方向搜索下一个边界，直到连成边界弧段。3）拓扑关系生成，对于矢量表示得边界弧段数据，判断其与原图上各多边形的

空间关系，以形成完整的拓扑结构并建立与属性数据的联系。4）去除多余点及曲线圆滑，由于搜索是逐个栅格进行的，必须去除由此造成的多余点记录，以减少数据繁杂，搜索结果，曲线由于栅格精度的限制可能不够圆滑，需要采用一定的插补算法进行光滑处理，常用的算法有线性迭代法，分段三次多项式插值法，正轴抛物线平均加权法。斜轴抛物线平均加权法，样条函数插值法。多边形栅格转矢量的双边界搜索算法：思想是通过边界提取，将左右多边形信息保存在边界点上，每条边界弧段甴两个并行的边界链组成，分别记录该边界弧段的左右多边形编号。边界线搜索采用2*2的栅格窗口，在每个窗口内4个栅格数据的模式，可以唯一地确定下一个窗口的搜索方向和该弧段的拓扑关系，极大的加快了搜索速度，拓扑关系也很容易建立，步骤（1）边界点和结点提取2）边界线搜索与左右多边形信息记录3）多余点去除。单边界搜索算法：对区域的描述由两部分组成，区域外轮廓和内部孔洞，确定外轮廓跟踪起始点，对区域的外轮廓进行跟踪和记录，对区域内部的所有孔洞进行扫描跟踪和记录。将图像中的所有区域按包含关系分为若干层，每一层至少包含一个区域对象，流程：1搜索跟踪第一层所有的区域并记录外轮廓和内部孔洞信息；2根据跟踪到的空孔洞信息找出下一层中未跟踪过的区域的外轮廓跟踪起始点；3跟踪找到的新区域并记录其外轮廓和内部孔洞信息4重复2，3步直到该层所有区域都已被跟踪完毕5重复2-4步知道整幅图像内所有区域都已被跟踪完毕。拓扑关系生成过程：1弧段处理，使整幅图形中的所有弧段，除在端点处相交外没有其他交点，即没有相交或自