一种快速的等值线生成算法

董肇伟++卢海达++倪广元++王剑秦

摘 要：本文提出了一种新的等值点位于网格点时，对等值点的调整方法；在分析已有等值线追踪算法的基础上，提出了一种基于TIN网格的快速等值线追踪算法，实验表明该算法具有较高的执行效率。

关键词：等值线 等值点 TIN网格

中图分类号：TP391.41 文献标识码：A 文章编号：1672-3791（2014）04（a）-0033-02

等值线图能直观地展示数据的变化趋势，是众多领域展示成果的重要图件之一，被广泛应用于石油勘探、矿物开采、气象预报等众多领域。等值线的绘制是指从大量采样数据中提取出具有相同值的点的信息，并生成形态完整、位置精确的等值线的过程，包括等值线网格化、等值线追踪、等值线光滑、等值线填充与标注几个处理步骤[1]。其中等值线网格化是对网格边进行线性插值，进而求出等值点的过程。等值线的追踪则是利用等值线网格化产生的等值点数据，将其中相同等值点进行连接的过程。等值线追踪的传统方法是，在网格单元边上选取一个等值点，寻找邻近的等值点，顺次连接成线，直到等值点回到起始点或位于工区边界，完成单条等值线的追踪，并以此为基础遍历所有的等值点。在追踪过程中，等值线分为闭合与非闭合两种情形，需要先追踪开曲线，再追踪闭曲线，否则不能确保结果正确。特定的搜索顺序提高了处理过程的复杂性，增加了网格单元的重复搜索次数，致使效率低下。

针对此类问题，很多学者提出了在不规则三角网（TIN网格）下的改进方法，成建梅[2]等提出为三角形三边分别赋予不同的权值，以方便确定三角形单元内等值点的位置。但是这只是对局部的改进，未涉及等值线追踪过程的优化。黄维科[3]等基于三角形单元内等值线段容易确定的事实，提出了使用“焊接法”将相同的等值点连接从而生成整条等值线的方法。但是在搜索等值线段间的共同等值点时，需要对已确定的等值线段进行遍历，执行效率提高幅度有限；并且使用的是简单的坐标值判别法，容易因机器误差引起错误结果。

1 改进的等值线生成算法

现在常用的用于生成等值线的网格有矩形网格、TIN网格等。综合考虑，本文选用TIN网格。生成等值线的主要步骤中，等值线的网格化处理与等值线的追踪是基础与关键，直接影响等值线的准确度和生成速度。接下来将针对TIN网格，介绍对这两个过程的改进。

1.1 等值线网格化处理方法

在TIN网格中，等值线网格化处理的作用就是在网格边上计算出各等值点，为之后的等值线追踪提供基础数据。以三角形单元为单位，遍历整个TIN网格，判断三角形棱边上有无等值点[4]，使用公式：

其中z为等值线的高程，zi，zj是对应三角形顶点的高程。若存在，则等值点的坐标为：

1.2 等值线追踪算法

本文采用的追踪思想即是：从一个等值点出发，沿任意方向搜索等值点，直到回到起点或者到达边界；再从起点开始沿反向搜索未经过的点。最终生成一条等值线。

为了提高搜索效率，注意到在经过网格化处理后，可以保证每条三角形棱边至多有一个等值点，而与该等值点相连的等值点至多有两个。所以在以三角形单元为单位遍历TIN网格时，给每一棱边指定唯一的序号，若找出等值点，则记录与之相连的等值点所处的棱边。接下来以棱边为基本单元追踪等值线，这样的好处是便于构造顺序存储结构，进而使用随机存取机制，加快追踪速度。

序号的引入将问题转化为简单的数值匹配，避免了常规算法中使用的方位信息。同时可以忽略常规等值线追踪算法中的特定追踪顺序，对于拓扑复杂TIN网格，不考虑三角形棱边是否位于边界上可以大大简化处理的复杂度。

2 算法实现

2.1 数据结构

程序要兼顾按索引查找时的快捷和等值点插入的便利，故选择混合存储结构。具体实现如下。

等值点的数据结构见表1。

三角单元棱边的数据结构见表2。

其中访问标记指示是否追踪过该边，初始时置为False。等值点1是位于该边上的等值点。等值点2指针指向当前等值线上的另一个端点（队尾）。邻接边1，2上的等值点与该边上的相连。

当完成等值线网格化处理后，所有等值点被计算出，三角网格边中的棱边序号、等值点1指针、邻接棱边1与邻接棱边2的序号均被确定。特别的，当棱边上的等值点为一条非闭合等值线的端点时，它只有一个有效的邻接棱边。

2.2 算法流程

（1）从TIN网格中顺次读取一个棱边E1。如果E1上不存在等值点，或访问标记为TRUE，重复步骤（1）。否则，置访问标记为True，根据邻接边1序号读取棱边Ei，转到步骤（2）。

（2）置Ei的访问标记为True，并将它的等值点移动到前一个等值点的末尾。若Ei即是E1，完成单条等值线的搜索，转到步骤（1）。否则，读取Ei上不同于前一棱边的邻接边序号。若存在，则在读取新的棱边Ei，重复步骤（2）。若不存在，根据E1的邻接边2序号取出棱边Ej，转到步骤（3）。

（3）置Ej的访问标记为True，将等值线头结点移动到Ej上等值点的末尾。读取Ej上不同于后一个点所在边的邻接边序号。若存在，则取出新的棱边Ej，重复步骤（3）。若不存在，完成单条等值线的搜索，转到步骤（1）。

当所有棱边都在步骤（1）中被读取过后，算法完成。

3 实验结果与分析

笔者将本文提出的改进算法运用到“裂缝性储层精细描述软件”当中，利用该算法获得层面模型的等值线，并经过平滑、着色处理后，得到如图4所示的效果图。

为进一步测试算法效率，利用图4中的层面，计算传统追踪算法和改进算法的运行时间。层面模型包含22827个坐标点，出于确保结果有效性的考虑，指定等值线高程值的个数分别为5，10，15，…，60，从而获得12组测试数据。随着高程值个数的增加，程序会多次调用追踪算法，相当于增多了模型坐标点与等值点的个数。

采用改进算法追踪等值线，速度平均提升30%以上。这是因为由于TIN网格拓扑复杂，追踪等值线时大量时间消耗在对网格的遍历上。传统算法在计算等值点时需要遍历一遍网格，在进行等值线追踪时，又要遍历两遍：第一遍以位于网格边界的等值点为起点，查找非闭合等值线；第二遍再查找闭合等值线。而本文提出的改进算法只需要在计算等值点时遍历一遍网格，由于遍历时为三角形单元的棱边设置索引，在追踪等值线时，直接按索引遍历从而避开了TIN网格的复杂性对程序的不良影响。并且，改进算法中不区分等值线的开闭性，可以用统一的过程追踪，又减少一次对棱边的遍历。故改进算法的时间性能大幅优于传统算法。

4 结论

本文基于TIN网格，提出了一种快速的等值线生成算法，该算法改进了等值点位于网格顶点时，对其进行偏移的方法，尽最大限度减小偏移量的不确定性，使结果更贴合原始数据。之后，针对现有主流追踪算法过程繁琐，实现复杂的弱点，为三角单元棱边设置索引，简化遍历过程，并将闭合和非闭合两种等值线的追踪方法统一，大大简化追踪流程。在等值线绘图中，采用TIN网格有两大优点：一是等值线连接方式唯一，不会出现矩形网格中的二义性问题；二是TIN网格使用的是原始数据点，避免了网格拟合带来的误差，尤其在原始数据密集的情况下，能高度还原地形地貌。本文的工作使得TIN网格下等值线的追踪更加方便快捷，从而可以较好的应用于地质建模领域。

参考文献

[1] 王鹏.等值线快速绘图方法研究及系统设计与实现[D].电子科技大学，2011.

[2] 成建梅，陈崇希，孙红林.三角网格等值线自动生成方法及程序实现[J].水利学报，1998，10（10）：23-26.

[3] 黄维科，王弘琪.在AutoCAD中用“焊接法”绘制等高线[J].公路与汽运，2005，1：29.

[4] 李瑞雪.球物理等值线构建及属性建立[D].中南大学，2012.

[5] 韩丽娜.地质等值线图的生成与绘制[D].西安：西安科技大学，2006.endprint

摘 要：本文提出了一种新的等值点位于网格点时，对等值点的调整方法；在分析已有等值线追踪算法的基础上，提出了一种基于TIN网格的快速等值线追踪算法，实验表明该算法具有较高的执行效率。

关键词：等值线 等值点 TIN网格

中图分类号：TP391.41 文献标识码：A 文章编号：1672-3791（2014）04（a）-0033-02

等值线图能直观地展示数据的变化趋势，是众多领域展示成果的重要图件之一，被广泛应用于石油勘探、矿物开采、气象预报等众多领域。等值线的绘制是指从大量采样数据中提取出具有相同值的点的信息，并生成形态完整、位置精确的等值线的过程，包括等值线网格化、等值线追踪、等值线光滑、等值线填充与标注几个处理步骤[1]。其中等值线网格化是对网格边进行线性插值，进而求出等值点的过程。等值线的追踪则是利用等值线网格化产生的等值点数据，将其中相同等值点进行连接的过程。等值线追踪的传统方法是，在网格单元边上选取一个等值点，寻找邻近的等值点，顺次连接成线，直到等值点回到起始点或位于工区边界，完成单条等值线的追踪，并以此为基础遍历所有的等值点。在追踪过程中，等值线分为闭合与非闭合两种情形，需要先追踪开曲线，再追踪闭曲线，否则不能确保结果正确。特定的搜索顺序提高了处理过程的复杂性，增加了网格单元的重复搜索次数，致使效率低下。

针对此类问题，很多学者提出了在不规则三角网（TIN网格）下的改进方法，成建梅[2]等提出为三角形三边分别赋予不同的权值，以方便确定三角形单元内等值点的位置。但是这只是对局部的改进，未涉及等值线追踪过程的优化。黄维科[3]等基于三角形单元内等值线段容易确定的事实，提出了使用“焊接法”将相同的等值点连接从而生成整条等值线的方法。但是在搜索等值线段间的共同等值点时，需要对已确定的等值线段进行遍历，执行效率提高幅度有限；并且使用的是简单的坐标值判别法，容易因机器误差引起错误结果。

1 改进的等值线生成算法

现在常用的用于生成等值线的网格有矩形网格、TIN网格等。综合考虑，本文选用TIN网格。生成等值线的主要步骤中，等值线的网格化处理与等值线的追踪是基础与关键，直接影响等值线的准确度和生成速度。接下来将针对TIN网格，介绍对这两个过程的改进。

1.1 等值线网格化处理方法

在TIN网格中，等值线网格化处理的作用就是在网格边上计算出各等值点，为之后的等值线追踪提供基础数据。以三角形单元为单位，遍历整个TIN网格，判断三角形棱边上有无等值点[4]，使用公式：

其中z为等值线的高程，zi，zj是对应三角形顶点的高程。若存在，则等值点的坐标为：

1.2 等值线追踪算法

本文采用的追踪思想即是：从一个等值点出发，沿任意方向搜索等值点，直到回到起点或者到达边界；再从起点开始沿反向搜索未经过的点。最终生成一条等值线。

为了提高搜索效率，注意到在经过网格化处理后，可以保证每条三角形棱边至多有一个等值点，而与该等值点相连的等值点至多有两个。所以在以三角形单元为单位遍历TIN网格时，给每一棱边指定唯一的序号，若找出等值点，则记录与之相连的等值点所处的棱边。接下来以棱边为基本单元追踪等值线，这样的好处是便于构造顺序存储结构，进而使用随机存取机制，加快追踪速度。

序号的引入将问题转化为简单的数值匹配，避免了常规算法中使用的方位信息。同时可以忽略常规等值线追踪算法中的特定追踪顺序，对于拓扑复杂TIN网格，不考虑三角形棱边是否位于边界上可以大大简化处理的复杂度。

2 算法实现

2.1 数据结构

程序要兼顾按索引查找时的快捷和等值点插入的便利，故选择混合存储结构。具体实现如下。

等值点的数据结构见表1。

三角单元棱边的数据结构见表2。

其中访问标记指示是否追踪过该边，初始时置为False。等值点1是位于该边上的等值点。等值点2指针指向当前等值线上的另一个端点（队尾）。邻接边1，2上的等值点与该边上的相连。

当完成等值线网格化处理后，所有等值点被计算出，三角网格边中的棱边序号、等值点1指针、邻接棱边1与邻接棱边2的序号均被确定。特别的，当棱边上的等值点为一条非闭合等值线的端点时，它只有一个有效的邻接棱边。

2.2 算法流程

（1）从TIN网格中顺次读取一个棱边E1。如果E1上不存在等值点，或访问标记为TRUE，重复步骤（1）。否则，置访问标记为True，根据邻接边1序号读取棱边Ei，转到步骤（2）。

（2）置Ei的访问标记为True，并将它的等值点移动到前一个等值点的末尾。若Ei即是E1，完成单条等值线的搜索，转到步骤（1）。否则，读取Ei上不同于前一棱边的邻接边序号。若存在，则在读取新的棱边Ei，重复步骤（2）。若不存在，根据E1的邻接边2序号取出棱边Ej，转到步骤（3）。

（3）置Ej的访问标记为True，将等值线头结点移动到Ej上等值点的末尾。读取Ej上不同于后一个点所在边的邻接边序号。若存在，则取出新的棱边Ej，重复步骤（3）。若不存在，完成单条等值线的搜索，转到步骤（1）。

当所有棱边都在步骤（1）中被读取过后，算法完成。

3 实验结果与分析

笔者将本文提出的改进算法运用到“裂缝性储层精细描述软件”当中，利用该算法获得层面模型的等值线，并经过平滑、着色处理后，得到如图4所示的效果图。

为进一步测试算法效率，利用图4中的层面，计算传统追踪算法和改进算法的运行时间。层面模型包含22827个坐标点，出于确保结果有效性的考虑，指定等值线高程值的个数分别为5，10，15，…，60，从而获得12组测试数据。随着高程值个数的增加，程序会多次调用追踪算法，相当于增多了模型坐标点与等值点的个数。

采用改进算法追踪等值线，速度平均提升30%以上。这是因为由于TIN网格拓扑复杂，追踪等值线时大量时间消耗在对网格的遍历上。传统算法在计算等值点时需要遍历一遍网格，在进行等值线追踪时，又要遍历两遍：第一遍以位于网格边界的等值点为起点，查找非闭合等值线；第二遍再查找闭合等值线。而本文提出的改进算法只需要在计算等值点时遍历一遍网格，由于遍历时为三角形单元的棱边设置索引，在追踪等值线时，直接按索引遍历从而避开了TIN网格的复杂性对程序的不良影响。并且，改进算法中不区分等值线的开闭性，可以用统一的过程追踪，又减少一次对棱边的遍历。故改进算法的时间性能大幅优于传统算法。

4 结论

本文基于TIN网格，提出了一种快速的等值线生成算法，该算法改进了等值点位于网格顶点时，对其进行偏移的方法，尽最大限度减小偏移量的不确定性，使结果更贴合原始数据。之后，针对现有主流追踪算法过程繁琐，实现复杂的弱点，为三角单元棱边设置索引，简化遍历过程，并将闭合和非闭合两种等值线的追踪方法统一，大大简化追踪流程。在等值线绘图中，采用TIN网格有两大优点：一是等值线连接方式唯一，不会出现矩形网格中的二义性问题；二是TIN网格使用的是原始数据点，避免了网格拟合带来的误差，尤其在原始数据密集的情况下，能高度还原地形地貌。本文的工作使得TIN网格下等值线的追踪更加方便快捷，从而可以较好的应用于地质建模领域。

参考文献

[1] 王鹏.等值线快速绘图方法研究及系统设计与实现[D].电子科技大学，2011.

[2] 成建梅，陈崇希，孙红林.三角网格等值线自动生成方法及程序实现[J].水利学报，1998，10（10）：23-26.

[3] 黄维科，王弘琪.在AutoCAD中用“焊接法”绘制等高线[J].公路与汽运，2005，1：29.

[4] 李瑞雪.球物理等值线构建及属性建立[D].中南大学，2012.

[5] 韩丽娜.地质等值线图的生成与绘制[D].西安：西安科技大学，2006.endprint

摘 要：本文提出了一种新的等值点位于网格点时，对等值点的调整方法；在分析已有等值线追踪算法的基础上，提出了一种基于TIN网格的快速等值线追踪算法，实验表明该算法具有较高的执行效率。

关键词：等值线 等值点 TIN网格

中图分类号：TP391.41 文献标识码：A 文章编号：1672-3791（2014）04（a）-0033-02

等值线图能直观地展示数据的变化趋势，是众多领域展示成果的重要图件之一，被广泛应用于石油勘探、矿物开采、气象预报等众多领域。等值线的绘制是指从大量采样数据中提取出具有相同值的点的信息，并生成形态完整、位置精确的等值线的过程，包括等值线网格化、等值线追踪、等值线光滑、等值线填充与标注几个处理步骤[1]。其中等值线网格化是对网格边进行线性插值，进而求出等值点的过程。等值线的追踪则是利用等值线网格化产生的等值点数据，将其中相同等值点进行连接的过程。等值线追踪的传统方法是，在网格单元边上选取一个等值点，寻找邻近的等值点，顺次连接成线，直到等值点回到起始点或位于工区边界，完成单条等值线的追踪，并以此为基础遍历所有的等值点。在追踪过程中，等值线分为闭合与非闭合两种情形，需要先追踪开曲线，再追踪闭曲线，否则不能确保结果正确。特定的搜索顺序提高了处理过程的复杂性，增加了网格单元的重复搜索次数，致使效率低下。

针对此类问题，很多学者提出了在不规则三角网（TIN网格）下的改进方法，成建梅[2]等提出为三角形三边分别赋予不同的权值，以方便确定三角形单元内等值点的位置。但是这只是对局部的改进，未涉及等值线追踪过程的优化。黄维科[3]等基于三角形单元内等值线段容易确定的事实，提出了使用“焊接法”将相同的等值点连接从而生成整条等值线的方法。但是在搜索等值线段间的共同等值点时，需要对已确定的等值线段进行遍历，执行效率提高幅度有限；并且使用的是简单的坐标值判别法，容易因机器误差引起错误结果。

1 改进的等值线生成算法

现在常用的用于生成等值线的网格有矩形网格、TIN网格等。综合考虑，本文选用TIN网格。生成等值线的主要步骤中，等值线的网格化处理与等值线的追踪是基础与关键，直接影响等值线的准确度和生成速度。接下来将针对TIN网格，介绍对这两个过程的改进。

1.1 等值线网格化处理方法

在TIN网格中，等值线网格化处理的作用就是在网格边上计算出各等值点，为之后的等值线追踪提供基础数据。以三角形单元为单位，遍历整个TIN网格，判断三角形棱边上有无等值点[4]，使用公式：

其中z为等值线的高程，zi，zj是对应三角形顶点的高程。若存在，则等值点的坐标为：

1.2 等值线追踪算法

本文采用的追踪思想即是：从一个等值点出发，沿任意方向搜索等值点，直到回到起点或者到达边界；再从起点开始沿反向搜索未经过的点。最终生成一条等值线。

为了提高搜索效率，注意到在经过网格化处理后，可以保证每条三角形棱边至多有一个等值点，而与该等值点相连的等值点至多有两个。所以在以三角形单元为单位遍历TIN网格时，给每一棱边指定唯一的序号，若找出等值点，则记录与之相连的等值点所处的棱边。接下来以棱边为基本单元追踪等值线，这样的好处是便于构造顺序存储结构，进而使用随机存取机制，加快追踪速度。

序号的引入将问题转化为简单的数值匹配，避免了常规算法中使用的方位信息。同时可以忽略常规等值线追踪算法中的特定追踪顺序，对于拓扑复杂TIN网格，不考虑三角形棱边是否位于边界上可以大大简化处理的复杂度。

2 算法实现

2.1 数据结构

程序要兼顾按索引查找时的快捷和等值点插入的便利，故选择混合存储结构。具体实现如下。

等值点的数据结构见表1。

三角单元棱边的数据结构见表2。

其中访问标记指示是否追踪过该边，初始时置为False。等值点1是位于该边上的等值点。等值点2指针指向当前等值线上的另一个端点（队尾）。邻接边1，2上的等值点与该边上的相连。

当完成等值线网格化处理后，所有等值点被计算出，三角网格边中的棱边序号、等值点1指针、邻接棱边1与邻接棱边2的序号均被确定。特别的，当棱边上的等值点为一条非闭合等值线的端点时，它只有一个有效的邻接棱边。

2.2 算法流程

（1）从TIN网格中顺次读取一个棱边E1。如果E1上不存在等值点，或访问标记为TRUE，重复步骤（1）。否则，置访问标记为True，根据邻接边1序号读取棱边Ei，转到步骤（2）。

（2）置Ei的访问标记为True，并将它的等值点移动到前一个等值点的末尾。若Ei即是E1，完成单条等值线的搜索，转到步骤（1）。否则，读取Ei上不同于前一棱边的邻接边序号。若存在，则在读取新的棱边Ei，重复步骤（2）。若不存在，根据E1的邻接边2序号取出棱边Ej，转到步骤（3）。

（3）置Ej的访问标记为True，将等值线头结点移动到Ej上等值点的末尾。读取Ej上不同于后一个点所在边的邻接边序号。若存在，则取出新的棱边Ej，重复步骤（3）。若不存在，完成单条等值线的搜索，转到步骤（1）。

当所有棱边都在步骤（1）中被读取过后，算法完成。

3 实验结果与分析

笔者将本文提出的改进算法运用到“裂缝性储层精细描述软件”当中，利用该算法获得层面模型的等值线，并经过平滑、着色处理后，得到如图4所示的效果图。

为进一步测试算法效率，利用图4中的层面，计算传统追踪算法和改进算法的运行时间。层面模型包含22827个坐标点，出于确保结果有效性的考虑，指定等值线高程值的个数分别为5，10，15，…，60，从而获得12组测试数据。随着高程值个数的增加，程序会多次调用追踪算法，相当于增多了模型坐标点与等值点的个数。

采用改进算法追踪等值线，速度平均提升30%以上。这是因为由于TIN网格拓扑复杂，追踪等值线时大量时间消耗在对网格的遍历上。传统算法在计算等值点时需要遍历一遍网格，在进行等值线追踪时，又要遍历两遍：第一遍以位于网格边界的等值点为起点，查找非闭合等值线；第二遍再查找闭合等值线。而本文提出的改进算法只需要在计算等值点时遍历一遍网格，由于遍历时为三角形单元的棱边设置索引，在追踪等值线时，直接按索引遍历从而避开了TIN网格的复杂性对程序的不良影响。并且，改进算法中不区分等值线的开闭性，可以用统一的过程追踪，又减少一次对棱边的遍历。故改进算法的时间性能大幅优于传统算法。

4 结论

本文基于TIN网格，提出了一种快速的等值线生成算法，该算法改进了等值点位于网格顶点时，对其进行偏移的方法，尽最大限度减小偏移量的不确定性，使结果更贴合原始数据。之后，针对现有主流追踪算法过程繁琐，实现复杂的弱点，为三角单元棱边设置索引，简化遍历过程，并将闭合和非闭合两种等值线的追踪方法统一，大大简化追踪流程。在等值线绘图中，采用TIN网格有两大优点：一是等值线连接方式唯一，不会出现矩形网格中的二义性问题；二是TIN网格使用的是原始数据点，避免了网格拟合带来的误差，尤其在原始数据密集的情况下，能高度还原地形地貌。本文的工作使得TIN网格下等值线的追踪更加方便快捷，从而可以较好的应用于地质建模领域。

参考文献

[1] 王鹏.等值线快速绘图方法研究及系统设计与实现[D].电子科技大学，2011.

[2] 成建梅，陈崇希，孙红林.三角网格等值线自动生成方法及程序实现[J].水利学报，1998，10（10）：23-26.

[3] 黄维科，王弘琪.在AutoCAD中用“焊接法”绘制等高线[J].公路与汽运，2005，1：29.

[4] 李瑞雪.球物理等值线构建及属性建立[D].中南大学，2012.

[5] 韩丽娜.地质等值线图的生成与绘制[D].西安：西安科技大学，2006.endprint