（一）矢量格式向栅格格式转换

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

1. 内部点扩散算法；该算法由每个多边形一个内部点（种子点）开始， 向其八个方向的邻点扩散，判断各个新加入点是否在多边形边界上，如果是

边界点，则新加入点不作为种子点，否则把非边界点的邻点作为新的种子点与原有种子点一起进行新的扩散运算，并将该种子点赋予多边形的编号。重复上述过程，直到所有种子点填满该多边形并遇到边界为止。

扩散算法程序设计比较复杂，需要在栅格阵列中进行搜索，占用内存很大。在一定栅格精度上，如果复杂图形的同一多边形的两条边界落在同一个或相邻的两个栅格内，会造成多边形不连通，则一个种子点不能完成整个多边形的填充。

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

复数积分算法涉及许多乘除运算，尽管可靠性好，设计也并不复杂，但运算时间很长，难以在比较低档次的计算机上采用。采用一些优化方法，如根据多边形边界坐标的最大最小值范围组成的矩形来判断是否需要做复数积分运算，可以部分地改善运算时间长的困难。

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

射线算法要计算与多边形交点，因此运算量大。另一个比较麻烦的问题是射线与多边形相交时有些特殊情况如相切、重合等，会影响交点的个数， 必须予以排除，由此造成算法的不完善，并增加了编程的复杂性。

1. 扫描算法：扫描算法是射线算法的改进，通常情况下，沿栅格阵列的行方向扫描，在每两次遇到多边形边界点的两个位置之间的栅格，属于该多边形。扫描算法省去了计算射线与多边形交点的大量运算，大大提高了效率， 但一般需要预留一个较大的数组以存放边界点，而且扫描线与多边形边界相交的几种特殊情况仍然存在，需要加以判别。

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

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

事实上，每幅地图都是由多个多边形区域组成的。如果把不属于任何多边形的区域（包括无穷远点）看成一个编号为零的特殊区域，则每一条边界弧段都与两个不同编号的多边形相邻，按边界弧段的前进方向分别称为左、右多边形。对图 3－24 所示的 3 个多边形的 6 条边，有如表 3－5 所示的多边形编号。

表 3-5 线号与左右多边形号的对应关系

线号 左多边形 右多边形

Ⅰ 0 n1

Ⅱ n2 0

Ⅲ n3 n2

Ⅳ n1 n2

Ⅴ n3 0

Ⅵ n3 n1

对多边形 n1：线Ⅰ上行－n1，下行+n1；线Ⅳ上行+n1；线Ⅵ下行+n1； 对多边形 n2：线Ⅱ上行+n2，下行－n2；线Ⅳ上行－n2；线Ⅲ上行－n2； 对多边形 n3：线Ⅳ下行-n3，线Ⅲ上行+n3；线Ⅴ下行-n3，上行+n3。

对所有运算按线号进行排列，把图外区域作为编号为零的区域参加计算，下面括号内标出的为相应线的左或右多边形。

下行：-n3（左） +0（右）

线Ⅵ下行：-n3（左） +n1（右）

由此得到边界代数算法的基本思想：对每幅地图的全部具有左右多边形编号的边界弧段，沿其前进的方向逐个搜索，当边界上行时，将边界线位置与左图框之间的网格点加上一个值=（左多边形编号）-（右多边形编号）； 当边界线下行时，将边界线位置与左图框的栅格点加上一个值=（右多边形编号）-（左多边形编号），而不管边界线的排列顺序。

图 3—25 为两个邻域多边形的边界代数转换过程及结果示意图。

边界代数法与其它算法的不同之处在于它不是逐点搜寻判别边界，而是根据边界的拓扑信息，通过简单的加减代数运算将拓扑信息动态地赋予各栅格点，实现了矢量格式到栅格格式的转换。由于不需考虑边界与搜索轨迹之间的关系，因此算法简单，可靠性好，而且由于仅采用加减代数运算，每条边界仅计算一次，免去了公共边界重复运算，又可不考虑边界存放的顺序， 因此运算速度快，同时较少受内存容量的限制，特别适用于微机地理信息系统。