来源：电子技术应用  作者：邓飞 王美平 周杲

摘要：提出了一种基于扫描线转换的等值线快速填充算法。与现有的逐点扫描法和区域填充算法相比，该算法既不需要进行逐点插值计算，也不需要追踪等值区域，判断区域包含关系，因而填充速度很快，且填充结果与区域填充法结果一致。实践证明该算法可以在毫秒级完成等值线图的填充。

关键词：等值线扫描线填充

等值线图在地质、物探、水文等许多工程领域都有广泛的应用，因此等值线图的自动生成问题一直是人们研究的热点。一般等值线图的生成分为等值线生成和等值线填充两个部分。目前，等值线的生成方法已经很成熟，最常用的是等值线追踪算法。近年来关于等值线填充算法的研究也很多，大致可分为扫描填充和区域填充两类。其中扫描填充法出现较早，它通过插值计算每个待填充点的颜色值，进行逐点填充。算法简单、可靠，但是填充速度慢，而且与追踪法生成的等值线存在一些细微差异，因此目前关于扫描填充的研究已经不多了。区域填充算法出现较晚，是研究的热点。算法的基本思想是寻找等值区域。然后利用图形库的多边形填充函数进行充填。该算法对于填充大幅等值线图效果明显，但是由于需要追踪等值区域并且判断区域包含关系．因此算法比较复杂，而且对于等值线较多的情况，处理速度也较慢。

考虑到前面两种算法的不足，本文借鉴了图形学中关于多边形快速填充的经典算法——扫描线转换算法，提出了一种利用扫描线填充等值线图的快速算法。该算法利用扫描线与等值线的拓扑关系确定填充颜色，并充分利用扫面线问的相关性快速填充。无需计算每个填充点的颜色值，也无需寻找等值区域后再进行多边形填充，因此速度明显优于前两类填充算法，而且填充效果与区域填充算法一致。

1 等值线追踪算法
等值线追踪是生成等值线图的第一步。目前等值线追踪算法的研究已经比较成熟，根据追踪的原始数据不同，分为规则矩形网格追踪和三角网追踪两类。其中常用的等值线绘制软件Surfer就是基于矩形数据网格的。当然矩形网格不能用于不规则的图形．因此后来又出现了基于三角网的等值线追踪方法。本文主要介绍等值线填充算法，因为填充算法仅需要利用等值线追踪的结果，而与具体采用何种追踪方法无关，因此这里不过多讨论等值线追踪算法．仅以矩形网格追踪为例进行简要说明。

等值线追踪的第一步是，计算出所有对应某一值的等值点在网格边线上的坐标。这对于矩形网格来说比较简单：先判断网格边线上是否存在等值点，如果存在则利用线性插值计算等值点在网格上的坐标。得到全部边线上的等值点后就需要使用一种追踪策略，将孤立的等值点连接在一起形成等值线。一般先追踪开曲线，即起止于网格边界线上的等值线。追踪开曲线可以顺着四个边界进行，对于某个边界任意选取一个等值点作为开始点，追踪下一个等值点，直到追踪到的下一个等值点也是边界上的点，就完成了一条等值线的追踪。

要从一个等值点追踪到下一个等值点，这通常是利用上一次的追踪方向来确定的。对于矩形网格来说追踪方向有4种，即向下、向左、向上和向右。如果上一次等值点所在网格的列比本次等值点所在列小1，则追踪方向向右。对于每一种追踪方向可能出现的情况有两种。这里以向右追踪为例进行说明，其余方向可以类推。向右追踪时，如果网格其他三个边上仅有一边存在等值点．则选择它作为下一个点；如果其他三边均存在等值点则从相邻的上、下边中选取，计算上一个等值点到上、下边中待选等值点的距离，取距离小的作为下一个等值点。利用上面的追踪方法追踪等值线一般都符合实际情况，并且不会出现交叉现象。

当追踪出一个等值点后需要将它删除，这样追踪完一条等值线后就不会重复追踪该等值线上的点了。当某一边界已没有等值点可以追踪后，就完成了该边界的开曲线追踪，对于矩形网格需要在四个边界上都进行开曲线追踪。开曲线追踪完毕后，可能还存在一些等值点，它们将构成封闭的闭曲线，可以任取一点进行追踪，直至回到该点则完成追踪。如果所有等值点都被追踪过了。则关于该等值的等值线就全部追踪完毕了。图1是使用网格法追踪生成的等值线图。后面的填充算法将对它进行快速填充。

利用追踪算法得到的等值线，在网格比较稀疏的情况下显得不够平滑，往往还需要采用一种拟合方法对等值线进行圆滑。一般可以使用三次参数样条曲线或三次B样条曲线来拟合加密曲线，达到圆滑的效果。不过为了保证曲线通过原有等值点，使用这两种拟合方式时都需要求解线性方程组，速度比较慢，但是圆滑效果很好．因为能够保证二阶连续。如果需要提高速度则可以采用HB曲线。该方法不需要求解方程，可以保证一阶连续，对于大多数情况都可以取得满意的效果，图1中的等值线就使用了该方法进行圆滑。

来源：电子技术应用  作者：邓飞 王美平 周杲

摘要：提出了一种基于扫描线转换的等值线快速填充算法。与现有的逐点扫描法和区域填充算法相比，该算法既不需要进行逐点插值计算，也不需要追踪等值区域，判断区域包含关系，因而填充速度很快，且填充结果与区域填充法结果一致。实践证明该算法可以在毫秒级完成等值线图的填充。

关键词：等值线扫描线填充

等值线图在地质、物探、水文等许多工程领域都有广泛的应用，因此等值线图的自动生成问题一直是人们研究的热点。一般等值线图的生成分为等值线生成和等值线填充两个部分。目前，等值线的生成方法已经很成熟，最常用的是等值线追踪算法。近年来关于等值线填充算法的研究也很多，大致可分为扫描填充和区域填充两类。其中扫描填充法出现较早，它通过插值计算每个待填充点的颜色值，进行逐点填充。算法简单、可靠，但是填充速度慢，而且与追踪法生成的等值线存在一些细微差异，因此目前关于扫描填充的研究已经不多了。区域填充算法出现较晚，是研究的热点。算法的基本思想是寻找等值区域。然后利用图形库的多边形填充函数进行充填。该算法对于填充大幅等值线图效果明显，但是由于需要追踪等值区域并且判断区域包含关系．因此算法比较复杂，而且对于等值线较多的情况，处理速度也较慢。

考虑到前面两种算法的不足，本文借鉴了图形学中关于多边形快速填充的经典算法——扫描线转换算法，提出了一种利用扫描线填充等值线图的快速算法。该算法利用扫描线与等值线的拓扑关系确定填充颜色，并充分利用扫面线问的相关性快速填充。无需计算每个填充点的颜色值，也无需寻找等值区域后再进行多边形填充，因此速度明显优于前两类填充算法，而且填充效果与区域填充算法一致。

1 等值线追踪算法
等值线追踪是生成等值线图的第一步。目前等值线追踪算法的研究已经比较成熟，根据追踪的原始数据不同，分为规则矩形网格追踪和三角网追踪两类。其中常用的等值线绘制软件Surfer就是基于矩形数据网格的。当然矩形网格不能用于不规则的图形．因此后来又出现了基于三角网的等值线追踪方法。本文主要介绍等值线填充算法，因为填充算法仅需要利用等值线追踪的结果，而与具体采用何种追踪方法无关，因此这里不过多讨论等值线追踪算法．仅以矩形网格追踪为例进行简要说明。

等值线追踪的第一步是，计算出所有对应某一值的等值点在网格边线上的坐标。这对于矩形网格来说比较简单：先判断网格边线上是否存在等值点，如果存在则利用线性插值计算等值点在网格上的坐标。得到全部边线上的等值点后就需要使用一种追踪策略，将孤立的等值点连接在一起形成等值线。一般先追踪开曲线，即起止于网格边界线上的等值线。追踪开曲线可以顺着四个边界进行，对于某个边界任意选取一个等值点作为开始点，追踪下一个等值点，直到追踪到的下一个等值点也是边界上的点，就完成了一条等值线的追踪。

要从一个等值点追踪到下一个等值点，这通常是利用上一次的追踪方向来确定的。对于矩形网格来说追踪方向有4种，即向下、向左、向上和向右。如果上一次等值点所在网格的列比本次等值点所在列小1，则追踪方向向右。对于每一种追踪方向可能出现的情况有两种。这里以向右追踪为例进行说明，其余方向可以类推。向右追踪时，如果网格其他三个边上仅有一边存在等值点．则选择它作为下一个点；如果其他三边均存在等值点则从相邻的上、下边中选取，计算上一个等值点到上、下边中待选等值点的距离，取距离小的作为下一个等值点。利用上面的追踪方法追踪等值线一般都符合实际情况，并且不会出现交叉现象。

当追踪出一个等值点后需要将它删除，这样追踪完一条等值线后就不会重复追踪该等值线上的点了。当某一边界已没有等值点可以追踪后，就完成了该边界的开曲线追踪，对于矩形网格需要在四个边界上都进行开曲线追踪。开曲线追踪完毕后，可能还存在一些等值点，它们将构成封闭的闭曲线，可以任取一点进行追踪，直至回到该点则完成追踪。如果所有等值点都被追踪过了。则关于该等值的等值线就全部追踪完毕了。图1是使用网格法追踪生成的等值线图。后面的填充算法将对它进行快速填充。

利用追踪算法得到的等值线，在网格比较稀疏的情况下显得不够平滑，往往还需要采用一种拟合方法对等值线进行圆滑。一般可以使用三次参数样条曲线或三次B样条曲线来拟合加密曲线，达到圆滑的效果。不过为了保证曲线通过原有等值点，使用这两种拟合方式时都需要求解线性方程组，速度比较慢，但是圆滑效果很好．因为能够保证二阶连续。如果需要提高速度则可以采用HB曲线。该方法不需要求解方程，可以保证一阶连续，对于大多数情况都可以取得满意的效果，图1中的等值线就使用了该方法进行圆滑。