在矢量数据结构中，通常以不规则多边形来表示区域，对于多边形内填充的晕线或符号，只是图形输出的表示方法，它并不作为空间数据参加运算。

矢量数据转成栅格数据是通过矢量边界轮廓的转换实现的。在栅格数据结构中，栅格元素值直接表示属性值。因此，当矢量边界线段转换成栅格数据后，还须进行面域的填充。

从计算机图形学的角度看，区域填充有很多算法，但基本上分两大类：一类是适合光栅扫描设备的算法，如种子填充法；另一类是还适合画线式设备的算法，如射线法。不论哪种算法，其关键是判断哪些点或栅格单元在多边形之内，哪些点在多边形之外。

1．射线法 该法中常用水平线扫描(或垂直线)法来判断一点是否在区域内。假若有一疑问点P(x，y)，要判断它是否在多边形内，可从该疑问点向左引水平扫描线(即射线)，计算此线段与区域边界的相交的次数c，如果c为奇数，认为疑问点在多边形内；c为偶数，则疑问点在多边形外。如图5-13(a)所示。为了方便起见，利用上述原理，可直接作一系列水平扫描线，求出扫描线和区域边界的交点，并对每个扫描线交点按X值的大小进行排序，其两相邻坐标点之间的射线在区域内。如图5-13(b)中扫描I1中x1x2段，扫描线I2中x′1x′2，x′3x′4段均在区域内。但上述情况中常出现一些例外，称奇异性。如图5-14(b)中射线I1，I2分别遇到了极值点P、P′，从而可能出现判断错误。对这种情况应采用邻点分析法区分出极值点。当用直线段逼近曲线时，极值点必定是两条直线的交点。如图5-14(a)中P1 、P2点。但二直线的交点不一定是极值点，如点P3，P4。为此，需要判断与顶点相交的两个直线段是否在扫描线的同一侧。若在同一侧为极值点，否则是非极值点。这样，当扫描线遇到多边形顶点时分两种情况：一种是该顶点为极值点，另一种是非极值点。对极值点看作2个同值交点，对非极值点看作一个交点，从而解决奇异性。

这样，增加了射线法的复杂性，为此出现了简化方法。高端点下移射线法就是一个例子。这种算法是采用坐标修正法来简化算法。它对组成多边形的每条直线的高端点y值坐标进行负修正，修正值根据设备和系统规定的精度和容差值确定，这样避开了上述奇异性。如图5-15所示多边形对每条直线y值高端点坐标进行负修正后形成如粗线所示的图。这时各扫描线同原边界点的交点如图中所示，从而避开了奇异点。这种求交法也称“上闭下开”法。即在二直线的交点处，扫描线上面的边与该扫描线相交的点有效，扫描线下面的边与该扫描线相交的交点无效，当扫描线与多边形边重合时不作求交运算。

2．边界点跟踪法 这是另一种填充法，该法从边界上某一栅格单元开始按顺时针方向跟踪边界上各栅格，(对多边形中岛则按逆时针方向跟踪，使岛内不被填充)。这里将跟踪的每个栅格分别赋予字符R，L或N，

其中R表示该栅格同相邻象素的行数不同，且行数增加的单元。

L表示该栅格同相邻象素的行数不同，且行数减少的单元。

N表示该栅格极值单元或相邻单元行数相同的单元。

最后，逐行扫描根据填充字符值，填充L→R之间的栅格。如图5-16所示。

图5-16 边缘跟踪法填充

5．4．2 边界代数法

矢量向栅格转换的关键是对矢量表示的多边形边界内的所有栅格赋予多边形编码，形成栅格数据阵列。为此需要逐点判断与边界关系，边界代数法不必逐点判断同边界关系即可完成矢量向栅格的转换。这时，面的填充是根据边界的拓扑信息，通过简单的加减运算将边界位置信息动态地赋予各栅格的。实现边界代数法填充的前提是已知组成多边形边界(弧段)的拓扑关系，即沿边界前进方向的左右多边形号。

图5-17为边界代数法的填充过程。这里假定沿边界前进方向y值下降时称下行，y值上升时称上行。填充值基于积分求多边形面积的思想，上行时填充值为左多边形号减右多边形号，下行时填充值为右多边形号减左多边形号，将每次填充值同该处的原始值作代数运算得到最终填充属性值。

图5-17(a)中，N1，N2弧上行，左多边形号减右多边形号为0-1=-1。在弧段N1，N2左边栅格值为-1。

图5-17(b)中N2，N3弧下行，右多边形号减左多边形号为2-0=2。在弧段N2，N3左边栅格值加2。

图5-17(c)中N3，N1弧下行，右多边形号减左多边形号为3-0=3。在弧段N3，N1左边栅格值加3。

图5-17(d)中N1，N4弧上行，左多边形号减右多边形号为1-3=-2。在弧段N1，N4左边栅格值加-2。

图5-17(e)中N4，N2弧上行，左多边形号减右多边形号为1-2=-1。在弧段N4，N2左边栅格值加-1。

图5-17(f)中N4，N3弧下行，右多边形号减左多边形号为3-2=-1。在弧段N4，N3左边栅格值加1。最后得到如图所示属性值。

本例中的每条弧段均为单值上行弧或下行弧。实际上，有时一条弧段可能既包含上行段，亦包括下行段，这时将该弧段分成上行段，下行段分别处理即可。

本算法可不考虑边界存放顺序及搜索轨迹，每条边界只计算一次，免去了边界的重复运算。因算法简单，可靠性高，运算速度快，广泛用于微机地理信息系统中。