基于扫描线转换的快速等值线填充算法

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

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

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

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

1 等值线追踪算法

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

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

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

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

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

2 扫描线转换算法

利用等值线追踪算法已经得到了全部的等值线，现在的问题是如何选择一组色标并充填整幅等值线图。色标中的颜色数应等于等值线的级数。由于人跟对灰度等级分辨能力不高，通常只有十几个等级，因此应当选择多个键色内插形成色标。另外为了提高填充速度，应当将内插形成的色标颜色组存储下来，以便按等级数提取相应的填充颜色。

2．1 填充扫描线

选定填充色标后，就需要用色标中的颜色来填充等值线图了。但在介绍扫描线转换算法之前，先考虑一下如何填充一条扫描线。图2表示了一条水平扫描线与等值线相交的拓扑关系。这里假设等值线从0开始，间隔为10米，[0，10)对应颜色为c0，[30，40)对应颜色为c3，以此类推。算法首先需要求出扫描线与所有等值线的交点，并按照X坐标的大小排序，接着根据等值线问的拓扑关系，确定相邻两个交点间应该填充的颜色。观察图2可以发现相邻交点有两类情况：(1)前后交点的等高值不同，相差一个等级，如p0、p1交点对；(2)前后交点的等高值相同，如p3、p4交点对。        

对于第(1)种情况，颜色的确定比较容易，如pO、p1交点对，因为前后等值线的等值不同且必然相差一个等级，因此填充颜色应当取为[30，40)区段对应的颜色c3。在实际计算中可以计算相邻交点对应等高值的平均值v，并令填充颜色为v对应颜色。   

第(2)种情况要复杂一些，因为前后两个交点不存在级差，因此无法直接判断填充颜色，如p3、p4和p4、p5交点对。这时需要利用前一段填充的颜色来辅助判断，例如填充p3、p4交点对时，考虑到p2、p3交点对对应的等高值为50、60，而当前填充交点对对应的等高值为60、60，说明当前交点对对应的颜色应当比上一段高一个色阶，因而取为c6。这样就可以利用前一段的色阶推断等高值相同的后一段对应的填充颜色。在实际计算中，可以记下前一段的颜色等级g0，并且用当前交点对中任意交点对应的等高值计算出颜色等级g1。如果g0   

前面讨论了第一次出现等高值相同交点对的情况，但是有时候等高值相同的交点对会连续出现，例如p3、p4交点对后面的p4、p5交点对等高值也相同，这时是否可以继续使用前面的算法呢?不妨用前面的算法试一下，p3、p4交点对使用填充色c6，即g0=6，p5对应的颜色等级gl=6，按照前面的算法g0不小于gl，因此取g0=6-1=5，颜色取c5，恰巧正确。这是因为根据等值线不会相交的特点，如果连续出现等高值相同的交点对．那么交点对的颜色取值将会是交替变化的。利用前面的算法处理连续相同的交点对，也会得到交替变化的颜色，测试对于其他情况前面的算法也都是成立的。

2．2 扫描线转换算法快速填充等值线圈

前面介绍了填充一条扫描线的方法，如果将一幅等值线图的所有扫描线都按上面的算法填充，就可以得到填充后的等值线图。不过填充的速度比较慢，因为每条扫描线都需要与全部等值线求交，并按交点水平坐标大小排序，工作量很大，耗时较多。然而实际上一条扫描线仅仅会与一些等值线的某个边相交，并且与上一条扫描线相交的边一般也会与下一条扫描线相交，扫描线之间存在着相关性。因此可以借鉴图形学中填充多边形的扫描线转换算法，充分利用这些相关性，提高填充速度。下面详细介绍扫描线转换算法所需要使用的数据结构和算法流程。   

为了有效利用扫描线的相关性，在扫描线转换算法中需要建立如下数据结构：   

(1)等值线Y桶。等值线Y桶用于记录等值线的基本信息，桶的长度与扫描线的条数一样多，其编号与扫描线序号一致。每条等值线都要生成一个桶记录项，记录该等值线的最大Y坐标ymax、指向等值线的指针和指向该等值线边Y桶的指针。桶记录项按等值线的最小Y坐标插入到桶中。图3为等值线Y桶数据结构的示意图。

    (2)有效等值线表AIT。该表存储与当前扫描线相交的所有等值线在等值线Y桶中的记录指针。

    (3)边Y桶。每条等值线都由一系列的边组成，为了利用相关性，需要建立等值线的边Y桶，记录每条边的基本信息。等值线边Y桶的长度等于与该等值线相交的扫描线的条数。对于等值线中的每条边都要产生一个边记录，记录该边的最大Y坐标ymax，Y值较小端对应的X坐标xmin，当扫描线增大1时X坐标的增量△x，以及等值线的值value。每一个边记录按该边的最小Y坐标和整条等值线的最小Y坐标的差值存人边桶中，图4为边Y桶数据结构的示意图。

    (4)有效边表AET。该表存储与当前扫描线相交的所有等值线的边在边Y桶中的记录指针。   

    利用上面的数据结构，一个完整的扫描线转化填充算法如下：

    (1)遍历所有的等值线，为每一条等值线生成一个等值线Y桶中的记录，并根据等值线的最小Y坐标将该记录加入到等值线Y桶中。

    (2)将有效等值线表AIT和有效边表AET初始化为空。

    (3)对于每一条扫描线i，它从最小值开始，做以下工作。①检查等值线Y桶对于扫描线i是否有新的等值线记录，如果有则生成该扫描线对应的边Y桶，并在有效等值线表AIT中加入该扫描线的桶记录。②遍历AIT中的每一条等值线对应的桶记录，检查该等值线对应的边Y桶对于扫描线i是否有新的边记录加入，如果有则将新的边记录按xmin字段的大小加入到有效边表AET中。③利用有效边表AET和扫描线填充算法填充该扫描线。④遍历AET，检查是否有边记录的ymax字段等于i，如果有则删除该边记录，否则令该边记录的xmin=xmin+△x。⑤遍历AIT表，检查是否有等值线记录的ymax字段等于i，如果有则删除该记录。

    利用上面的算法可以实现等值线的填充，由于使用了扫描线转换算法，其算法复杂度与多边形填充一致，因而速度优势很明显。图5和图6是利用上面算法填充的等值线图。其中图5原始网格数据为lO行×15列，图幅450×300像素，色标含35个色阶，由4个键色插值生成，在主频为1.4GHz的电脑上填充时间约为40ms。图6原始网格数据为215行×330列，图幅990×645像素，色标含42个色阶，由4个键色插值生成，在主频为1.4GHz的电脑上填充时间约为120ms。从填充效果来看，填充结果与等值线一致，色阶正确没有出现任何误填和漏填错误。填充结果与其他填充算法结果一致。

    本文介绍了等值线图生成的一般方法，并在总结已有填充方法的基础上，提出了基于扫描线转换的等值线填充算法。该方法无需逐点插值填充，也无需追踪等值区域、判断包含关系，而是利用扫描线和等值线的拓扑关系确定填充颜色，并利用快速的扫描线转换算法进行填充，因而速度明显由于其他填充方法。经实践证明该方法可以在毫秒级完成一般等值线图的填充，而且填充效果与其他算法一致，因而具有很强的实用性。