第二章 计算机地图制图的基本方法1

1、1/60 计算机地图制图计算机地图制图 是以地图学理论为指导，按一定的数学法则，是以地图学理论为指导，按一定的数学法则，利用计算机及其输入输出设备作制图工具，应用数利用计算机及其输入输出设备作制图工具，应用数据库技术和图形的数字化处理方法，实现解决地图据库技术和图形的数字化处理方法，实现解决地图信息的获取、变换、传输、识别、存储、处理和显信息的获取、变换、传输、识别、存储、处理和显示，最后以自动的或人机结合的方式输出地图。示，最后以自动的或人机结合的方式输出地图。第二章 计算机地图制图的基本方法2/60第一节 坐标变换一、概述第二章 计算机地图制图的基本方法 计算机地图制图的成图系统包括：数据

2、采集设备、计算机、输入输出装置及各种相关软件。 数据采集数据采集由测量外业完成，地图的生成过程由计算机系统完成。 计算机系统中的图形显示设备、图形输出设备、图形录入设备及制图使用的测量数据，都涉及定位（点）及坐标系的概念，测量数据的采集和绘制成的地图，采用的是大地坐标系，而上述计算机外围设备采用的是与大地坐标系不同的用户坐标系或称设备坐标系，这就必然出现在利用这些设备录入、显示或输出地图时，需要进行不同坐标系之间进行坐标变换。3/60 大比例尺数字测图系统中，大地坐标是采用高斯克吕格平面坐标系或独立坐标系。测图成果一般是在平面地形图上加注高程和绘制等高线。 由于计算机屏幕对观察者也相当于平面绘

3、图坐标，因此二维地图的录入过程、屏幕输出或绘图仪输出，类同于在图纸上绘图或是在图纸上表示的地图。 大地坐标和设备坐标的区别：大地坐标和设备坐标的区别： 空间与平面位置的不同 大地坐标系的原点可根据测量的实际需要取一参考点。数值可以在很大范围内变化。而绘图坐标都是以绘图设备的某一固定参考点为原点（显示屏左上角点、绘图仪左下角点），坐标数值变化范围很小。4/60 坐标系的尺度及取值范围不同 大地坐标一般以m、km为单位，数值可以是任意实数，而绘图设备的坐标单位、取值范围与绘图设备的技术性能有关，以设备的最小分辨率为单位，如显示器为像素，绘图仪为绘图笔移动的步长，取值一般是正整数，取值范围对分辨率为

4、640480的显示器，水平方向（屏幕坐标系X轴）取值范围是0639，垂直方向（屏幕坐标系Y轴）的取值范围0479；对滚筒绘图仪在滚筒的轴向（X轴）取值范围取决于滚筒的长度，而走纸方向（Y轴）取值范围可以很大。 外业测量采集的大地坐标数据，经过处理后需以图形方式输出时，要进行坐标变换，把大地坐标转换为绘图坐标，以符合各种图形输出设备的绘图坐标范围。从图形设备输入数据时，要把绘图坐标转换为大地坐标，因此坐标变换是数字绘图软件中常用的算法。 大地坐标和设备坐标的区别5/60 二、大地坐标系到屏幕坐标系的变换二、大地坐标系到屏幕坐标系的变换 图(a) 大地坐标系中的某点P（Xt，Yt），其所在图幅的范

5、围由其西南角坐标（Xn，Yn）和东北角坐标（Xm，Ym）决定；图（b） 在屏幕坐标系中的点P（Xp，Yp），显示屏上图幅显示范围由左上角坐标（X0，Y0）和右下角坐标（X1,Y1）决定。大地坐标系到屏幕坐标系的变换公式为：)()(010ntYPntXPXXKYYYYYKXX6/60 三、大地坐标系到绘图仪坐标系的变换由于 Kx与Ky的值不同，变换中取较小者作为变换系数。 图1(c)中所示为绘图仪坐标系中的某点P（Xh，Yh），绘图仪上图幅的范围由左下角坐标（Xa，Ya）和右上角坐标（Xb，Yb）决定。则大地坐标系到绘图仪坐标系的变换公式为：)/()()/()(0101nmYnmXXXYYKYY

6、XXK式中：Kx ，Ky为坐标转换系数三、大地坐标系到绘图仪坐标系的变换)()(ntahntahXXMYYYYMXX7/60 M为变换的比例系数，即待绘图的比例尺，由大地坐标系的单位与绘图笔坐标系的单位确定。四、同一坐标系的变换 同一坐标系的坐标平移变换、比例变换和旋转变换对于二维平面图形是比较简单的，相应的变换公式如下：8/60 （1）坐标平移变换yyyxxx式中：x，y -原坐标系的坐标 x,y-平移后的坐标系坐标 x,y-新坐标原点在原坐标系中的位置。如图（a)9/60 (2)坐标比例变换式中： （x,y）,(x,y)-新旧坐标系中的坐标 Kx，Ky-X轴和Y 轴方向上新旧坐标单位长度之

7、比。如图（b） ykyxkxyx10/60 sincossincosxyyyxx(3)坐标旋转变换 新旧坐标系的原点为同一点。而相应坐标轴之间的夹角为，即坐标轴转动了角度。设定逆时针方向为的正方向，如图（c）。11/60 第二节、图形绘制的数学基础一、绘制直线的函数 计算机系统中的图形输出设备，可以识别程序中绘制直线的指令，在图形屏幕上或绘图笔绘出相应的直线段。在绘图时，一般需要按照输出图形的比例要求，对绘图坐标进行变换。通过对x和y方向的比例系数的分别控制，可以对图形进行线性变换。 平面直线可以由两个点唯一地确定，因此绘制直线的函数一般只需两个参数（两个点的坐标）。同时由于数字绘图软件所处理

8、的主要是直线段，直线函数的变量相应为线段的两个端点坐标。绘制直线的函数一般形式为：),(2211yxyxline12/60 第二节、图形绘制的数学基础二、绘制直线的算法 在图形设备上生成直线时，是按照直线的延伸方向不断地生成光点的轨迹或绘出微小的线段，光点的间距及绘图笔移动光点的间距及绘图笔移动的距离称为步长。的距离称为步长。实际生成的直线是连续的像素或连续折线组成的。由于图形设备的分辨率限制，实际生成的点有可能偏离直线的理论位置，要确保直线生成的质量，除使用高质量的计算机设备外，还要采用高质量和高效率的算法。绘制直线的算法很多，下面介绍两种较常用的算法。13/60 点， N1斜率为，由于 ,

9、则tantan，N1线位于NM线上方，下一次就在X方向绘出一个步长的位移；如果= ， 即tan=tan ，说明点位于NM方向上，下次仍在x方向前进一个步长；当 ，即tan0 ，xm 0 判别i点位置偏差可用如下公式： imimmimmiixxxyxyxyxytantanimmiixyxyf仍自N点起，在y方向绘出单位步长到达1点，1点的坐标为（xn ,y n+1),判别式为：0) 1(1mnmnmmnnmmnxfxxyxyxyxyf 自点1向x方向步进一个单位到达2点，2点的坐标为（xn+1,y n+1),判别式为：mmmnmmnnmmnyfyxxyxyxyxyf12) 1() 1(第二节、图

10、形绘制的数学基础 设有位于直线理论位置的M点与位于实际位置的某点i。其中i=1，2，3n，坐标的单位为绘图仪的步长，则其斜率差为：15/60 依次类推，可分析得到在第一象限内的偏差判别的简化公式为： 当f i =0时，在x方向给出一个单位步长： f i+1 = f i-ym第二节、图形绘制的数学基础对于其它象限，可以总结出相应的简化判别公式，如表1表1 偏差判别公式 f i =0f i 0时，点位于直线以上的平面；当点满足f(x,y)0时，点位于直线以下的平面；当点满足f(x,y)=0时，点位于直线上。 第二节、图形绘制的数学基础 绘制直线时，每步进一个步长即根据点的当前位置(x,y)计算f(

11、x,y)，从而确定与标准直线的偏移，然后可以决定下一步的绘制方向。17/60 3、数值微分法（DDA，digital differential analyzer) 即绘制的每一步在X和Y方向的步长之比为常数。设当前位置的坐标为(x,y)，在X方向上的步长为x ，则Y方向应移动的步长为y=kx，该位置的坐标是（x+x ，y+kx ）。同样如果以Y方向上的步长y为依据，下一位置的坐标应该是（x+y/K ，y+y） 。根据选择步长的方式不同，DDA算法又可分为简单DDA和对称DDA。对直线y= f(x),其一阶导数为：df/dx=y/x=k (k为常数）第二节、图形绘制的数学基础18/60 (1)简

12、单DDA算法 简单DDA算法选择|x|和|y|较大者作为步长。一般的判断准则是：当直线的斜率(k = dy/dx= y/x)的绝对值|k|1时，选择|y|为单位步长。这样可以保证每一步进，至少在一个方向上有一个步长的移动，避免重复绘制同一点。第二节、图形绘制的数学基础19/60 第二节、图形绘制的数学基础（2）对称DDA算法 由上式确定的x方向和y方向的步进步长为： 为了避免除法运算，人们又设计了对称DDA算法：当直线的两端点分别为N(xn，yn）、M（xm，ym）时，选择一整数n使下式成立：1)2/ | ,2/ |max(|2/1nnmnnmyyxxnnmnnmyyyxxx2/ |2/ |

13、上式中虽有除法运算，但因除数是2n ，能用算术右移运算方便地实现；利用下式对 和 进行算术左移还可以计算出n：nnmnmnyyxx2|)| |,max(|21|nmxx|nmyy20/60 第二节、图形绘制的数学基础三、生成圆和圆弧的算法 生成圆及圆弧函数的一般形式为：RyxyxF22),(圆的具体表示形式有： 圆心坐标及半径表示法； 用位于圆上的三个点的坐标表示法。圆弧的表示方法有：圆弧的圆心、圆弧的起点及圆心角表示法；圆弧的起点、终点及圆弧上任一点表示法等。 在计算机图形输出设备上，生成圆或圆弧的算法也有逐点比较法、Bresenham法等多种算法。21/60 第二节、图形绘制的数学基础 1

14、、 逐点比较算法逐点比较算法生成圆弧的基本思想，同直线的逐点比较算法类似。自起点开始每步进一个步长，即与理论圆弧进行比较，根据生成点的位置偏移量决定下一步进的方向，绘制下一线段，这样绘出来的圆弧实际上是一条台阶状的折线，但由于步长很小（0.1mm），人眼看上去是一条光滑的曲线。22/60 第二节、图形绘制的数学基础 2、 Bresenham算法算法的大意是：自圆弧起点每步进一个步长都选择在变化最大的方向上，在另一方向是否步进，先要进行当前点位于圆内、圆上或圆外的判断，再据判断结果确定下次步进的方向，并步进一个步长。 确定一个点与圆的相对位置的判别函数为：当点位于圆内时，当点位于圆外时，当点位于

15、圆上时，222),(ryxyxf0),(yxf0),(yxf0),(yxf 如果中点M位于圆外，则SE点更接近圆弧；若M点位于圆内，则E点更接近圆弧。23/60 第二节、图形绘制的数学基础 判断M点位置的函数是2222/11)2/1, 1(ryxyxfdpppp如果d=0，选择SE为所绘圆弧的下一点，其坐标是下一次判别中点的函数为1, 1ppyx522/32)2/3, 2(2222ppppppyxdryxyxfd24/60第二节、图形绘制的数学基础四、任意曲线的生成简述 生成任意曲线的算法，一般是利用曲线上或曲线附近已知的若干控制点坐标，首先生成位于曲线位置上的折线，再对折线进行平滑处理，也就

16、是所谓曲线的拟合算法。25/60 第三节、图形裁剪 在计算机地图制图过程中，会遇到图幅划分及在图形编辑过程中对某个区域进行局部放大的问题，这些问题要求确定一个区域，并使区域内的图形能显示出来，而将区域之外的图形删去（不显示或分段显示），这就是所谓的图形裁剪，这里提到的区域也称窗口，根据区域的形状窗口分为矩形或任意多边形。 图形裁剪的基本目的是清除窗口以外的图形。 图形裁剪的基本过程：首先要求判明图形是否在窗口内，并计算出图形元素与窗口边界线的交点，正确选取显示部分的图形，将内容显示在规定形状区域（窗口）内。一、图形裁剪的基本理论26/60 第三节、图形裁剪二、线段、圆和曲线的裁剪1、基本原理

17、判断图形是否在窗口内，对使用较多的矩形窗口来讲其算法简单，只需做四次坐标比较即满足下式，满足条件则选之，否则弃之。13,maxminmaxminyyyxxx式中：（x，y）是被判别的点，（xmin，ymin）及（xmax，ymax） 则是矩形窗口的最小与最大坐标值。 由于曲线可看做是由一组短直线段组成的，因而求直线与矩形窗口边界线交点的算法，是计算图形与矩形窗口交点的基础算法，该算法可用下列公式表示：23)()(yabaxabayyyyxxxx27/60 第三节、图形裁剪其中：0|)()()()(|)()()()(|1|)()()()(|1abmnabmnmamnmamnyabmaabmaxy

18、yyyxxxxDyyyyxxxxDyyyyxxxxD 式中：（x，y）是交点坐标，A（ xa，ya ）、B（ xb，yb ）为某边界线的端点，M（ xm，ym ），N（ xn，yn ）为直线的两端点。 由上述公式可以看出，图形裁剪的原理并不复杂，但图形裁剪的算法却很复杂，裁剪算法软件开发中至关重要的是计算速度。28/60 第三节、图形裁剪 标号法也叫CohenSutherLand法，基本思想：将图形所在的平面分成9个区，给每区一个由四位数组成的编号，每位数表示一个方位。0000代表窗口，如图5所示，1001代表左上方，而0110代表右下方等。 2、线段的裁剪方法（1）.标号法29/60 第三节

19、、图形裁剪第一位1 表示 ，即位于窗口上边框之上maxyy 第二位1 表示 ，即位于窗口上边框之下第三位1 表示 ，即位于窗口上边框之右第四位1 表示 ，即位于窗口上边框之左minyy minxx maxxx 如果4位全是0，即表示位于窗口之内（包括位于窗口之上）。30/60 第三节、图形裁剪如果两端点的区号全由零组成，则该直线位于窗口内取之，如图6中的线段1； 如果两端点的区号的逻辑乘不为零，则该直线位于窗口外的同一侧弃之，如线段4； 若逻辑乘为零，则该直线与窗口边界线有交点，如线段2、3和5，需进行下一步判断。13,maxminmaxminyyyxxx 对线段与窗口关系的判别，首先根据式

20、(3-1) 判别线段两端点所在区并给端点冠以相应区号，然后进行以下的测试：31/60对线5首先据式（3-2）求出与边线的交点M，舍AM段，对BM段再作步中的判断，再到求出与边线的交点N，舍去MN，对BN段再进行步判断，BN为可见线段取之。对线段2、3也要作类似线段5的判断，最后弃之。23)()(yabaxabayyyyxxxx32/60 第三节、图形裁剪(2).中点分割法 中点分割法又称对分法，即将直线对半平分，用中点逼近直线与窗口边界线的交点，进而找到对应直线两端点的最远可见点（位于窗口内的点），两最远可见点之间的部分即是应取线段，其余弃之。33/60 第三节、图形裁剪 计算p1、p2的中点

21、pm。pm为可见点，所以对pmp2再进行对分，计算出的中点为p m。 p m是不可见点，则下次对pm p m进行对分，得到新的中点pm。接下去的对分是在p m pm上进行。如此反复后，当前后两次计算中心出的点pm2 是相对而言于p1的最远可见点。 对p1pm2作同样的的对半查找，直到相对于pm2的最远可见点pm1 。 pm1pm2就是剪裁后窗口内的可见部分。34/60 第三节、图形裁剪 在计算机地图制图中，圆和曲线可看做是用一组短直线逼近形成的曲线，故在裁剪圆及曲线时，可将圆和曲线分解成一组短直线，用线段裁剪的方法进行处理，实现对圆或整条曲线的裁剪。在裁剪前可对那些完全位于矩形内，或全位于矩形

22、外的圆，用外接矩形理论作判断，排除不必作裁剪的图形。3、圆和曲线的裁剪4、多边形的裁剪 地图制图中的多边裁剪是很多的，对于多边形的裁剪，一种方法是将多边形分解成线段逐段裁剪，但效果不理想。事实上，地图中的多边形有时需对其面积进行计算，并且在大多数情况下，多边形内充填有各种符号，这就要求裁剪后的多边形能保持其封闭性，而分解式的裁剪法难以做到这一点。35/60 第三节、图形裁剪 SutherLandHodgman裁剪算法的核心是：先选择窗口的一边界线，对多边形各边进行裁剪，生成新多边形，再用窗口的第二条边界对其裁剪，生成第二个新多边形。依此类推，直至用最后一条窗口边界线裁剪最新生成的多边形，形成最

23、后的多边形即为裁剪结果。 36/60 第四节、曲线的光滑一、概述 地图所描述的诸如道路、水系、境界等地物和用来描述地表起伏的等高线都是曲线，而计算机制图时是先采集实际曲线上一定数量的特征点，再由图形软件根据这些特征点生成相应的曲线，此过程必有一个对曲线平滑处理的过程，这就是曲线的光滑。 曲线光滑也就是曲线拟合或内插，即将曲线看成是由一系列的点列连接而成，只要能根据已知点内插出这些点列的位置，并确保在这些点处具有连续的一阶导数或连续的二阶导数，就可保证得到的曲线是光滑的。 曲线的光滑：通过曲线内插程序计算加密点,连接各相邻点而获得光滑曲线的方法。 37/60 第四节、曲线的光滑 曲线的光滑处理方

24、法有两种类型：一种是光滑后的曲线不一定通过己知点称为曲线拟合曲线拟合；另一种是光滑后的曲线一定通过已知节点称为曲线内插曲线内插，计算机地图制图中大都要求光滑后的曲线通过已知点。 光滑曲线的算法很多，如线性选代法、正轴抛物线加权平均法、B样条法、分段三次多项式插值法、张力样条函数插值法及样条抛物线法等，所用的拟合算法不同，会有不同的光滑结果，地图制图中曲线的形态有多种，要求平滑处理程序中所应包含的拟合算法应是多样的。在此仅对较典型的方法作简述。38/60 第四节、曲线的光滑二、线性迭代法 线性迭代法（抹角法）是一种较简单的曲线光滑方法。该法建立在线性插值的基础上，用反复的线性选代产生加密的折线对

25、曲线进行光滑处理，每迭代一次，抹去一批拐角点，反复迭代以达到曲线光滑的目的，因而拟合的曲线不通过给定的已知点。 如图7所示，每次选代均在上次迭代得到的点列上进行，在所有各相邻点间各内插两个14点，将其两两相连得到新的折线点列（1、2、 3、 4）图a，在新点列上进行第二次抹角如图b，进行多次迭代后就可得到一条光滑的曲线。 39/60 第四节、曲线的光滑 线性迭代的缺点是：迭代结果会造成曲线偏离全部特征点，向内收缩，在曲线挠度大时愈加明显，使曲线定位精度较低。 优点是：图形向内收缩可以确保等高线即使在较密集的情况下也不会相交，且计算量小。当曲线定位精度要求较低时，可采用线性迭代。40/60 第四

26、节、曲线的光滑三、正轴抛物线加权平均法 该法的基本思想是：过特征点列的所有相邻三点分别作一条抛物线（x=ay2+by+c),这样所有相邻两点（除开始和末尾两点）间都有两段抛物线弧，取加权平均结果作为光滑曲线，如图8 该法计算简单。曲线可通过每个特征点，当特征点较密集时，绘出的曲线较为满意。但在特殊情况下正轴抛物线的顶点往往偏离特征点较远，使最后得到的加权平均曲线摆动较大；并因此可能出现曲线交叉的情况。41/60 第四节、曲线的光滑四、张力样条函数插值法 所谓样条是一种可塑的弹性金属条，将它固定在几个节点上可形成一条通过这些节点的光滑曲线，称为样条曲线。 对样条曲线进行数学模拟得出的函数叫做样条

27、函数，广泛应用于曲线拟合、插值等科技计算中。42/60 图形显示的分层处理 在数字测图系统中可将显示的图形分成若干层，可以根据需要生成相关的图形。 实现分层显示的基础是不同类型数据的编码，根据编码在DTM数据库中检索出所有符合特征的数据，构成一个显示层。在屏幕上同时显示多层图形时，只需在区域内重复画出每一层的内容，不同的物体就会按照各自的位置显示。 在计算中机显示三维图形时，用于隐去对观察者不可见的曲线和曲面的技术称为消隐消隐。常用的消隐法有深度缓冲法、扫描法、扫描线算法及深度排序算法等。43/60 图形显示的分层处理 深度缓冲区算法是消隐的最简单的算法。它根据被画的点在垂直于显示屏幕的方向（

28、Z轴方向）上的距离（深度）决定是否画出该点。显示区域的每一个点都有一个其对应的深度缓冲区，用于存放该点的深度值。深度缓冲区的初始值被设成Zmax，即最大的深度值，相当于离观察者最远的距离值。在将图形转换成屏幕上的点时，对每一点都进行以下处理：1、计算被画点的深度值Z。2、如果Z小于深度缓冲区中的当前值，则把深度缓冲区的值改为Z，并画出新点；如果Z大于深度缓冲区中的当前值，说明被画点被遮挡，此时不改变深度缓冲区，即不画出新点。44/60 第五节、等高线的自动生成一、等高线自动生成的基本概念 等高线是地图中最常用的符号之一， 一般说来，等高线生成算法有以下三大类：第一类方法第一类方法 直接根据不规

29、则分布的已知数据点，构成不规则网格（如四边形、三角形或其他多边形网）进行等高线的绘制；第二类方法第二类方法 利用网格数据（即原始数据位于规则的矩形网格交点上）直接勾绘等高线；第三类方法第三类方法 以不规则离散原始数据为依据，用双三次拟合、按距离加权平均或按距离加权最小二乘方法,先拟合一张曲面 Z=f（x，y），再将规则网格点的平面坐标代入曲面方程，解算出网格点高程后，再勾绘等高线。45/60 第五节、等高线的自动生成一般将第一类方法叫不规则网格法，后两种称为规则网格法。无论是采用那种方法，引绘等高线一般都需要做如下的工作：构网（采用第二类方法时不需构网）、等高点位寻找、等高点的追踪、等高线的光

30、滑和等高线的注记。 46/60 第五节、等高线的自动生成二、构网、等高点位的寻找 当使用不规则原始数据，即离散点数据作为依据引绘等高线时，应在制图区域人工构造一个规则网格或不规则网格，以便在单元（网格）的棱边上寻找等高点，进行等高线的引绘。 规则网格是指在制图区域上构成一个矩阵式网格，每个网格角点值（高程值）可采用一定的插值方法求得，而等高线就是利用这些点值引绘的。直接利用离散点连成的四边形、三角形或其他多边形网格称为不规则网格，实用中以三角形网格较为常用。47/60 第五节、等高线的自动生成 构成三角形网的算法有多种，但其基本思想是相同的，即以三角形的某一边作基础边向外扩展，直至全部离散点均

31、连成三角形网为止。设某两点构成了某个三角形的一条边（基础边），其直线方程可由该两端点的坐标建立，则这条直线将把平面所有的离散点分成三个点集，与该三角形另一顶点在同一侧的点集，位于该直线上的点集中的任何一点均不能与该直线两端点形成新的三角形，其余的点均有可能与该直线两端点构成新的三角形。 能与该直线两端点构成新三角形的最合适一点的选择，应满足以下的构网条件：1、所选点与基础边两端点连线的夹角最大；2、过所选点与基础边两端点所构成圆的圆心圆心到两端点连线的距离最小（这里对“距离”规定如下：当圆心与另一角点同侧时取负值，否则取正值）。48/60 第五节、等高线的自动生成 满足上述两条件之一的可选点集

32、中的任一点就是可与基础边构成新的三角形的点。新三角形构成后要进行检验，如果与已有的三角形重复则构成的新三角形无效，反之新三角形为有效三角形。第一个三角形构成的方法是在离散数据信息场中，选择距离最近的两个点，作第一个三角形的基础边，也可用同一地性线任何相邻两点的连线作为第一个三角形的基础边，然后按上述方法选择第三点，进而构成第一个三角形。 三角网的扩展是一个比较复杂的问题，一般的做法是采用两计数器的方法来解决，一个记录已构成的三角形个数，一个记录已扩展的三角形个数。当这两个计数器中数目相等时，表明三角网的构网工作已结束。构网中要确保三角网中没有交叉和重复的三角形，且应当把全部离散点都连接起来。4

33、9/60 第五节、等高线的自动生成 等高点的寻找也就是在已构成的三角网或多边形网格的棱边上确定等高点的通过位置，三角形棱边上是否存在等高点取决于该棱边的两个节点高程值。在完整的等高线图中，一般要包含不同高程值的等高线多条，但是由于各等高线生成的算法完全相同，所以只讨论一个高程值的等高线生成算法即可。 式中： Hi 、 Hj为棱边上两节点的高程值。 设i、j是某三角单元的两个节点，其所构成的棱边i j是否与某高程值为Hc的等高线相交，其判别式为：cjcicjciHHHHfHHHHf或/50/60 第五节、等高线的自动生成当f0时，两者不相交，如图 9（a）所示；f=0时，等高线过i或j中的一个端

34、点，如图9（b）所示；f0时，等高线与该棱边有唯一交点，如图9（c）所示。cjcicjciHHHHfHHHHf或/51/60 第五节、等高线的自动生成 f=0时的情况易引起等高线追踪的困难，会使等高线追踪出现二义性，因而在进行判别时先在该节点的高程值中加入一微小量，在高程为Hc的全部等高线生成后，再恢复节点原来的高程值。这种处理方法实际上是使等高线绕过该节点，但从图形的效果来看因加入量微小，图形显示上依然是通过该点的。 对三角形单元来说，某条等高线至多在三角形单元中通过一次，与单元的一条棱边只存在一个交点，或者说等高线与三角形单元全部棱边的交点数或为零或为两个。四边形单元也是如此，等高线至多在

35、四边形单元中通过一次，等高线与四边形单元全部棱边的交点数或为零或为两个。 结论：三角形和四边形单元，其棱边上的等高点总是成对出现。52/60 第五节、等高线的自动生成 设高程值Hc在单元内及棱边上是线性变化的，则等高点的坐标为：)/()()/()(ijijicicijijicicHHyyHHyyHHxxHHxx式中：（xc，yc）为等高线与棱边 ij的交点坐标即等高点坐标；（xi，yi）、（xj，yj）为棱边两端点 i、j的坐标； Hi和 Hj为其高程值。53/60 第五节、等高线的自动生成三、等高点的追踪 等高点的追踪就是将具有相同高程而又属于同一支等高线的点有序地连接起来。由于在定义域内对

36、给定的高程值可能有若干条等高线存在，关键问题是确定等高线的走向。一般采用逐条生成的办法，这样既可提高等高线的生成速度，又能节约计算机内存。 具体的方法是开辟一个动态数组，记录一条等高线上所有高程点的坐标信息。一条等高线生成完毕后，先将该动态数组清零，之后用来记录下一条等高线的信息。同时采用链表结构记录等高点所在的单元信息，链表的节点的数据域应包括等高点所在的格网单元信息记录和等高点的个数信息记录两个数据项；指针域有一个指针，用来记录下一个存在等高点的单元序号。54/60 第五节、等高线的自动生成 若链表的第一个节点所指示的单元为n，该单元上的第一个等值点为n1(也称线头)，因单元上的等高点总是

37、成对出现，所以在单元n上定能找到另一个等高点n2，将n1、n2的坐标记录到动态数组中。55/60 第五节、等高线的自动生成又因单元n上只有被跟踪过的两个等高点，则链表节点上等高点个数降为零，该节点将从链表中删除，生成下一条同高程的等高线时，不需要重复搜索该单元。如果上述等高点不是定义域边界点（图10中），则应根据单元的序号搜索下一单元（m单元），由于n2(m1)点既是m单元的入口点，可在m单元的棱边上寻找另一等高点m2点，并将m2的坐标数据记录在动态数组中，依次追踪。当找不到新的入口点时，需要将找到的最后一个点（出口点）坐标与已记录的起始点坐标比较，如果坐标是相同的，则曲线闭合，等高线生成结束；否则该等高线在定义区域就是开曲线，该出口点应是边界点，则将已跟踪的等值点坐标倒排序，利用已记录的起始点作为出口点继续搜索，直到发现另一边界点结束跟踪。 56/60 第五节、等高线的自动生成 对追踪到的等高点进行连接时，可按某种规则逐点连接成为一条等高线。当精度要求不高或网格很密时，可用直线段将动态数组中的等高点连