矢量格式向栅格格式的转换

矢量格式向栅格格式转换又称为多边形填充，就是在矢量表示的多边形边界内部的所有栅格上赋予相应的多边形编号，从而形成栅格数据阵列。

内部点扩散算法：由每个多边形一个内部点(种子点)开始，向其八个方向的邻点扩散，判断各个新加入点是否在多边形边界上，如果是边界点，则新加入点不作为种子点，否则把非边界点的邻点作为新的种子点与原有种子点一起进行新的扩散运算，并将该种子点赋予多边形的编号。重复上述过程，直到所有种子点填满该多边形并遇到边界为止。

扩散算法程序设计比较复杂，需要在栅格阵列中进行搜索，占用内存很大。

复数积分算法：对全部栅格阵列逐个栅格单元判断栅格归属的多边形编码，判别方法是由待判点对每个多边形的封闭边界计算复数积分，对某个多边形，如果积分值为2∏i，则该待判点属于此多边形，赋予多边形编号，否则在此多边形外部。

复数积分算法涉及许多乘除运算，运算时间很长，难以在比较低档次的计算机上采用。

射线算法：逐点判别数据栅格点在某多边形之外或在多边形内，由待判点向图外某点引射线，判断该射线与某多边形所有边界相交的总次数，如相交偶数次，则待判点在该多边形的外部，如为奇数次，则待判点在该多边形内部。

要计算与多边形交点，因此运算量大。

扫描算法：扫描算法是射线算法的改进。

边界代数算法：边界代数多边形填充算法(Boundary Algebra Filling，简称BAF)，是任伏虎等设计并在微机地理信息系统上实现的一种基于积分思想的矢量格式向栅格格式转换算法。其原理如图3-23：



为说明边界代数转换法的原理，先考虑图3—23所示单个多边形的简单情况，模仿积分求多边形区域面积：初始化的栅格阵列各栅格值为零，欲填充多边形编号为a的区域，即将区域内栅格点的值变为a，而区域外各点仍保持原值零。转换时，以栅格行列为参考坐标轴，由多边形边界上某点为起点顺时针搜索边界线，当边界线段为上行时(图3—23(a))，位于搜索边界曲线左侧的具有相同行坐标的所有栅格点被减去一个值a；当边界线段为下行时(图3—23(b))，则将边界曲线左边(从曲线前进方向看为右侧)所有具相同行坐标的栅格点加上一个值a，当沿边界搜索运算一周回到起始点后，所有多边形内部的栅格点都被赋值a，而多边形外的栅格点的值不变。

边界代数法与其它算法的不同之处在于它不是逐点搜寻判别边界，而是根据边界的拓扑信息，通过简单的加减代数运算将拓扑信息动态地赋予各栅格点，实现了矢量格式到栅格格式的转换。算法简单，可靠性好，较少受内存容量的限制，特别适用于微机地理信息系统。

栅格格式向矢量格式的转换

栅格格式向矢量格式转换的目的，是为了将栅格数据分析的结果，通过矢量绘图装置输出，更重要的是为了将自动扫描仪获取的栅格数据加入矢量形式的数据库。

多边形栅格格式向矢量格式转换：就是提取以相同编号的栅格集合表示的多边形区域的边界和边界的拓扑关系，并表示成多个小直线段的矢量格式边界线的过程，包括以下四个基本步骤：

多边形边界提取：采用高通滤波将栅格图像二值化或以特殊值标识边界点；

边界线追踪：对每个边界弧段由一个节点向另一个节点搜索，通常对每个已知边界点需沿除进入方向的其它7个方向搜索下一个边界点，直到连成边界弧段。

拓扑关系生成：对于矢量表示的边界弧段，判断其与原因上各多边形的空间关系，形成完整的拓扑结构，并建立与属性数据的联系。

去除多余点及曲线圆滑：搜索是逐个栅格进行的，必须去除由此造成的多余点记录，以减少数据冗余。曲线由于栅格精度的限制可能不够圆滑，需要采用一定的插补算法进行光滑处理。常用的算法有线性叠代法、分段三次多项式插值法、正轴抛物线平均加权法、斜轴抛物线平均加权法、样条函数插值法等。

栅格向矢量转换中最为困难的是边界线搜索、拓扑结构生成和多余点去除。