数学建模2012国赛获奖论文地表面积估算与资源分配的DEM模型

1、地表面积估算与资源分配的DEM模型摘要本文针对三维地形的地表面积的大小以及监测器的合理布置以求达到最有效的监测范围问题进行了模型分析，建立了DEM模型和三维空间最佳面积覆盖模型，考虑该矩形区域内地形表面的实际情况，综合影响模型准确程度的一系列因素，对其进行模型精确度的分析。问题一：根据已知测量点数据，利用二维差值法生成格网结构的数字高程模型，运用DEM三维地形地表面积递推算法求解地表面积，其精度用残差总和的大小与回归分析法进行综合评估。问题二：对于矩形区域的无盲区覆盖问题，建立了三维空间的随机最佳覆盖模型，运用分布式启发算法完成整个矩形区域内无盲区的覆盖问题。文章最后，对该文所应用的模型在其他

2、一些重要领域进行了简单的介绍，扩展了模型从而加强了它的普遍适用性。关键词：二维差值法 DEM模型 残差总和 回归函数 随机最佳模型 1 问题的提出要在长4000米，宽3000米的某矩形区域内进行一项野外作业，需要布设一些监控器。附件data5B.txt中给出了该区域的步长为5米的网格节点对应的海拔高度值及等高线图，其概貌如下图所示：问题一:试通过数学建模方法，估算所给矩形区域内海拔在12米以上部分的地表面积，并分析说明计算精度；问题二：如果要在该矩形区域内布设某型号的监控器，已知在无障碍情况下最远可观测距离为500米，为实现整个矩形区域的无盲区全覆盖监视，需研究在矩形区域内设置多少个监视器？其

3、最佳位置在何处？若在该区设置28个监控器，这些监控器应该设置在什么位置？可以覆盖矩形区域内的多大面积。2 问题的分析2.1问题一分析：已知该矩形区域的等高线图及相应海拔高度值（见附录），要对海拔在12米以上的部分地表面积进行计算。在计算实际地形的地表面积时，因其地形是随机起伏的，很难准确的运用函数来描述这种起伏状况，而用传统的数学方法又不易得到准确值，故运用一种基于逼近思想的递归算法来求解DEM模型，从而算出三维地形的地表面积。对其模型精度的分析评估中，影响其精度因素主要有地形表面的特征、原始数据的分布及密度、DEM表面的建模方法以及其表面特性等，而原始数据的内插法为直接影响因素，因此运用残差

4、总和的大小进行比较，再者结合回归函数分析与之比较，可知其精度较高，模型较为准确。2.2问题二分析：要实现对整个矩形区域内无盲区全覆盖监测，可以通过设计一个基于位置的算法来找到一条连接网络中任意S源节点和Sink指令中心的路径，并使该路径上所有点的最小被观察能力最大化，转化为无线传感器网络中的“最佳覆盖问题”，运用分布式启发算法进行求解。3 模型假设1）问题的描述涉及到地表的规模，当规模发生变化后，问题性质不发生变化。2）问题的出口条件定为判断各个小三角形面积是否小于阀值。3）监测器在任何情况下均可以达到最大范围的监测效果。4符号系统：表示x轴坐标;：表示y轴坐标;：表示z轴坐标;：三角形1的面

5、积;：三角形2的面积;：三角形面积;:第一点的坐标;:三角形边长和的一半;：第二点的坐标;：第三点的坐标;：第四点的坐标;:一点二点之间的距离;:一点三点之间的距离;:二点三点之间的距离;:一点四点之间的距离;:二点四点之间的距离;:三点四点之间的距离;：与两点之间的距离。S：残差总和y：线性函数回归y：二次函数回归y：负指数函数回归5模型的建立与求解5.1问题一针对问题一，在计算地表面积时，首先圈定一个多边形，因三维地形随机起伏，故此多边形内部的三维地形表面也是随机起伏的。在已知平面内建立空间直角坐标系O-xyz，将多边形的各个顶点通过鼠标在三维空间中进行三维拾取，然后从目标多边形ABCDE

6、（如图一）的某一个固定的顶点出发，依次连接各个顶点，这样便可把多边形分解为一个一个的三角形ABC（如图二），为了能够更加精确的计算出三角形固定的三维地形的表面积，再对三角形依照地形特征进行拆分，关键是要求出三角形内的一个点，这个点能够代表出这个地形的地表特征，将其与其余的点相连接，得到三个更小的三角形（如图三），以此类推，直到三角形的面积小于一个阀值或者拆分位于三角形的平面内，最后利用海伦公式，可得三角形面积。将逼近思想运用于本题，分割成n*n个目标多边形，把每个多边形分成三个三角形，运用海伦公式求此三角形的面积，利用循环解把n*n个目标多边形面积相加可得面积总和。 图一 目标多边形示意图 图

7、二 未分割的三角形示意图 图三 分割后的三角形示意图 求解如下：建立空间直角坐标系O-xyz，取四个峰顶为四个顶点，连接四个点可得到一个四边形，任意连接一对角线，将四边形分割成两个三角形（如下图四）利用海伦公式及逼近的思想，可近似的得到地表面积的大小。图四 将四边形分割为两三角形若把本题表面分解成3000*4000个矩形，把每个矩形分成2个三角形，利用海伦公式和MATLAB得出循环解求得总面积为.因此地表面积为。对运用DEM模型求得的三维地表面积大小的精确度进行残差总和和回归函数模型进行综合评估，公式内容如下：残差总和公式S=，其中残差总和越小，模型的精确度越高。线性函数回归y=+x+r二次函

8、数回归y=+x+x+r负指数函数回归y=e+r式中，r为回归方程的函数，是判断回归函数拟合效果的重要指标，运用MATLAB软件分别求出线性、二次、负指数函数回归三个函数各自的残差总和，由算法结果可知：负指数函数的残差总和最小，因此采用负指数函数回归作为对DEM模型精确度的分析。经MATLAB软件求得，该模型的计算误差约为1.02%，精确度相对较高。5.2问题二针对问题二，因为所有节点的监测半径是相同的，当找到一个所有节点覆盖半径的最小值r满足条件：只要经过监测器节点为圆心，r为半径所确定的多个圆内部就可以找到一条连接网络中S源节点与Sink指令中心的路径。求解过程如下：根据现有的3维WSN拓扑

9、图生成化简但不失地理特性的3维德洛内三角图D（x）（如下图五）留映射为对应的2维德洛内三角图D（x）（如下图六），顶点集就可以尽可能多的保持原有3维WSN拓扑图的基本地理特征。在保持3维WSN拓扑图一定级别的地理特征条件下，3维WSN拓扑图的覆盖即可转化为 D（x）的覆盖问题，故只需保证其构成的三角形可被传感器节点覆盖监测即可。图五 3维德洛内三角图图六 2维德洛内三角形示意图为了实现整个矩形区域的无盲区全覆盖监视，在该矩形区域内应设置监视器的数量如下图所示，图中所有圆的个数即为所要求得的监测器的数量，共有30个监测器，最有可能的位置便是在图中所示圆的中心处设置。图七 区域内监控器个数示意图如

10、果在该区域内设置28个监测器，最有可能的设置位置便是在图六2维德洛内三角形的各个顶点处，那样便可以得到三维地形的最佳覆盖面积。6 模型的评价和推广 6.1优点： 1）DEM模型求解面积具有客观性、实际性，在现实生活中易被采纳，具有可操作性实用价值。 2）递归算法能够灵活调整阀值，更好的控制模型的计算精度。 3）考虑较全面，运用较广泛，实际性强。6.2改进之处： 1）选择恰当的高程点来确定拆分三角形较为困难。 2）模型是在理想的情况下建立的，并没有考虑野外的动态因素，因此模型仍存在着不足，但总的来说，还是具有很好的借鉴意义和指导价值的。6.3模型的推广应用DEM模型已经在各领域均有广泛的应用，比

11、如线路勘测设计、水利建设工程、军事工程等等方面，对于自然灾难而形成的洪水、泥石流淹没区的估算，山区日照分析和GIS中的三维可视化，以及本文涉及的平面等高线图、立体等高线图，只要是与地理位置相联系的空间定位，均可以用到数字高程模型。7模型改进本文所建模型是从地势表面宏观方向考虑的，从而忽略了较为微小的一些真实地势概貌，若将插值单元的长度与宽度尽可能的缩小以至趋于无穷小，那么所建模型变更能反映出山势地貌的真实情况，计算出的地表面积以及监测器的合理布置的精确性也会有大大的提高。参考文献李志林，朱庆.数字高程模型.武汉：武汉测绘科技大学出版社，2004孙家广.计算机图形学（第三版）.北京：清华大学出版

12、社，2003任彦，张思东.线传感器网络三维空间最佳覆盖路由协议.电子学报，2006，2朱衡君.MATLAB语言及实践教程.北京：清华大学出版社，北京交通出版社，2005姜启源.数学模型.北京：高等教育出版社，1987 杨晓云，顾利亚. 字高程模型的误差处理与精度评估.铁道勘查，2004，5侯飞，韩奎峰.多分辨率DEM的插值残差计算及精度评价模型.工程勘察2010， 附录一:( 步长为5m的三维立体图形的程序)图为该区域等高线示意图clc, cleara=load(data1.txt);amin=min(min(a), amax=max(max(a)x0=0:5:4000; y0=0:5:300

13、0;xx0,yy0=meshgrid(x0,y0);mesh(xx0,yy0,a)v=-49,1,12,44,75,107,171,184:80:357,357:100:614,614;figure, c=contour(x0,y0,a,v); clabel(c)图为步长为5m的三维立体图形附录二：（地行地表面积的算法程序）clc, clear %该程序计算最小面积a=load(data1.txt);a=a;x0=0:5:4000; y0=0:5:3000;pp=csape(x0,y0,a)x=0:4000; y=0:3000;z=fnval(pp,x,y);m,n=size(z);s=0;f

14、or i=1:m-1 for j=1:n-1 p1=x(i),y(j),z(i,j); p2=x(i+1),y(j),z(i+1,j); p3=x(i+1),y(j+1),z(i+1,j+1); p4=x(i),y(j+1),z(i,j+1); p12=norm(p1-p2); p23=norm(p3-p2); p13=norm(p3-p1); p14=norm(p4-p1); p34=norm(p4-p3); if all(z(i,j),z(i+1,j),z(i+1,j+1)=12) z1=(p12+p23+p13)/2; s1=sqrt(z1*(z1-p12)*(z1-p23)*(z1-p

15、13); s=s+s1; end if all(z(i,j),z(i+1,j+1),z(i,j+1)=12) z2=(p13+p14+p34)/2; s2=sqrt(z2*(z2-p13)*(z2-p14)*(z2-p34); s=s+s2; end endends附录三：（实现无盲区全覆盖监视区域内设置的监视器个数的程序） MATLAB程序如下：clc, clearload pdataa=load( data1.txt);x0=0:5:4000; y0=0:5:3000;v=-49,1,12,44,75,107,171,184:80:357,357:100:614,614;c=contour(x0,y0,a,v); clabel(c)hold onplot(P1(1),P1(2),S)plot(P2(1),P2(