计算机地图制图的理论基础

1、第二章第二章 计算机地图制图计算机地图制图 的理论基础的理论基础目录：目录：2.1 初等几何学及其算法 2.2 图论 2.3 计算几何 2.4 图像处理的基本方法2.5 数字地面模型 2.1 初等几何学及其算法计算机地图制图几何元素间的关系：计算机地图制图几何元素间的关系：点点线线面面点点线线面面是在地理坐标空间而不是在屏幕坐标空间中计算是在地理坐标空间而不是在屏幕坐标空间中计算!1. 1. 点线关系点线关系 点在线上点在线上点线相离点线相离研究重点：研究重点：点与线段的侧位关系判断、点与线点与线段的侧位关系判断、点与线拓扑关系的判别方法及点到线的距离计算。拓扑关系的判别方法及点到线的距离计算

2、。 1.1 点线侧位关系判断点线侧位关系判断 设有一条直线，其方程为：设有一条直线，其方程为： ，则对于函，则对于函数数 ，任取空间一点，任取空间一点 ，有：，有：0CByAxCByAxyxf),(),(00yxm判断点线侧位关系的意义？判断点线侧位关系的意义？1.2 1.2 点、线关系的判别方法点、线关系的判别方法 点线关系判别的目的之一是确定点是否在线上。点线关系判别的目的之一是确定点是否在线上。 图图2-1 2-1 点线关系的判断（虚线为投影矩形）点线关系的判断（虚线为投影矩形）Ap1P2P3P4P5P6B1.3 1.3 点到线的距离计算点到线的距离计算 Ap1p2（a）Ap1p2（b）

3、图图2-2 点与线段距离的两种情形点与线段距离的两种情形点到线段的距离可能是该点与线段点到线段的距离可能是该点与线段某一端点某一端点的距离，的距离，也可能是点到线段的也可能是点到线段的垂距垂距。p1P2P3P4P5DA最远距离最近距离图图2-3 2-3 点与线的最远距离和最近距离点与线的最远距离和最近距离点到线的距离有最远距离和最近距离。点到线的距离有最远距离和最近距离。2. 2. 线线关系线线关系 相离相离共位共位相交相交线线关系判断的基础是：线线关系判断的基础是：两线段是否相交两线段是否相交,可由可由1.1简单推算之简单推算之.图图2-4 2-4 折线的单调链划分及其投影矩形折线的单调链划

4、分及其投影矩形l1l2l3l4l5l6k1k2k3LK两折线相交与否的判断两折线相交与否的判断第一步：第一步：生成单调链生成单调链(此图中此图中为关于纵坐标的单调链为关于纵坐标的单调链)第二步：第二步：计算每个单调链的计算每个单调链的最小投影矩形最小投影矩形第三步：第三步：两两判断最小投影两两判断最小投影矩形是否相交矩形是否相交,如相交如相交,才判才判断其对应单调链是否相交断其对应单调链是否相交.两两判断线段是否相交即可两两判断线段是否相交即可,但不是最优算法但不是最优算法.折线自相交的判断与此基本一样折线自相交的判断与此基本一样.3.3.点面关系点面关系 图图2-5 2-5 点与三角形的位置

5、关系点与三角形的位置关系1111),(cybxayxf2222),(cybxayxf3333),(cybxayxf0),(),(0),(),(0),(),(332211PPBBPPAAPPCCyxfyxfyxfyxfyxfyxf若满足：若满足：则点则点P位于三角形的内部，否则点位于三角形的内部，否则点P位位于三角形的外部。于三角形的外部。ABABBCBCCACA3.13.1点与三角形位置关系的计算点与三角形位置关系的计算 void CTView:OnLButtonUp(UINT nFlags, CPoint point) / TODO: Add your message handler cod

6、e here and/or call default/CView:OnLButtonUp(nFlags, point);if(m_DrawCurrent=2)float F1=f1(PointXyz2.x,PointXyz2.y);float F2=f2(PointXyz0.x,PointXyz0.y);float F3=f3(PointXyz1.x,PointXyz1.y);float F4=f1(float(mPointOrign.x),float(mPointOrign.y);float F5=f2(float(mPointOrign.x),float(mPointOrign.y);fl

7、oat F6=f3(float(mPointOrign.x),float(mPointOrign.y);if(F1*F40 & F2*F50 & F3*F60)MessageBox( 点在三角形内！点在三角形内！ );else MessageBox( 点在三角形外！点在三角形外！ ); ReleaseCapture();3.2 3.2 点与多边形位置关系的计算点与多边形位置关系的计算 判断点与多边形位置关系的夹角求和算法判断点与多边形位置关系的夹角求和算法(只适用于简单多边形只适用于简单多边形,对于带孔多边形的算法改进比较麻烦对于带孔多边形的算法改进比较麻烦)设有一简单设有一简

8、单n边形，其顶点可以表示为边形，其顶点可以表示为Pi( (xi,yi) )，i=1,2,=1,2,n，另有待判别的独立点，另有待判别的独立点A A。连接点。连接点A A与多边与多边形的各个顶点，计算其夹角和，且规定顺时针方向形的各个顶点，计算其夹角和，且规定顺时针方向旋转的角度为旋转的角度为正正，逆时针方向旋转的角度为，逆时针方向旋转的角度为负负。若。若有有在多边形外点在多边形内点A0A21111PPPPPPnniii图 2-8 P1P2P4P5P6PP2图 2-9P3P4P5PP3P6P1PXYO方位角求夹角的方法：在笛卡儿坐标系中，从在笛卡儿坐标系中，从x x轴正轴正向起逆时针旋转某一射线

9、得到向起逆时针旋转某一射线得到一个角度，可定义为该方向的一个角度，可定义为该方向的方位角。射线方位角。射线OPOP的方位角。方的方位角。方位角的取值范围是：位角的取值范围是： 3600判断点与多边形位置关系的判断点与多边形位置关系的铅垂线内点算法铅垂线内点算法(适用于带孔多边形适用于带孔多边形)基本思想基本思想: :从待判别点引铅垂线，由该铅垂线从待判别点引铅垂线，由该铅垂线（注意：是一条射线）（注意：是一条射线）与多边形交点个数的与多边形交点个数的奇奇偶性偶性来判断点是否在多边形内。来判断点是否在多边形内。 若交点个数为奇数，点在多边形内；若交点个数为奇数，点在多边形内； 若交点个数为偶数，

10、则该点在多边形外。若交点个数为偶数，则该点在多边形外。 A1A2P1P2P3P4P5图图2-11 2-11 由交点数奇偶性判断点面包含关系由交点数奇偶性判断点面包含关系铅垂线内点算法铅垂线内点算法 : :第一步第一步，计算多边形最小投影矩形，若点在最小投影矩形，计算多边形最小投影矩形，若点在最小投影矩形外，则点一定在多边形外，算法结束；否则执行第二步。外，则点一定在多边形外，算法结束；否则执行第二步。第二步第二步，设置记录交点个数的计数器，设置记录交点个数的计数器NumNum=0=0。第三步第三步，从待判断的点作铅垂线，顺次判断该铅垂线与多，从待判断的点作铅垂线，顺次判断该铅垂线与多边形各边是

11、否相交，若相交，求出交点并记录下来。每有边形各边是否相交，若相交，求出交点并记录下来。每有一次相交，把一次相交，把NumNum数值增加数值增加1 1。第四步第四步，若，若NumNum为偶数，则该点在多边形外；否则，该点为偶数，则该点在多边形外；否则，该点在多边形内。算法结束。在多边形内。算法结束。（a）图图2-12 铅垂线交于多边形的顶点铅垂线交于多边形的顶点（b）AAP1P2P3P4P1P2P3P4（a）（b）图图2-13 2-13 铅垂线与多边形的一边相重合铅垂线与多边形的一边相重合P1P2P3P4P5P6AP1P2AP3P4P5特殊情况的考虑：特殊情况的考虑：1. 1. 交点位于多边形顶

12、点交点位于多边形顶点 建立铅垂线的直线方程，判断该顶点前、后相邻建立铅垂线的直线方程，判断该顶点前、后相邻的两顶点是否在铅垂线的同侧，的两顶点是否在铅垂线的同侧，若在同侧，若在同侧，NumNum不不变，否则变，否则NumNum加加1 1。 2. 2. 铅垂线与多边形的一条边重合铅垂线与多边形的一条边重合 建立铅垂线的直线方程，判断与该边两端点相邻的建立铅垂线的直线方程，判断与该边两端点相邻的前、后两顶点是否在铅垂线的同侧，前、后两顶点是否在铅垂线的同侧，若在同侧，若在同侧，NumNum不变，否则不变，否则NumNum加加1 1。 部分源代码：部分源代码：void CDraw1View:judg

13、e2(float x, float y) float xmax=PointXyz0.x; float xmin=PointXyz0.x; float ymin=PointXyz0.y; float fy; /fy为待判断点与直线方程的交点的纵坐标为待判断点与直线方程的交点的纵坐标 int num=0; /记录待判断点与直线方程的交点的数目记录待判断点与直线方程的交点的数目 PointXyza.x=PointXyz0.x; PointXyza.y=PointXyz0.y; PointXyza+1.x=PointXyz1.x;PointXyza+1.y=PointXyz1.y; PointXyza

14、+2.x=PointXyz2.x; PointXyza+2.y=PointXyz2.y; PointXyza+3.x=PointXyz3.x; PointXyza+3.y=PointXyz3.y;for(int j=0;j=y&(PointXyzj.xx&xPointXyzj+1.x)|(PointXyzj+1.xx&xPointXyzj.x) / 纵坐标越往下，值越大纵坐标越往下，值越大 num=num+1; continue; else if(x=PointXyzj+1.x&fy=PointXyzj+1.y) / 交于多边形顶点时交于多边形顶点时 if(Po

15、intXyzj.xx&xPointXyzj+2.x)|(PointXyzj+2.xx&xy) /若前后相邻的两顶点在该顶点所做铅垂线分得异侧，则若前后相邻的两顶点在该顶点所做铅垂线分得异侧，则num+ num=num+1; else if(x=PointXyzj+1.x&x=PointXyzj+2.x&PointXyzj+2.yy) /若铅垂线与边部分重合若铅垂线与边部分重合 if(PointXyzj+3.xx&xPointXyzj.x)|(PointXyzj.xx&xPointXyzj+3.x) num=num+1; if(num%2=1) M

16、essageBox(点在多边形内！点在多边形内！); elseif(num%2=0) MessageBox(点在多边形外！点在多边形外！);4. 4. 线面关系线面关系 线面关系研究的重点问题是线面关系研究的重点问题是求线与面的相交求线与面的相交。 线段与多边形交线的算法线段与多边形交线的算法 ：第一步第一步，求多边形的最小投影矩形。，求多边形的最小投影矩形。第二步第二步，判断线段是否有端点在该最小投影矩形，判断线段是否有端点在该最小投影矩形中。若不在，结论为中。若不在，结论为“线段与多边形相离线段与多边形相离”，算，算法结束；否则，执行第三步。法结束；否则，执行第三步。第三步第三步，顺次判断

17、线段与多边形各边是否有交点，顺次判断线段与多边形各边是否有交点，若有交点，则求出并保存交点坐标。若有交点，则求出并保存交点坐标。第四步第四步，对交点坐标排序：计算各交点与线段，对交点坐标排序：计算各交点与线段一一端点端点的距离，然后按照距离由小到大对交点编号的距离，然后按照距离由小到大对交点编号排序。排序。第五步，按规律第五步，按规律连接各个交点，得到位于多边形内部的连接各个交点，得到位于多边形内部的交线。交线。p1p6p3p4p5图图2-14 线段与多边形相交时的交点连接规律线段与多边形相交时的交点连接规律p2p7p8p9p10p11p12p13p14Qq1q2q4q3q5q6q8q7q9q

18、10Kk2k3k1HM5. 5. 面面关系面面关系 任意两多边形求交问题解决的基础是两个简任意两多边形求交问题解决的基础是两个简单多边形单多边形求交求交、求差求差和和求并求并的算法。的算法。 5.1 5.1 计算简单多边形交集的算法计算简单多边形交集的算法 设有两个简单多边形：设有两个简单多边形：P=P1,P2,Pm，Q=q1,q2,qn，各多边形顶点各多边形顶点Pi、qj逆时针排列，逆时针排列，确定它们的确定它们的交交：F = PQ =k|kPkQ。例：例：p1p2p3p4p5p6q1q2q3q4q5q6q7k1k8k2k4k5k6图图2-15 2-15 简单多边形求交简单多边形求交k3k7

19、5.2 5.2 计算任意多边形交集的算法计算任意多边形交集的算法 例：例：平面上给定两个多边形平面上给定两个多边形P、Q（它们可以是简（它们可以是简单多边形，也可以是复杂多边形），单多边形，也可以是复杂多边形），P的外围的外围多边形为多边形为P0,内嵌内嵌m（m0 0）个岛屿多边形为）个岛屿多边形为P1、P2、Pm，Q的外围多边形为的外围多边形为Q0，内嵌，内嵌n（n0）个岛屿多边形为个岛屿多边形为Q1、Q2、Qn，各多边形顶，各多边形顶点逆时针排列，确定它们的交点逆时针排列，确定它们的交F = PQ =q|qPqQ 图图2-17 2-17 两复杂多边形求交两复杂多边形求交PQQ0Q1P1P0

20、P22.2 2.2 图论图论（后面介绍）（后面介绍）1 1、图论的起源与发展、图论的起源与发展 图论创立的标志：哥尼斯堡七桥问题的提出图论创立的标志：哥尼斯堡七桥问题的提出 图图2-18 2-18 哥尼斯堡七桥问题图示哥尼斯堡七桥问题图示ABCD问题：问题：“你能经你能经过每桥当且尽当过每桥当且尽当一次再返回出发一次再返回出发点吗？点吗？” ” 哈密尔顿回路问题、货郎哈密尔顿回路问题、货郎担问题、地图印刷的四色担问题、地图印刷的四色问题、拉姆塞问题问题、拉姆塞问题 2.2.图的概念图的概念 有向图示例有向图示例记为记为D Dv1v2v3e3e1e2有向边有向边端点端点起点起点终点终点v1v2v

21、3e3e1e2无向图示例无向图示例记为记为G G顶点顶点边边v3v1v2v4v5v6e1e2e3e4e5e7e8e6非简单有向图示例非简单有向图示例环环平行边平行边对称边对称边孤立顶点孤立顶点3. 3. 图的矩阵表示图的矩阵表示 邻接矩阵邻接矩阵(A)(A)是图的一种有效表示方法，图在计算机是图的一种有效表示方法，图在计算机中经常用其对应邻接矩阵来保存。所谓图的邻接矩中经常用其对应邻接矩阵来保存。所谓图的邻接矩阵，是指一个阵，是指一个v v v v阶矩阵。阶矩阵。 其中元素为其中元素为u(eu(ei i,e,ej j),),对对G G为为e ei i和和e ej j之间的边数；对之间的边数；对

22、D D为从为从e ei i和和e ej j之间的边数。之间的边数。所谓图的所谓图的关联矩阵关联矩阵(M)(M) ，是指一个，是指一个v v e e阶矩阵。其中阶矩阵。其中元素，对元素，对G G取取1 1，0 0；对；对D D取取1 1，-1-1，0 0。图的图的矩阵表示矩阵表示在矩阵论与图论之间架起了一座桥梁。在矩阵论与图论之间架起了一座桥梁。v1v2v3v4e1e2e3e4e5e6e7v11101v11110000v21021v21001011v30201v30000111v41110v40101100邻接矩阵A(G)关联矩阵M(G)v1v2v3v4e1e2e3e4e5e6e7无向图矩阵无向

23、图矩阵v1v2v3v4e1e2e3e4e5e6e7v11101v11110000v20021v2-1001011v30000v30000-1-1-1v40010v40-10-1100邻接矩阵A(D)关联矩阵M(D)v1v2v3v4e1e2e3e4e5e6e7有向图矩阵有向图矩阵（a）794532243（b）-7945-32-243图图2-23 2-23 加权图加权图. . （a a）加权无向图；）加权无向图； （b b）加权有向图）加权有向图2.3 2.3 计算几何计算几何 计算几何（计算几何（Computational GeometryComputational Geometry）是由）是由

24、函数逼近论、微分几何、代数几何、计算数学等形函数逼近论、微分几何、代数几何、计算数学等形成的一门边缘学科，研究几何信息的计算机表示、成的一门边缘学科，研究几何信息的计算机表示、分析和综合等。分析和综合等。计算几何在计算机辅助设计（计算几何在计算机辅助设计（CADCAD：Computer-Aided DesignComputer-Aided Design）、计算机辅助制造（）、计算机辅助制造（CAMCAM：Computer-Aided ManufactureComputer-Aided Manufacture）、计算机辅助地图）、计算机辅助地图制图（制图（CACCAC：Computer-Aide

25、d CartographyComputer-Aided Cartography）、图）、图形学、机器人技术、超大规模集成电路设计等诸多形学、机器人技术、超大规模集成电路设计等诸多领域有着十分重要的应用。领域有着十分重要的应用。 1. 1. 曲线拟合曲线拟合 定义：定义： 找出一条通过一组给定点的曲线是一个找出一条通过一组给定点的曲线是一个插插值问题值问题； 找出一条近似地通过一组给定点的曲线则找出一条近似地通过一组给定点的曲线则是是逼近问题逼近问题。两者统称曲线拟合。两者统称曲线拟合。 分段多项式插值法分段多项式插值法和和样条曲线插值法样条曲线插值法 2. 2. 凸壳凸壳 平面点集平面点集S

26、S的凸壳（的凸壳（Convex HullConvex Hull）或凸）或凸包或曰凸多边形是指包含包或曰凸多边形是指包含S S的最小凸集，通的最小凸集，通常用常用CHCH（S S）来表示。）来表示。 从几何的直观上判断，从几何的直观上判断，S S的凸壳表现为的凸壳表现为S S中任意两点所连的线段全部位于中任意两点所连的线段全部位于S S中。平面中。平面点集点集S S的凸壳边界的凸壳边界BCH(S)BCH(S)是一个凸多边形，是一个凸多边形，多边形的顶点必定为多边形的顶点必定为S S中的点。中的点。 凸壳是计算几何中最普遍、最基本的一凸壳是计算几何中最普遍、最基本的一种结构，在种结构，在CACCA

27、C中使用频繁。中使用频繁。 定义：定义：凸多边形直径凸多边形直径 又称为平面点集的直径或平面点集凸壳又称为平面点集的直径或平面点集凸壳的直径，定义为凸多边形顶点序列中的直径，定义为凸多边形顶点序列中距离最距离最大大的点对的连线。的点对的连线。 2.1 2.1 求解平面点集凸壳的算法求解平面点集凸壳的算法 图图2-26 2-26 格雷厄姆算法格雷厄姆算法求解群点凸壳的过程求解群点凸壳的过程x图图2-27 2-27 夹角序列夹角序列算法算法2.2 2.2 求凸多边形直径的算法求凸多边形直径的算法 3.Voronoi3.Voronoi图图 3.1 Voronoi3.1 Voronoi图的定义图的定义

28、 图图2-28 2-28 平面两点的平面两点的VoronoiVoronoi图图Lpjpip1p2L1LrV (p1)V (p2)设设P P1 1，P P2 2是平面上两点，是平面上两点，L L是是P P1 1P P2 2的的垂直平分线，垂直平分线，L L将平面分成两部分将平面分成两部分Lr和和Ll。位于。位于Ll内的点具有特性：内的点具有特性：d d( (P Pi i，P P1)1)d d( (P Pi，P P2 2) )，其中，其中d d( (Pi，Pl) )表示表示P Pi i，P Pl l间的间的欧几里德距离欧几里德距离。位于位于Ll内的点比平面上的其它点更内的点比平面上的其它点更接近点

29、接近点P Pl l。换句话说，。换句话说，Ll内的点是内的点是比平面上其它点更接近比平面上其它点更接近P Pl l的点的轨的点的轨迹，记为迹，记为V(P1)。同理，同理，Lr内的点内的点是比平面上其它点更接近是比平面上其它点更接近P P2 2的点的的点的轨迹，记为轨迹，记为V(P2)。给定平面上给定平面上n个点的点集个点的点集S= P1, P2, Pn。把上面的定义推广，定义。把上面的定义推广，定义V(Pi)为比其为比其它点更接近它点更接近Pi的点的轨迹，是的点的轨迹，是n-1个半平面的个半平面的交，它是一个不多于交，它是一个不多于n-1条边的凸多边形域，条边的凸多边形域，称为关联于称为关联于

30、Pi的的Voronoi多边形多边形或或关联于关联于Pi的的Voronoi域域。P1P2P3P4P5L1L2L3L4L5图图2-29 平面点集的平面点集的Voronoi和和Delaunay三角网三角网Voronoi顶点顶点 Voronoi边边 对于对于S S中的每一个中的每一个点都可以作一个点都可以作一个VoronoiVoronoi多边形，多边形，这样的这样的n n个个VoronoiVoronoi多边形组成的图称多边形组成的图称为为VoronoiVoronoi图图，记，记为为Vor(SVor(S) )。Voronoi图的实质图的实质Voronoi图可以理解为对空间的一种分割方式图可以理解为对空间

31、的一种分割方式（一个（一个Voronoi多边形内的任意一点到本多边形内的任意一点到本Voronoi多边形中心点的距离都小于其到其它多边形中心点的距离都小于其到其它Voronoi多边形中心点的距离）多边形中心点的距离），也可以理解，也可以理解为对空间的一种内插方式（空间中的任何一为对空间的一种内插方式（空间中的任何一个未知点的值都可以由距离它最近的已知点，个未知点的值都可以由距离它最近的已知点，即采样点的值来替代）。即采样点的值来替代）。4. Delaunay三角网三角网 4.1 Delaunay三角网的定义三角网的定义 有公共边的有公共边的Voronoi多边形称为相邻的多边形称为相邻的Voro

32、noi多边形，多边形，连连接所有相邻接所有相邻Voronoi多边形的生长中心所多边形的生长中心所形成的三角网称为形成的三角网称为Delaunay三角网三角网。 4.2 Delaunay三角网的性质三角网的性质 （1）它是）它是唯一唯一的；的；（2）三角形的外围边界构成群点的）三角形的外围边界构成群点的凸壳凸壳；（3）任意三角形的外接圆中没有其它点）任意三角形的外接圆中没有其它点外接外接圆规则圆规则；（4）三角形最大限度地保持均衡，避免狭长三角）三角形最大限度地保持均衡，避免狭长三角形出现形出现最大最小角规则最大最小角规则；（5） Delaunay三角网是平面图，遵守平面图形三角网是平面图，遵守

33、平面图形的欧拉定理；的欧拉定理；（6）Delaunay三角网最多有三角网最多有3n-6条边和条边和2n-5个三个三角形，这里角形，这里n是点数；是点数；（7）Delaunay三角网和三角网和Voronoi图是图是对偶对偶，得到，得到一个就很容易得到另一个。一个就很容易得到另一个。4.3 Delaunay三角网常见算法三角网常见算法 静态算法静态算法动态算法动态算法射线扫描算法（Radial sweeP）递归分割算法（Recursive sPlit）分治算法（Divided-and-conquer）渐次算法（SteP-by-steP）层次式修改算法（Modified hierarchical）生

34、长算法（Incremental）生长式删除重建算法（Incremental delete-and-build）2.4 2.4 图像处理的基本方法图像处理的基本方法1. 1. 灰度值变换灰度值变换 45分割型非线性线性分线段性临界值操作原始灰度值新灰度值反转型255255100100200200图图2-32 2-32 灰度值变换的不同传递函数曲线灰度值变换的不同传递函数曲线图图2-33 2-33 在灰度值在灰度值1010上作临界值操作上作临界值操作2. 2. 两个栅格图像的算术组合运算两个栅格图像的算术组合运算 3. 3. 扩张扩张 2.5 2.5 数字地面模型数字地面模型2.5.1 DEM2.

35、5.1 DEM概述概述2.5.2 DEM2.5.2 DEM建立建立DEMDEM的数据获取的数据获取DEMDEM的建立方法的建立方法2.5.3 DEM2.5.3 DEM应用应用2.5.1 DEM2.5.1 DEM概述概述DEMDEM，(Digital Elevation Models)(Digital Elevation Models)，是国家基，是国家基础空间数据的重要组成部分，它表示地表区域础空间数据的重要组成部分，它表示地表区域上地形的上地形的三维向量三维向量的的有限有限序列，即地表单元上序列，即地表单元上高程的集合高程的集合，数学表达为：，数学表达为：z=f(xz=f(x，y)y)。 D

36、TMDTM：当：当z z为其它二维表面上为其它二维表面上连续变化连续变化的的地理特地理特征征，如地面温度、降雨、地球磁力、重力、土，如地面温度、降雨、地球磁力、重力、土地利用、土壤类型等其他地面诸特征，此时的地利用、土壤类型等其他地面诸特征，此时的DEMDEM成为成为DTM(Digital Terrain Models)DTM(Digital Terrain Models)。 概述：概述：DEM 与与 DTM的区分的区分数字高程模型数字高程模型( (Digital Elevation Digital Elevation ModelModel，DEMDEM) )：研究地面起伏。：研究地面起伏。数

37、字地形模型数字地形模型( (Digital Terrain Digital Terrain ModelModel，DTMDTM) )：含有地面起伏和属：含有地面起伏和属性性( (如坡度、坡向等如坡度、坡向等) )两个含义，是两个含义，是DEMDEM的进一步分析。的进一步分析。概述：概述：DEM的表示方法的表示方法概述：概述：DEM的的线模式线模式表示表示描述高程曲线的描述高程曲线的等高线等高线；数字化现有等高线地图产生的数字化现有等高线地图产生的DEMDEM比比直接直接利用航空摄影测量方法产生的利用航空摄影测量方法产生的DEMDEM质量要差；质量要差；数字化的等高线对于计算坡度或生成着色数字化

38、的等高线对于计算坡度或生成着色地形图不十分适用。地形图不十分适用。概述：等高线模式概述：等高线模式 等高线通常被存储成一个等高线通常被存储成一个有序有序的的坐标点序列坐标点序列，可，可以认为是一条带有高程值属性的以认为是一条带有高程值属性的简单多边形简单多边形或多边形或多边形弧段。由于等高线模型只是表达了区域的弧段。由于等高线模型只是表达了区域的部分高程值部分高程值，往往需要一种往往需要一种插值方法插值方法来计算落在来计算落在等高线以外等高线以外的的其他其他点点的高程，又因为这些点是落在两条等高线包围的区的高程，又因为这些点是落在两条等高线包围的区域内，所以，通常只要使用域内，所以，通常只要使

39、用外包的外包的两条等高线的高程两条等高线的高程进行进行插值插值。 概述：概述：DEM的的点模式点模式表示表示高程矩阵高程矩阵( (规则矩形格网规则矩形格网) )，与栅格地图相同。，与栅格地图相同。表示方法：将区域划分成网格，记录每个网格的表示方法：将区域划分成网格，记录每个网格的高程；高程；线模型到高程矩阵的转换。线模型到高程矩阵的转换。优点：计算机处理以栅格为基础的矩阵很方便，优点：计算机处理以栅格为基础的矩阵很方便，使高程矩阵成为最常见的使高程矩阵成为最常见的DEMDEM；缺点：在平坦地区出现大量数据冗余；若不改变缺点：在平坦地区出现大量数据冗余；若不改变格网大小，就不能适应不同的地形条件

40、；在视线计格网大小，就不能适应不同的地形条件；在视线计算中过分依赖格网轴线。算中过分依赖格网轴线。概述：概述：GRID模式模式 规则格网法是把规则格网法是把DEMDEM表示成表示成高程矩阵高程矩阵，此时，此时，DEMDEM来源于直接规则矩形格网采样点或由不规则离散数据来源于直接规则矩形格网采样点或由不规则离散数据点内插产生。点内插产生。 结构简单结构简单，计算机对矩阵的，计算机对矩阵的处理处理比较比较方便方便，高程，高程矩阵已成为矩阵已成为DEMDEM最通用最通用的形式。高程矩阵特别的形式。高程矩阵特别有利于有利于各各种应用。种应用。 概述：概述：GRID模式的缺点模式的缺点GridGrid系

41、统有下列系统有下列缺点缺点：1 1、地形简单的地区存在、地形简单的地区存在大量冗余数据大量冗余数据；2 2、如不改变如不改变格网大小格网大小, ,则则无法适用无法适用于起于起伏程度不同的地区；伏程度不同的地区；3 3、对于某些特殊计算如、对于某些特殊计算如视线视线计算时，格计算时，格网的网的轴线方向被夸大轴线方向被夸大；4 4、由于栅格过于粗略，、由于栅格过于粗略，不能精确不能精确表示地表示地形的关键特征形的关键特征, ,如山峰、洼坑、山脊等；如山峰、洼坑、山脊等； 概述：不规则三角网概述：不规则三角网( (TINTIN) ) TINTIN（Triangulated Irregular Net

42、workTriangulated Irregular Network) )表示法利表示法利用所有采样点取得的离散数据，按照用所有采样点取得的离散数据，按照优化组合优化组合的原则，的原则，把这些离散点把这些离散点( (各三角形的顶点各三角形的顶点) )连接成相互连续的连接成相互连续的三三角面角面( (在连接时，尽可能地确保每个三角形都是在连接时，尽可能地确保每个三角形都是锐角锐角三角形三角形或是三边的或是三边的长度近似长度近似相等相等DelaunayDelaunay) )。 因为因为TINTIN可根据地形的可根据地形的复杂程度复杂程度来确定采样点的来确定采样点的密密度度和和位置位置，能，能充分表

43、示充分表示地形特征点和线，从而地形特征点和线，从而减少了减少了地形较平坦地区的地形较平坦地区的数据冗余数据冗余。 概述：概述：TINTIN的三角剖分的三角剖分概述：概述：TINTIN模型的存储方式模型的存储方式NoXYZ190.010.043.5250.710.067.3367.223.962.6:1010.090.081.0概述：概述：TINTIN模型的表现模型的表现概述：概述：TINTIN小结小结表示方法：表示方法：将区域划分为相邻的三角面网络，区将区域划分为相邻的三角面网络，区域中任意点都将落在三角面顶点、线或三角形内。域中任意点都将落在三角面顶点、线或三角形内。落落在顶点上在顶点上其高

44、程与顶点相同；落其高程与顶点相同；落在线上在线上则由两个则由两个顶点线性插值得到；落顶点线性插值得到；落在三角形内在三角形内则由三个顶点插则由三个顶点插值得到。值得到。生成方法：生成方法：由不规则点、矩形格网或等高线转换由不规则点、矩形格网或等高线转换而得到。而得到。TINTIN允许在地形复杂地区收集较多的信息，而在允许在地形复杂地区收集较多的信息，而在简单的地区收集少量信息，避免数据冗余。简单的地区收集少量信息，避免数据冗余。对于某些类型的运算比建立在数字等高线基础上对于某些类型的运算比建立在数字等高线基础上的系统更有效，如坡度、坡向等的计算。的系统更有效，如坡度、坡向等的计算。概述：概述：

45、建立建立DEMDEM的目的的目的 1 1）作为国家地理信息的基础数据；）作为国家地理信息的基础数据； 2 2）土木工程、景观建筑与矿山工程规划与设计；）土木工程、景观建筑与矿山工程规划与设计； 3 3）为军事目的而进行的三维显示；）为军事目的而进行的三维显示； 4 4）景观设计与城市规划；）景观设计与城市规划； 5 5）流水线分析、可视性分析；）流水线分析、可视性分析； 6 6）交通路线的规划与大坝选址；）交通路线的规划与大坝选址； 7 7）不同地表的统计分析与比较；）不同地表的统计分析与比较； 8 8）生成坡度图、坡向图、剖面图、辅助地貌分析、估计侵蚀和径流等；）生成坡度图、坡向图、剖面图、

46、辅助地貌分析、估计侵蚀和径流等； 9 9）作为背景叠加各种专题信息如土壤、土地利用及植被覆盖数据等，以）作为背景叠加各种专题信息如土壤、土地利用及植被覆盖数据等，以进行显示与分析；进行显示与分析； 1010）与）与GISGIS联合进行空间分析；联合进行空间分析； 1111）虚拟现实）虚拟现实(Virtual Reality)(Virtual Reality)； 此外，从此外，从DEMDEM还能派生以下主要产品：平面等高线图、立体等高线图、等还能派生以下主要产品：平面等高线图、立体等高线图、等坡度图、晕渲图、通视图、纵横断面图、三维立体透视图、三维立体彩色图坡度图、晕渲图、通视图、纵横断面图、三

47、维立体透视图、三维立体彩色图等。等。 DEMDEM数据来源数据来源DEMDEM数据采集数据采集数字摄影测量：数字摄影测量：利用带自动记录装置的立体测利用带自动记录装置的立体测图仪或立体坐标仪、解析测图仪及数字摄影测量图仪或立体坐标仪、解析测图仪及数字摄影测量系统，进行人工、半自动或全自动的量测。其原系统，进行人工、半自动或全自动的量测。其原理是在摄影图的基础上利用测图仪进行测量。理是在摄影图的基础上利用测图仪进行测量。现有地图数字化：现有地图数字化：对已有地图上的信息对已有地图上的信息( (如等如等高线高线) )进行数字化。进行数字化。地面测量：地面测量：利用自动记录的测距经纬仪在野外利用自动

48、记录的测距经纬仪在野外实地测量。实地测量。空间传感器：空间传感器：利用利用GPSGPS，结合雷达和激光测高，结合雷达和激光测高仪采集数据。仪采集数据。数字摄影测量采样点的选取数字摄影测量采样点的选取沿等高线采样：沿等高线采样：主要用于山区采样。主要用于山区采样。规则网格采样：规则网格采样：按规则矩形网格进行采样，按规则矩形网格进行采样，可直接生成规则矩形格网的可直接生成规则矩形格网的DEMDEM数据。数据。渐进采样：渐进采样：根据地形使采样点合理分布，根据地形使采样点合理分布，即平坦地区采样点少，地形复杂区采样点多。即平坦地区采样点少，地形复杂区采样点多。选择采样：选择采样：根据地形特征进行采

49、样，如沿根据地形特征进行采样，如沿山脊线、山谷线等进行采集。山脊线、山谷线等进行采集。混合采样。混合采样。注意：所有采集的数据都要按一定注意：所有采集的数据都要按一定的空间插值方法转换成点模式格式的空间插值方法转换成点模式格式数据。数据。2.5.2 2.5.2 DEMDEM的生成的生成方法：方法：1 1、人工格网法、人工格网法2 2、三角网法、三角网法3 3、立体像对法、立体像对法4 4、曲面拟合法、曲面拟合法5 5、等值线插值法、等值线插值法人工格网法人工格网法在地形图上蒙上格网，在地形图上蒙上格网，逐格逐格读取读取中心点中心点或或交点交点的高程值。的高程值。三角网法三角网法 对有限个离散点

50、，对有限个离散点，每三个每三个邻近点邻近点联结成联结成三角形，三角形，每个三角形代表一个每个三角形代表一个局部平面局部平面，再根据每个平面方，再根据每个平面方程，可计算程，可计算各格网点各格网点高程，生成高程，生成DEMDEM。 构三角网的要求构三角网的要求应尽可能保证每个三角形是锐角三角应尽可能保证每个三角形是锐角三角形或三边的长度近似相等，避免出现形或三边的长度近似相等，避免出现过大的钝角和过小的锐角。过大的钝角和过小的锐角。 角度判断法建立角度判断法建立TINTIN当已知三角形的两个顶点后，利用当已知三角形的两个顶点后，利用余余弦定理弦定理计算备选第三顶点的三角形内计算备选第三顶点的三角

51、形内角的大小，选择最大者对应的点为该角的大小，选择最大者对应的点为该三角形的第三顶点。三角形的第三顶点。 将原始数据分块将原始数据分块 检索所处理三角形邻近点检索所处理三角形邻近点C1C2C3确定第一个三角形确定第一个三角形iCCmax则C为该三角形第三顶点 AB构网示意图构网示意图与与A A点距离点距离最近的点最近的点哪个内哪个内角最大角最大iiiiibacbaC2cos222三角形的扩展三角形的扩展对每一个已生成的三角形的新增加的两对每一个已生成的三角形的新增加的两边，按角度最大的原则向外进行扩展，边，按角度最大的原则向外进行扩展，并进行是否重复的检测。并进行是否重复的检测。向外扩展的处理

52、：若从顶点为向外扩展的处理：若从顶点为P P1 1(X(X1 1,Y,Y1 1), ), P P2 2(X(X2 2,Y,Y2 2), P), P3 3(X(X3 3,Y,Y3 3) )的三角形之的三角形之P P1 1P P2 2边向外扩边向外扩展，应取位于直线展，应取位于直线P P1 1P P2 2与与P P3 3异侧的点异侧的点 异则判断异则判断0)()(),(1212112YYXXXXYYYXFp3p2若备选点P之坐标为（X，Y）重复与交叉的检测：任意一边最多只能是两个三角形的公共边。p1立体像对法立体像对法资料来源于张超主编的资料来源于张超主编的地理信息系统教程地理信息系统教程所配光盘

53、所配光盘曲面拟合法曲面拟合法 根据根据有限个有限个离散点的高程，采用离散点的高程，采用多项式多项式或或样条函数样条函数求得求得拟合公式拟合公式，再逐个计算各点的高程，得到拟合的再逐个计算各点的高程，得到拟合的DEMDEM。可反映。可反映总的地势总的地势，但，但局部局部误误差差较大较大。可分为：。可分为：整体拟合：根据研究区域内整体拟合：根据研究区域内所有采样点所有采样点的观测值建立的观测值建立趋势面模型趋势面模型。特。特点是不能反映内插区域内的局部特征。点是不能反映内插区域内的局部特征。局部拟合：利用局部拟合：利用邻近的邻近的数据点数据点估计估计未知点的值，能未知点的值，能反映局部反映局部特征

54、。特征。等高线插值法等高线插值法2.5.3 DEM2.5.3 DEM的应用的应用1 1、基于、基于DEMDEM的信息提取的信息提取2 2、等高线的绘制、等高线的绘制3 3、基于、基于DEMDEM的可视化分析的可视化分析1 1、三维景观、三维景观2 2、数码城市和虚拟现实、数码城市和虚拟现实3 3、DEMDEM在工程上的应用在工程上的应用概述应用：概述应用：应用算法：应用算法：三维景观三维景观数码城市和虚拟现实数码城市和虚拟现实City ModelDOMDEMDLGAttribute RDB数码深圳数码深圳3D 3D 建筑建筑DEM+DOM+DLG交通行业：数字公路交通行业：数字公路DEMDEM的土石方计算的土石方计算立体计算线路挖土、石方量立体计算线路挖土、石方量坡度的计算坡度的计算YZZZZXZZZZYX22t