EN中文

Journal of Geo-information Science >

2015 , Vol. 17 >Issue 7: 830 - 836

DOI: https://doi.org/10.3724/SP.J.1047.2015.00830

Orginal Article

An Algorithm for Rapidly Generating Terrain Section Line on Mobile Platform

  • WANG Qi , 1 ,
  • CHEN Feixiang , 1, * ,
  • PENG Junjie 2
Expand
  • 1. School of Information Science and Technology, Beijing Forestry University, Beijing 100083, China
  • 2. The IOT Technology Research Institute, China Aerospace Science and Technology Corporation, Beijing 100094, China
*Corresponding author: CHEN Feixiang, E-mail:

Received date: 2015-03-09

  Request revised date: 2015-03-30

  Online published: 2015-07-08

Copyright

《地球信息科学学报》编辑部 所有
Fold

Abstract

This paper depicts a terrain section line generation method using the contour line. The method is adaptive to the relatively weak performance of mobile platform which has smaller internal and external storage capacity and lower computing ability of processor compared to a desktop platform. On the desktop platform, digital elevation model (DEM, including triangular irregular network and regular grid) is often used to generate terrain section line, which is also the basis of our proposed method. By comparing it with two other methods for generating terrain section line through digital elevation model, we found that the proposed method in this paper is much simpler and faster in calculation, more convenient in operation, and meanwhile has an appropriate accuracy in the result chart. It is quite suitable for mobile GIS use. In addition, this paper presents a solution for the case that a route is located between two contour lines. In other words, the route has no intersection with the closest contour lines while the traditional algorithm cannot figure out its elevation value. By making a horizontal straight line and a vertical straight line across a certain point on the route, the four intersections of the straight lines and the point's two nearest contour lines are obtained. Then, the elevation value of this point could be calculated using the four intersections' elevation values. With this method, enough elevation points could be obtained to generate the final terrain section line. It solves the problems encountered in the practical applications with a good result. In summary, the proposed method in this paper contains eight steps. Step1: thinning the measured route for reducing the amount of computation. Step2: finding out the intersection set of the thinned route and the contour lines, and then obtaining the elevation value for each intersection. Step3: checking whether the intersection set is empty. If yes, then execute step 4, if not, jump to step7. Step4: at a certain point, make a horizontal line and a vertical line across it for obtaining the intersections with the contour lines. Step5: obtaining the four intersections' elevation values and calculating the distances between the four intersection points and the certain point. Step6: calculating the elevation value of the certain point using a formula, and then use the same approach to obtain enough amount of points' elevation values. Step7: to ensure the final section line is smooth, more elevation points are acquired through interpolating to the existing elevation points. Step8: drawing the final terrain section line by sequentially connecting the elevation points. Finally, the proposed algorithm is applied in the production of regional geological survey, and achieves good results.

Key words： contour line; terrain section line; mobile GIS; DEM

Cite this article

WANG Qi , CHEN Feixiang , PENG Junjie . An Algorithm for Rapidly Generating Terrain Section Line on Mobile Platform[J]. Journal of Geo-information Science, 2015 , 17(7) : 830 -836 . DOI: 10.3724/SP.J.1047.2015.00830

1 引言

地质剖面图（Geologic Cross Section）能详细地描述测量区域的地层信息,在垂直方向上直观地反映地层和岩体的结构和属性特征。其将三维空间问题转换到二维平面,不仅可形象直观地表达地层的结构构造和沉积规律,还可更直接地进行分析处理。在指导地下资源的开发利用、分析局部地区的地质条件,以及实施地质工程等方面,有重要的参考作用[1]。绘制地质剖面图的基础是准确地得到该区域的地形剖面线。
利用计算机绘制地形剖面线,大大简化了地形剖面线的生成过程,减少了地质工作者的室内作业工作量[2]。随着移动GIS技术的发展,特别是我国在区域地质调查中对于掌上地质数据采集系统的推广,野外地质工作人员在移动设备上,如何利用现有的数据快速生成地形剖面线,不再需要导入桌面GIS进行生成后再导出,已成为非常迫切需要解决的一个问题。本文基于移动GIS技术,利用等高线地形图,提出一种适用于移动平台的快速生成地形剖面线的方法,并利用该方法,在Android移动操作系统平台上,设计并开发了地形剖面线数字化绘制系统。

2 地形剖面线生成思路

地形剖面线的生成原理是通过追踪地形图上的基线（即剖面从地形图正上方俯看的投影线）,由基线周围的地形相关信息,如钻孔数据或等高线数据,得到基线相应位置的高程信息[3]。传统的地形剖面线生成是基于等高线地形图手工绘制,由坡面基线与每条等高线相交的各点,分别向下引垂线,根据各点高程值得到垂线终点,将终点绘制到相应的高度位置上,最后连成平滑的曲线[4],如图1所示。从绘制过程可看出,手工绘制地形剖面线操作较为繁琐,效率低下且精度不高。
Fig. 1 The base line generates the section line

图1 基线生成剖面线

利用计算机技术绘制地形剖面线,通常以CAD（计算机辅助设计）技术自动[5]或半自动[6]绘制地质剖面,或用编程语言结合GIS组件技术来绘制剖面[7-9]。
计算机辅助设计（CAD）技术绘制地质剖面图虽有优势[10],但它不适用于野外数据调查对于地质剖面图的要求,因为野外数据调查通常结合空间数据和属性数据生成地质剖面图,且对属性数据库的支持正是CAD技术的弱项[11]。然而,用GIS组件技术生成地质剖面图则需用到数字地面模型（DTM）[12]。GIS系统利用原始数据生成数字高程模型后,就可通过调查路线在等高线模型基础上,进行插值计算得到路线的剖面图。另外,还可先将等高线模型转换成规则格网或不规则三角网。不规则三角网模型的生成方式是按照一定的规则,将原始的离散数据点建立三角剖面,即连接成Delaunay三角形[13],该方法也是数字地面模型最常用的建模方式。而规则格网模型的生成方式是网格化原始离散数据 点[14]。建模完成后,将模型网格线与剖面基线进行高程（Z坐标轴）方向的相交分析,得出交点坐标（ X , Y ）和高程值（Z）,再计算交点到基线始点的距离X0,将交点的高程值（Z）作为Y0,进行（X0,Y0）的二维平面投影,投影结果即为所求的地形剖面线。通常情况下,在二维平面投影前,还需插值剖面坐标点,以获取足够点投影。基于数字高程模型生成的地质剖面图,精度相对较高,并且可以保证剖面生产的一致性。
由上可知,DEM模型的建模数据是离散的高程点。然而,在野外调查工作的实践中,地质工作人员更多使用的是等高线而不是高程点,因为不管是纸介质还是电子地形图,等高线数据在信息量、表现力、利用率等方面都远超过高程点数据[15]。因此,地学工作者和工程设计人员一直将等高线作为数据源绘制地形剖面线[16]。另外,在目前野外数据采集和调查实践中,外业工作人员通常使用搭载了移动GIS功能的便携式移动智能终端设备来进行工作。移动智能终端设备内外存储容量小,处理器计算能力相对较弱等局限[17],在数据处理方面,无法与PC机相提并论。因此,使用于桌面平台的地形剖面线生成方法,并不适应移动端快速生成地形剖面线的要求。

3 以等高线生成剖面线算法

等高线是地形图的基本表现形式,蕴含了大量地学内涵的数据,是众多地质调查工作者的重要手段[18-19],因此,本文提出一种以等高线直接生成地形剖面线的方法。

3.1 算法描述

在常用的GIS系统中,等高线通常直接以线矢量文件的形式存储,属性字段记录高程值。因此,本算法不需要为等高线单独设计存储格式,减小了移动终端处理数据的负荷。本算法的基本步骤如下：
（1）对路线抽稀,减小计算量。
路线（即需生成剖面线的一条基线）包含了无数个点。计算前利用改进的道格拉斯-普克算法,将该线段抽稀成有限个点。传统的道格拉斯-普克算法是对每一条曲线的首末点虚连成一条直线,求所有点与直线的距离,并找出最大距离值dmax,将dmax与限差D相比：若dmax<D,则将这条曲线上的中间点全部舍去;若dmax≥D,则保留dmax对应的坐标点,并以该点为界,把曲线分为2部分,对这2部分重复使用该方法[20]。该算法在计算过程中没有考虑记录中间最大的距离的节点,循环时间长、递归嵌套层次深,从而影响了程序的运行效率,不符合移动端快速高效处理数据的要求。因此,本文使用一种结合栈数据结构的分段道格拉斯-普克算法,将曲线的第1个点和最后1个点作为工作区间,将最远点的距离与阈值D的大小做比较,最终完成线要素的综合化简。具体过程为：
① 对于一条曲线Pi,设A=P0,B=P(n-1),连接AB,生成栈D,将B入栈;
② 在AB之间寻找与AB距离最远的点,记为C,距离为Dist;
③ 判断Dist是否大于阈值,若是,则令B=C,将C点加入特征点序列,C点入栈D,连接AB,然后跳转到⑥;若否,则执行④;
④ 判断B是否等于D(n-1),若否,则令A=C、B=D,连接AB,然后继续②;若是,则执行⑤;
⑤ 判断B是否等于P(n),若否,则令A=B、B=D(n-2),连接AB,D的栈顶退栈,然后执行⑥;若是,则直接执行⑥;
⑥ 清空栈D。
利用改进后的道格拉斯-普克算法,可较高效地在移动端对路线进行抽稀,为下面的进一步计算打下良好的数据基础。
（2）求出抽稀后的路线与等高线的交点集,获取每个交点的高程值。
抽稀后的路线是一条直线段,而每一条等高线则都是一条封闭的曲线。计算直线段与曲线的交点,使用算法如图2所示。
Fig. 2 The coordinates for the intersection point of a straight line and curve

图2 直线与曲线交点坐标

首先在等高线上截取曲线段AB,求得曲线元起点A到直线的垂直距离d1,以d1作为交点P至曲线元起点A的弧长值lp的初值l1,则可以求得曲线元上与l1相对应的P1点;再求得P1点到直线的垂距d2,以（d1+d2）作为lP的新值l2,这样又可求得曲线元上与l2相对应的P2点,如此反复计算,直至 d n ≤ ε （阈值,如0.001 m）,则 l p = ∑ l n d i ,从而可根据线路坐标通用模型[21]唯一确定直线与曲线元的交点坐标,得到交点坐标后,即可获取该点位置的高程值。
（3）高程点插值。
为了得到足够多的高程点,保证最终获取剖面线的光滑,本文利用B样条函数插值法,对高程点进行插值。三次均匀B样条曲线的矩阵如式（1）所示。
P i u = 1 6 u 3 u 2 u - 1 3 - 3 1 3 - 6 3 0 - 3 0 3 0 1 4 1 0 V i V i + 1 V i + 2 V i + 3 i = 1,2 , … , n - 1 （1）
则各段曲线的首点如式（2）所示。
P i = P i ( 0 ) = 1 6 ( V i + 4 V i + 1 + V i + 2 ) i = 1,2 , … , n - 1 （2）
最后一段曲线的末点即最后一个点为： P n = V n + 2 。
方程需要补充2个适当的边界条件,才能计算出多边形顶点 V j ( j = 1,2 , … , n + 1 , n + 2 ) ,即方程组有唯一解。边界条件的选择不止一种,最常用的是假设节点矢量两端点为四重节点,并且给定曲线两端点条件。利用重节点端点条件的基函数构造准均匀B样条曲线,可以使曲线过首、末2个端点,这成为了其独特的优点。同时,该算法在反算情况下,也具有明显的优越性[22]。应用重节点后,基函数不再是一个统一的标准型式,因此,各方程组也不尽相同。根据以上算法原理,本文假设曲线段数≥5,经过计算和推导,可得到式（3）。
9 - 3 1 4 7 12 1 6 1 6 2 3 1 6 ⋱ 1 6 2 3 1 6 1 6 7 12 1 4 - 3 9 V 2 V 3 V 4 ⋮ ⋮ ⋮ V n - 1 V n V n + 1 = 6 P 1 P 2 P 3 ⋮ ⋮ ⋮ P n - 2 P n - 1 6 P n （3）
式中,首端点 V 1 = P 1 ,末端顶点 V n + 2 = P n 。
通过上述算法,可得到足够多的高程点,为进一步的连接成线做好准备。
（4）形成剖面线。
按序连接所得高程点,形成一条由若干线段组成的曲线。当步骤（3）中获得的高程点值足够多时,即可得到满足生产实践需求的光滑的地形剖面线。

3.2 路线与等高线无交点的处理

通过等高线直接生成剖面线过程中,求出路线与等高线的交点是关键。然而,如果路线处于2条等高线之间,即与等高线没有交点,上述算法便无法求得地形剖面线。如图3所示,路线AB处于2条等高线之间,与等高线没有交点。
Fig. 3 The base line has no intersection with the contour line

图3 基线与等高线无交点

对此,本文提出利用如图4所示方法求路线AB上任意点的高程值：
Fig. 4 Make horizontal and vertical lines across any point for their intersections with the adjacent contours

图4 过点作直线求交点

（1）对于任意点O,过O点作它的水平和垂直方向直线,与最邻近的等高线求交点。水平方向直线与最邻近等高线分别交于I点和J点,垂直方向直线与最邻近等高线分别交于K点和L点;
（2）获取I,J,K,L 4个点的高程值,分别设为Hi,Hj,Hk,Hl;求出OI,OJ,OK,OL的长度,分别设为x1,x2,y1,y2;
（3）利用式（4）求出O点的高程值Ho;
（4）
（4）利用上述方法求出足够多点的高程值;
（5）利用样条函数插值法对高程点进行插值;
（6）连接所得高程点形成符合要求的光滑剖面线。
鉴此,本文解决了在路线与等高线没有交点的情况下,快速画出了剖面线。在实际应用中,此方法具有较好的效果。
综上所述,本文算法的具体步骤如下：
（1）对实际测量得到的路线进行抽稀,减小计算量;
（2）求出抽稀后的路线与等高线的交点集,获取每个交点的高程值;
（3）判断交点集是否为空。若是,则执行步骤（4）,若否,则跳转至步骤（7）;
（4）对于任意点O,过O点作它的水平和垂直方向直线,与最邻近的等高线求交点。水平方向直线与最邻近等高线分别交于I点和J点,垂直方向直线与最邻近等高线分别交于K点和L点;
（5）获取I,J,K,L 4个点的高程值,设它们分别为Hi,Hj,Hk,Hl;求出OI,OJ,OK,OL的长度,设长度分别为x1,x2,y1,y2;
（6）利用式（4）求出O点的高程值Ho,利用同样方法求出足够多点的高程值;
（7）对高层点进行插值计算,得到足够多的高程点,保证最终获取的剖面线的光滑;
（8）按序连接高层点,形成剖面线。

4 快速生成地形剖面线验证与分析

本文使用中国地质调查局数字地质调查系统的地质填图子系统获取的路线L0316数据,分别利用将等高线转换成规则格网模型[23-24]和不规则三角网模型[25-27],在桌面平台和掌上平台,实现了自动绘制地形剖面线的功能,通过对比实验分析了3种方法生成地形剖面线的优劣。
本文首先在PC端对3种方法进行对比分析,PC机配置为Windows8.1 x64系统,Intel Core i7-4600U CPU @2.10 GHz,8 GB内存,结果如表1所示。
Tab. 1 Comparison of section generation methods on PC

表1 PC端剖面生成方法对比

指标 方法
规则格网 不规则三角网 本文算法
CPU占用率（%） 70 80 20
内存占用率（%） 50 60 20
完成时间（s） 4 5 2
剖面精度（%） 96 98 93

注：剖面精度结果为数字化生成图像与手工绘制图相似度

由表1可知,利用不规则三角网模型生成的剖面图精度最高,与手工绘制图相似度高达98%,通过规则格网模型生成的剖面图精度次之,相似度为96%,而利用本文算法生成的剖面图的精度与手工绘制相似度为93%,尽管没有上述2种方法高,但也完全符合野外地质调查生产实践的要求。而且其在完成时间、CPU占用率和内存占用率等方面都占有明显的优势。
由分析成果图发现,规则格网模型、不规则三角网模型在地形剖面线不经过光滑时,放大到一定程度会在细节部分出现锯齿状。其原因是由于跨越网格时,2个网格的插值函数（各网格参数不相同）不一致,导致在跨越网格处的不连续。相比之下,利用等高线直接生成的地形剖面线,虽然插值精度有所下降,但是,在不光滑的条件下视觉效果更好。另外,利用等高线生成地形剖面线时,在基线端点取值部分进行了特别处理,使端点的取值更准确。
综上所述,在PC机上配置条件足够高的情况下,利用不规则三角网模型和规则格网模型生成的剖面图精度更高,适用于资料保存和进一步地操作分析。
在掌上智能移动平台,本文同样做了上述3种方法的对比测试,手机配置为Android 4.1系统,2 GB RAM,1.5G APQ80 64四核处理器,Adreno 320 GPU。实验对比结果如表2所示。
Tab. 2 Comparison of section generation methods on mobile device

表2 移动端剖面生成方法对比

指标 方法
规则格网 不规则三角网 本文算法
CPU占用率（%） >100 >100 80
内存占用率（%） >100 >100 80
完成时间（s） >3600 >3600 15
剖面精度（%） 96 98 93

注：剖面精度结果为数字化生成图像与手工绘制图相似度

显而易见,限于目前智能终端设备相对PC机在数据存储和处理能力方面的劣势,利用规则格网和不规则三角网模型生成地形剖面线的方法,均会出现运算时间长、效率低,内存和CPU占用率非常高,甚至超负荷的问题,导致成图速度极其缓慢,甚至导致设备出现死机的情况,基本不适用于野外生产实践。而本文提出的算法可在手机端配置相对低下的情况下,顺利生成地形剖面线,且剖面图精度较高,完成时间可行,非常适合于野外的生产实践。利用等高线直接生成的信手剖面图如图5所示。
Fig. 5 Cross-sectional view

图5 信手剖面图

5 结论

本文提出的等高线直接生成地形剖面线的算法,可适于移动GIS上生成地形剖面线。多种方法对比结果表明,本算法高效、快速,具有较好的鲁棒性。用该方法画出的地形剖面线,能较好地满足实际生产需求,效果良好,是一种可行的地形剖面线生成算法。
本文采用移动GIS技术,使用等高线图层,在移动终端设备上,对于1:100 000以上比例尺等高线生成剖面线具有较高的精度,但对于1:250 000及以下的小比例尺等高线生成的地形剖面线精度还有所不足,仍需进一步改进,使生成的地形剖面线精度更高。另外,本文提出的算法在地质构造表达方面,特别是断层和褶皱生成的地形、地质剖面线,有待进一步研究完善。

The authors have declared that no competing interests exist.

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
张克信,李超岭,于庆文,等.数字地质填图技术中的数字剖面系统[J].地层学杂志,2007,31(2):157-164.

[2]
李超岭,于庆文,杨东来,等.PRB数字地质填图技术研究[J].地球科学-中国地质大学学报,2003,28(4):377-384.

[3]
包世泰,余应刚,夏斌,等. GIS技术在工程地质制图中的应用[J].工程勘察,2005(2):1-3.

[4]
Golledge N R.Digital field survey technology[J]. Earthwise, 2004,20:4-5.

[5]
邢存恩,宋毅.采矿工程剖面图计算机生成方法探讨[J].煤炭学报,2000,25(z1):34-38.

[6]
唐新军,严和平.利用VB6.0和AutoCAD处理工程图形[J].计算机应用,2002,22(1):104-106.

[7]
方世明,吴冲龙,刘刚,等.基于GIS的地质图图切剖面计算机辅助编绘[J].中国地质,2002,29(4):440-444.

[8]
包世泰,夏斌,蒋鹏,等.基于GIS的地质勘察信息系统设计与实现[J].地理与地理信息科学,2004,20(4):31-35.

[9]
Nabighian M N.The analytic signal of two-dimensional magnetic bodies with polygonal cross-section: its properties and use for automated anomaly interpretation[J]. Geophysics, 1972,37(3):507-517.

[10]
杨丽. 地质平/剖面图自动成图系统研究与实现[D].长沙:中南大学,2013.

[11]
Barzgar E, Fard I A, Moghaddam R H, et al.Geological analysis and updating velocity model by restoration of a cross section in Zagros fold-thrust belt in the southwest of Iran[J]. Arabian Journal of Geosciences, 2015,8(2):1-16.

[12]
李世平,武文波,于欢.数字高程模型的建立与分析应用[J].辽宁工程技术大学学报(自然科学版),2008,27(z1): 31-33.

[13]
蒲浩,宋占峰,詹振炎.基于约束Delaunay三角剖分的道路三维建模方法[J].华中科技大学学报(自然科学版),2005,33(6):111-113.

[14]
赵建三. 基于格网DEM的自适应等高线内插方法[J].中南工业大学学报(自然科学版),2003,34(3):315-319.

[15]
Lark R M, Thorpe S, Kessler H, et al.Expert modelling of a geological cross-section from boreholes: sources of uncertainty and their quantification[J]. Solid Earth Discussions, 2014,6(2):1687-1721.

[16]
胡昌龙,易燕.数字高程模型DEM及其显示[J].黑龙江科技学院学报,2004,14(4):233-236.

[17]
Ferster C J, Coops N C.A review of earth observation using mobile personal communication devices[J]. Computers & Geosciences, 2013,51(2):339-349.

[18]
许多文. 不规则三角网(TIN)的构建及应用[D].南昌:江西理工大学,2010.

[19]
周良辰,林冰仙,闾国年.虚拟钻孔控制的地质剖面图构建算法与实现[J].地球信息科学学报,2013,15(3):356-361.

[20]
王进宝,刘正纲.曲线矢量数据压缩算法实现及评析[J].测绘与空间地理信息. 2006,29(2):122-124.

[21]
李全信,叶刚.直线与线路曲线交点坐标统一解算模型的研究[J].勘察科学技术,2008(2):19-21,57.

[22]
庄重,肖铮.基于B样条插值法的曲线光滑处理技术及应用[J].电脑知识与技术,2009,5(15):4000-4001.

[23]
张亚萍,熊华,姜晓红,等.大型网格模型简化和多分辨率技术综述[J].计算机辅助设计与图形学学报,2010,22(4):559-568.

[24]
王耀革. DEM建模与不确定性分析[D].郑州:解放军信息工程大学,2009.

[25]
杨斌,许辉熙,何政伟,等.高精度数字高程模型的构建方法研究[J].测绘工程,2010,19(5):1-5.

[26]
徐旭. 基于三角网的等值线生成及填充算法[D].长沙:中南大学,2011.

[27]
何纪锋. 基于TIN的数字高程建模及可视化研究[D].长沙:中南大学,2011.

Options
Outlines

/

〈 〉