基于八点法的等值线追踪算法

摘要

本发明公开的是一种基于八点法的等值线追踪算法，其融入了现实中的地貌特征影响因素，在等值线遇到出口选择情况时，进行了八点法扩张判断，在判断出当前区域地貌特征后，再进行追踪的出口取舍，从而避免了等值线追踪到错误出口，使得等值线不割裂大地貌，不在山谷、山脊地区出现错误小圆，最终等值线可还原真实地貌特征，绘制的等值线图更利于简单而直观地进行综合分析。在水文模型的建立、地形模拟、公路铁路勘测和规划、自然资源管理等等地学领域得到了广泛的应用，而且显示出了许多优越性，本算法简单明了，便于用计算机进行处理，能够很容易的计算等高线，坡向坡度，自动提取地形。

说明书

技术领域

本发明涉及的是一种地貌特征综合分析的计算方法，具体涉及的是一种分析地貌特征基于八点法的等值线追踪算法。

背景技术

等值线的追踪是对离散数据用数学方法插值，将具有相同量值的点变换成图的过程。它将三维信息显示于二维平面，是进行地理要素空间特征分析的强大工具，通过绘制相应的等值线图简单而直观地进行综合分析。但是现有的等值线追踪算法在进行出口判断时，会依据最近原则进行出口选择，该原则既能保证追踪算法的顺利运行又能保证算法效率最优，但是此原则应用在山谷与山脊地貌时会出现与真实地貌严重不符的大地貌割裂错误现象。尤其是在地势凹凸走向非常明显，或者插值网格较粗且取值间距较大的情况下，更容易导致异常凸起或凹陷等值线小圆的出现。

例如，现有的从插值格网中提取等值线的方法可以分为两类，格网线性内插法和高次曲面内插法。其中，格网线性内插法，主要原理是直接在格网边上做线性内插得到等值点，再按照一定的规则追踪一条等值线的全部等值点，依据精度需要选择合适的曲线光滑算法完成等值线的绘制。这种方法程序设计比较简单，随着格网单元数的增多，占用计算机的内存也增多，不过，目前计算机软硬件的发展水平己完全满足算法对内存的要求；格网单元尺寸的大小，会造成一幅图的输出结果有些微小的差别，主要原因是选择网格尺寸过大，会忽略一些微小的变化区域；有时格网单元尺寸选择过大，在对曲线进行光滑时可能会出现曲线相交现象。

高次曲面内插法主要原理是在选定范围内的格网点上进行拟合曲面，这个曲面一般有一个统一的数学表达式，依据一定的函数关系，进行等值线的追踪，绘制等值线图，根据利用的格网点数可以分为整体曲面和局部曲面内插。这种方法由于空间变量的复杂性和随机性，在实际研究过程中，空间变量坐标值很难满足某一数学函数表达式，所以在编程时程序一般较为复杂，曲面一般很难拟合己知空间变量。但这种方法也有一定的优点，即曲线追踪非常容易，并且一般不会出现曲线相交的现象。

格网线性内插法和高次曲面内插法都是在格网建好后，在格网边上内插等值点进行等值线追踪，但是当四条边都存在等值点的时候，就会出现追踪出口的二义性问题，此时如何确定等值线的走向，是等值线追踪与生成的根本难点所在，也是决定了等值线能否正确反映真是地形地貌的关键技术点。

此外，现有的三角网格插值的主要缺点为:

◆ 可以用内插生成规则格网，也可以建立连续表面，适合于小范围大比例尺高精度的地形建模，但是大范围不适用。

◆ 外推能力差，数据结构复杂，不便于规范化管理，难以与栅格和矢量数据联合分析，算法实现比较复杂和困难；

矩形网格的主要缺点为：

◆ 格网点高程内插会损失精度；

◆ 网格过大会损失地形的关键特征；

◆ 不改变网格的大小就不能适用于起伏程度不同的地区；

◆ 地形简单地区存在冗余数据；

除了以上缺陷外，在格网建好后，在格网边上进行的等值线追踪会有四条边都存在等值点的情况，而现有的追踪算法都无法正确寻找到出口。

发明内容

针对现有技术上存在的不足，本发明目的是在于提供一种基于八点法的等值线追踪算法，通过外向扩张来探索整体地势的走向，由此选择出正确的等值线追踪出口，避免了大地貌割裂的错误现象，最终使得等值线可以符合并还原原始真实地貌。

为了实现上述目的，本发明是通过如下的技术方案来实现：

一种基于八点法的等值线追踪算法，其方法步骤如下：

首先获得待测地貌数据，通过获取的地貌数据输入至在计算的制图区域内，然后在制图区域内确定等值点的起点与终点；

设制图区域的底部、上部、左部、右部为制图区域的南、北、西、东四边，对于等值线分开曲线和等值线闭合曲线的等值点的起点与终点确定方法如下：

（1）对于等值线分开曲线起点线头的确定方法为：

从制图区域的南、西、北、东四条边上依次寻找，在制图区域矩形网格里进行等值线的追踪，从纵轴i=l开始,即从第一行开始；若南边存在有等值线，则为起始线头；

算法程序从横轴j=l即第一列开始扫描,一旦捕捉到某等值线的值即设为起点线头,并开始追踪；

等值点的终点的确定方法如下：

对于a₃（要追踪的下一等值点）到边界为止的判别式是：南边边界要满足Y_A3=dy（Y_A3表示等值点a₃的Y坐标,dy表示单元网格纵向边长）；西边满足X_A3=dx（X_A3表示等值点a₃的X坐标,dx表示单元网格横向边长）；北边满足Y_A3=M（M表示区域纵向总网格点数）；东边满足X _A3=N（N表示区域横向总网格点数）；

只要满足上述任一个条件时，等值线即停止追踪，终点确定；

对于等值线闭合曲线，等值线始起点在图幅内追踪，且在制图区域的矩形内部网格任意边上的等值点数都可作为起始点；

等值线闭合曲线的等值点的终点确定方法为：

等值线选入起点后，然后从制图区域的矩形网格一边进入后，计算机程序追踪起始点所在矩形网格的中心格四角上的点称为内四点，并追踪以中心格为中心的与内四点水平以及垂直方向相对应的外八点，该等值线的终点算法流程如下：

设等值线从中心格左边进入，Hi,j表示i行j列点的高程，高于当前高程的点称为高程点，低于当前高程的称为低程点；_r为

当外八点的平均高程大于内四点中高程点的平均值时，即

H_8外>(1/2)(H_r,c+H_r+1,c+1)，则判断为被测地貌为山谷；

当外八点的平均高程小于内四点中低程点平均值时，即

H_8外<(1/2)(H_r+1,c+H_r,c+1)时，则判断为被测地貌是山脊；按照等值线不穿过山谷、山脊规则即可判断出口；其中r为行序数，c为列序数，且r>1，c r>1。

当外八点的平均高程大于内四点中低程点平均值，即H_8外介于二者之间时，中心格中的等值线为双曲抛物面，类似马鞍面；则用前高程值与中心格的中心点值H_中心相比较，判断等值线的走向，若当前高程>H_中心，应向左转；若当前高程<H_中心，应向右转。

上述中心格的中心点值H_中心的技术方法如下：

用待定系数法，可知中心点表达式为：

H_中心=A*（H_r,c+H_r+1,c+1 +H_r+1,c+H_r,c+1)/4+B*H_外             ①

3、要满足红字所示条件，仔细观察上图，可知必有

当H_外=(1/2)(H_r,c+H_r+1,c+1)时，H_中心=（H_r+1,c+H_r,c+1)/2             ②

当H_外=(1/2)(H_r+1,c+H_r,c+1)时，H_中心=（H_r,c+H_r+1,c+1)/2             ③

将②和③代入①得A=2, B=-1

代入①得 H_中心=2*（H_r,c+H_r+1,c+1 +H_r+1,c+H_r,c+1)/4－H_外=2H_内-H_外

上式中，H_内表示内四点的平均高程。

5、求出H_中心后，可与当前高程比较，若当前高程>H_中心，应向左转；若当前高程<H_中心，应向右转。

本发明融入了现实中的地貌特征影响因素，在等值线遇到出口选择情况时，进行了八点法扩张判断，在判断出当前区域地貌特征后，再进行追踪的出口取舍。从而避免了等值线追踪到错误出口，使得等值线不割裂大地貌，不在山谷、山脊地区出现错误小圆，最终等值线可还原真实地貌特征，绘制的等值线图更利于简单而直观地进行综合分析。在水文模型的建立、地形模拟、公路铁路勘测和规划、自然资源管理等等地学领域得到了广泛的应用，而且显示出了许多优越性，本算法简单明了，便于用计算机进行处理，能够很容易的计算等高线，坡向坡度，自动提取地形。

 

附图说明

下面结合附图和具体实施方式来详细说明本发明；

      图1为等值线出现交叉和不确定情况的示意图。

      图2为现有的解决方案示意图；

   图3为考虑地形走向的等值线的示意图；

   图4为本发明的八点法扩展判断等值线的示意图；

   图5为采用本发明进行追踪的等值线勾勒出原始地貌的等高线示意图；

   图6为依据本发明进行绘制的雨量等值线图。

 具体实施方式

为使本发明实现的技术手段、创作特征、达成目的与功效易于明白了解，下面结合具体实施方式，进一步阐述本发明。

本实施例是融入了现实中的地貌特征影响因素，在等值线遇到出口选择情况时，进行了八点法扩张判断，在判断出当前区域地貌特征后，再进行追踪的出口取舍，从而避免了等值线以最近原则寻找出口，使得等值线按照真实大地貌走向进行勾勒。

本实施例中，等值线：制图对象某一数量指标值相等的各点连成的平滑曲线，由地图上标出的表示制图对象数量的各点，采用内插法找出各整数点绘制而成的。常见有等温线，等压线，等高线，等势线等。

等值点的追踪：是指在计算出全部等值点以后,依照一定规则一定顺序把他们逐点连成等值线。为追踪到等值点，其要解决这个问题,分下列几个方面进行:

(1)等值点的起点与终点；

追踪一条等值线首要条件是确定等值线的起点。等值线分开曲线和闭合曲线两种，在寻找等值线头的方法是不相同的。开曲等值线特点是从制图区域网格边界开始又终止于网格边界的等值线；从图幅内部开始又在任意一点结束于该点的等值线算为闭合等值线。一般情况开曲等值线的线头从制图区域的南、西、北、东四条边上去找，而闭曲线的线头只能以在制图区域的内部网格上找。

开曲线起始点、终点的确定:

在矩形网格里进行等值线的追踪一般是从纵轴i=l开始,即从第一行（底边找称南边）开始。如果南边存在有等值线，必定是线头。但线头究竟在南边哪个位置上取决于横方向网格序号的变化。算法设计时让它从纵轴j=l（第一列）开始扫描,一旦捕捉到某等值线的值即找到线头,并开始追踪。

线头在南边上的等值线分布有四种可能:1、从南边开始西边终止；2、从南边开始又回到南边；3、南边开始北边结束；4、南边开始东边结束。如果在南边从j=1一直扫描到N-1还没有发现线头，算法会自动转西边界去找线头。其过程是：当i=2时,寻找线头必从j=1开始，若一直到N-1还没有发现，即进入i=3，j=l开始，为此推进，就可以把西边界上的等值线线头找出来。线头在西边界上的等值线分布也有四种情况。线头在北边界的条件是i=M，j=1，2，…，N-1。线头在东边界的条件是j=n，i=2,3,…,（m-1）。

以上四种情况的等值线分布情况的总结，实际追踪而成的等值线形态各异，但都不会超出这四种形态。对于a₃到边界为止的判别式是：南边要满足YA₃=dy；西边满足XA₃=dx；北边满足JA₃=M；东边满足J A₃=N。只要满足上述任一个条件时，等值线即停止追踪，终点也就确定下来。

对于闭合等值线起始点的确定：

对于闭合等值线始起点必须在图幅内寻找，并且只要是在矩形内部网格任意边上的等值点数都可作为起始点。具体方案是：从j=2到n-1和i=2到m-1各条纵边逐次找出等值点。当0<DV(i，j)<1，i=2，3,…,（m-1）j=2，3,……,（n-l）时即有等值点的在此，并令该点为a₂,j_a1=0，即可采用J_A1<J_A2的条件,由西向东追踪a₃等值点。

当得到a₂，a₃点后，经过上推和改变下标变量，即可采用上述的四种追踪条件，直到追踪到起始点本身。

(2)等值线出网格走向；

等值线进入网格后，只能往网格的另外三个边方向出去。如果不在算法上给予处理，就会出现等值线的交叉和不确定现象，如图1所示:

现有的技术或文献中的解决方案为：假设前一等值点为 a₁，当前等值点为a₂，要追踪的下一等值点为a₃，显然可能出现三种情况（a31，a32，a33），而实际追踪时只能选择一个。则选择的次序为：

a．当a31，a33 都存在时，选择靠近网格左侧边者为a₃；

b．当a31，a33 靠近左侧边距离相等时，则选择与a₂ 距离近者为a₃；

c．当a31，a33 只有一个存在时，存在点作为a₃；

d．当a31，a33 都不存在时，对边必存在a32作为a₃。

通过图3可以证明该方法的错误。

根据最近法则，等值线必然将跨越山脊、山谷线，将导致地貌特征线割裂现象，等值线绘制结果不符合地貌特征。

(3)基于八点法的等值线追踪算法

如图4所示，以从左边进入为例，且等值线的方向按约定，中心格的角上的点称为内四点，●表示高于当前高程称为高程点，○表示低于当前高程称为低程点，图形上面c-1,c,c+1, c+2是列号，左面r-1,r,r+1,r+2是行号。

除中心格四个顶点外，还应该考虑虚线圆标出的八个点（外八点），判断属于哪种情况。算法流程如下：

用Hi,j当表示i行j列点的高程。

1、当外八点的平均高程大于中心格四角中的黑点即高程点平均值时，即   H_外>(1/2)(H_r,c+H_r+1,c+1)，应认为是山谷。当外八点的平均高程小于白点即中心格四角中的低程点平均值时，即H_外<(1/2)(H_r+1,c+H_r,c+1)时，应认为是山脊。按照等值线不穿过山谷、山脊规则即可判断出口。

2、当H外介于二者之间时，即外八点的平均高程大于内四点中低程点平均值，且小于内四点中高程点的平均值时，可认为中心格类似马鞍面。仍然用前高程值与中心点比较的方法，用待定系数法，可知中心点表达式为：

H_中心=A*（H_r,c+H_r+1,c+1 +H_r+1,c+H_r,c+1)/4+B*H_外                     ①

3、要满足两高程点连接的对角线所示条件，参见图4，可知必有

当H_外=(1/2)(H_r,c+H_r+1,c+1)时，H_中心=（H_r+1,c+H_r,c+1)/2             ②

当H_外=(1/2)(H_r+1,c+H_r,c+1)时，H_中心=（H_r,c+H_r+1,c+1)/2             ③

4、将②和③代入①得A=2, B=-1

代入①得 H_中心=2*（H_r,c+Hr_+1,c+1 +H_r+1,c+H_r,c+1)/4－H_外=2H_内-H_外

上式中，H_内表示内四点的平均高程。

5、求出H_中心后，可与当前高程比较，若当前高程>H_中心，应向左转；若当前高程<H_中心，应向右转。

应用实例：如图5所示，选用了山谷地势走向明显的地区，依据本发明进行追踪的等值线可以勾勒出原始地貌（灰色底图），不破坏、不跨域山谷、山脊特征线。如图6所示，选用了四川地区2013年6月22日降雨测值，经过网格插值、等值线追踪、填充最终展现了依据本发明进行绘制的雨量等值线图。

本发明融入了现实中的地貌特征影响因素，在等值线遇到出口选择情况时，进行了八点法扩张判断，在判断出当前区域地貌特征后，再进行追踪的出口取舍。从而避免了等值线追踪到错误出口，使得等值线不割裂大地貌，不在山谷、山脊地区出现错误小圆，最终等值线可还原真实地貌特征，绘制的等值线图更利于简单而直观地进行综合分析。在水文模型的建立、地形模拟、公路铁路勘测和规划、自然资源管理等等地学领域得到了广泛的应用，而且显示出了许多优越性，本算法简单明了，便于用计算机进行处理，能够很容易的计算等高线，坡向坡度，自动提取地形。

以上显示和描述了本发明的基本原理和主要特征和本发明的优点。本行业的技术人员应该了解，本发明不受上述实施例的限制，上述实施例和说明书中描述的只是说明本发明的原理，在不脱离本发明精神和范围的前提下，本发明还会有各种变化和改进，这些变化和改进都落入要求保护的本发明范围内。本发明要求保护范围由所附的权利要求书及其等效物界定。