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

矢量格式向栅格格式转换又称为多边形填充，就是在矢量表示的多边形边界内部的所有栅格点上赋以相应的多边形编码，从而形成类似图7-4的栅格数据阵列。几种主要的算法描述如下：

1）内部点扩散算法

该算法由每个多边形一个内部点（种子点）开始，向其八个方向的邻点扩散，判断各个新加入点是否在多边形边界上，如果是边界上，则该新加入点不作为种子点，否则把非边界点的邻点作为新的种子点与原有种子点一起进行新的扩散运算，并将该种子点赋以该多边形的编号。重复上述过程直到所有种子点填满该多边形并遇到边界停止为止。扩散算法程序设计比较复杂，并且在一定的栅格精度上，如果复杂图形的同一多边形的两条边界落在同一个或相邻的两个栅格内，会造成多边形不连通，这样一个种子点不能完成整个多边形的填充。

2）复数积分算法

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

3）射线算法和扫描算法

射线算法可逐点判断数据栅格点在某多边形之外或在多边形内，由待判点向图外某点引射线，判断该射线与某多边形所有边界相交的总次数，如相交偶数次，则待判点在该多边形外部，如为奇数次，则待判点在该多边形内部（图7-12）。采用射线算法，要注意的是：射线与多边形边界相交时，有一些特殊情况会影响交点的个数，必须予以排除（图7-13）。

扫描算法是射线算法的改进，将射线改为沿栅格阵列列或行方向扫描线，判断与射线算法相似。扫描算法省去了计算射线与多边形边界交点的大量运算，大大提高了效率。

4）边界代数算法（BAF-Boundary Algebra Filling）[任伏虎]

边界代数多边形填充算法是一种基于积分思想的矢量格式向栅格格式转换算法，它适合于记录拓扑关系的多边形矢量数据转换为栅格结构。图7-15表示转换单个多边形的情况，多边形编号为a，模仿积分求多边形区域面积的过程，初始化的栅格阵列各栅格值为零，以栅格行列为参考坐标轴，由多边形边界上某点开始顺时针搜索边界线，当边界上行时（图7-15-a），位于该边界左侧的具有相同行坐标的所有栅格被减去a；当边界下行时（图7-15-b），该边界左边（前进方向看为右侧）所有栅格点加一个值a，边界搜索完毕则完成了多边形的转换。

图7-15：单个多边形的转换

事实上，每幅数字地图都是由多个多边形区域组成的，如果把不属于任何多边形的区域（包含无穷远点的区域）看成编号为零的特殊的多边形区域，则图上每一条边界弧段都与两个不同编号的多边形相邻，按弧段的前进方向分别称为左、右多边形，可以证明，对于这种多个多边形的矢量向栅格转换问题，只需对所有多边形边界弧段作如下运算而不考虑排列次序：当边界弧段上行时，该弧段与左图框之间栅格增加一个值（左多边形编号减去右多边形编号）；当边界弧段下行时，该弧段与左图框之间栅格增加一个值（右多边形编号减去左多边形编号）。两个多边形转换过程如图7-16所示。

边界代数法与前述其他算法的不同之处，在于它不是逐点判断与边界的关系完成转换，而是根据边界的拓扑信息，通过简单的加减代数运算将边界位置信息动态地赋给各栅格点，实现了矢量格式到栅格格式的高速转换，而不需要考虑边界与搜索轨迹之间的关系，因此算法简单、可靠性好，各边界弧段只被搜索一次，避免了重复计算。

但是这并不意味着边界代数法可以完全替代其它算法，在某些场合下，还是要采用种子填充算法和射线算法，前者应用于在栅格图像上提取特定的区域；后者则可以进行点和多边形关系的判断。

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

多边形栅格格式向矢量格式转换就是提取以相同的编号的栅格集合表示的多边形区域的边界和边界的拓扑关系，并表示由多个小直线段组成的矢量格式边界线的过程。

1）步骤

栅格格式向矢量格式转换通常包括以下四个基本步骤：

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

（1．2）边界线追踪：对每个边界弧段由一个结点向另一个结点搜索，通常对每个已知边界点需沿除了进入方向的其他7个方向搜索下一个边界点，直到连成边界弧段；

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

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

2）多边形栅格转矢量的双边界搜索算法（DBDF-Double Boundary Direct Finding）

算法的基本思想是通过边界提取，将左右多边形信息保存在边界点上，每条边界弧段由两个并行的边界链组成，分别记录该边界弧段的左右多边形编号。边界线搜索采用2*2栅格窗口，在每个窗口内的四个栅格数据的模式，可以唯一地确定下一个窗口的搜索方向和该弧段的拓扑关系，极大地加快了搜索速度，拓扑关系也很容易建立。具体步骤如下：

（2．1）边界点和结点提取：采用2*2栅格阵列作为窗口顺序沿行、列方向对栅格图像全图扫描，如果窗口内四个栅格有且仅有两个不同的编号，则该四个栅格表示为边界点；如果窗口内四个栅格有三个以上不同编号，则标识为结点（即不同边界弧段的交汇点），保持各栅格原多边形编号信息。对于对角线上栅格两两相同的情况，由于造成了多边形的不连通，也当作结点处理。图7-17和图7-18给出了节点和边界点的各种情形。

（2．2）边界线搜索与左右多边形信息记录：边界线搜索是逐个弧段进行的，对每个弧段由一组已标识的四个结点开始，选定与之相邻的任意一组四个边界点和结点都必定属于某一窗口的四个标识点之一。首先记录开始边界点的两个多边形编号，作为该弧段的左右多边形，下一点组的搜索方向则由进入当前点的搜索方向和该点组的可能走向决定，每个边界点组只能有两个走向，一个是前点组进入的方向，另一个则可确定为将要搜索后续点组的方向。例如图7-18（c）所示边界点组只可能有两个方向，即下方和右方，如果该边界点组由其下方的一点组被搜索到，则其后续点组一定在其右方；反之，如果该点在其右方的点组之后被搜索到（即该弧段的左右多边形编号分别为b和a），对其后续点组的搜索应确定为下方，其他情况依此类推。可见双边界结构可以唯一地确定搜索方向，从而大大地减少搜索时间，同时形成的矢量结构带有左右多边形编号信息，容易建立拓扑结构和与属性数据的联系，提高转换的效率。

（2．3）多余点去除：多余点的去除基于如下思想：在一个边界弧段上的连续的三个点，如果在一定程度上可以认为在一条直线上（满足直线方程），则三个点中间一点可以被认为上多余的，予以去除。多余点是由于栅格向矢量转换时逐点搜索边界造成的（当边界为直线时），多余点去除算法可大量去除多余点，减少数据冗余。