数字化成图技术若干理论基础

数字化成图技术若干理论基础第1页，共65页，2023年，2月20日，星期六§2.1.1测量坐标与屏幕坐标的转换屏幕是进行数字化测图常用的一个图形输出及编辑界面，它与测量坐标的定义方式如下图：测量坐标一般以米为单位，取值与图幅范围有关；屏幕坐标以点阵为单位，取值大小与屏幕分辩率有关。其变换公式如下：第2页，共65页，2023年，2月20日，星期六为尺度比例系数；计算公式为：

在实际开发中，为了保证所选区域能显示在屏幕上且图形不变形，通常取

中较小的显示的共同K值。第3页，共65页，2023年，2月20日，星期六§2.1.2测量坐标与绘图坐标的转换绘图仪是一种常用的图形输出设备，其坐标与和测量坐标系对照如下：绘图坐标单位一般为脉冲当量（或称步长），多数字绘图仪为0.025mm或0.00098英寸。第4页，共65页，2023年，2月20日，星期六由上图可以得出两坐标系的变换公式如下：

其中M为变换的比例系数。由测量坐标系的单位与绘图仪的坐标单位确定。第5页，共65页，2023年，2月20日，星期六§2.1.3通用线性变换坐标数据的变换是空间数据处理的基本内容，它是将地理实体从一个坐标系转换为另一个坐标系，以建立其间的对应关系。第6页，共65页，2023年，2月20日，星期六1平移变换坐标变换矩阵和齐次坐标第7页，共65页，2023年，2月20日，星期六比例变换第8页，共65页，2023年，2月20日，星期六第9页，共65页，2023年，2月20日，星期六第10页，共65页，2023年，2月20日，星期六组合变换多个基本变换组合的复杂变换称组合变换。组合变换实际上是多个基本变换的连乘。矩阵乘不符合交换律，组合变换必需注意变换循序。如下组合变换表示先将图形旋转，再进行平移。第11页，共65页，2023年，2月20日，星期六第12页，共65页，2023年，2月20日，星期六§2.1.4图幅定向在内业数字化成图中，为了便于数字地图的使用，往往在数字地图中储存地物、地貌点的空间坐标系坐标。而我们所采集的点是基于数字化板或数字影像图的坐标，这样就要建立一种数字化坐标与测量坐标对应关系的数学模型式。图幅定向就是通过采集多个（一般为3个以上）共同点，分别获取这些点的数字化坐标和测量坐标，从而建立两坐标系间的变换关系。有时也称这一工作为“图形定向”。图幅定向的作用：1、实现数字化坐标与测量坐标的转换2、消除部分图纸变形误差一般测量中，通常采用双线性方程进行图形定向，在一些软件内为了削弱变换误差的影响，还采用高次方程的进行参数解算。因此有时也称为图幅纠正，也叫几何纠正。第13页，共65页，2023年，2月20日，星期六几何纠正图形编辑可消除数字化产生的错误，但无法纠正图纸变形等误差。几何纠正是实现数字化数据的坐标转换和图纸变形的误差纠正。常用的几何纠正方法有高次变换、二次变换和仿射变换。仿射变换是使用最多的一种几何变换。第14页，共65页，2023年，2月20日，星期六仿射变换方程为：x’=a1x+a2y+a3y’=b1x+b2y+b3a1、

a2、

a3

、b1、

b2、

b3为待定系数理论上只要不在一条直线上的3个控制点坐标值和理论值，即可求得带定系数。实际上用4个以上控制点，通过最小二乘法进行处理，以提高处理精度。误差方程为：Ex=X–(a1x+a2y+a3）Ey=Y–(b1x+b2y+b3)X，Y为已知理论值，求误差最小。第15页，共65页，2023年，2月20日，星期六2.2图形的编辑2.2.1弧段和多边形的外接矩形弧段坐标链中最大最小值XminYminXmaxYmax组成的矩形称该弧段的外接矩形。多边形坐标链中最大最小值XminYminXmaxYmax组成的矩形称该多边形的外接矩形。第16页，共65页，2023年，2月20日，星期六外接矩形的应用引入外接矩形可大大提高弧段求交、多边形求交速度。判断外接矩形相交的逻辑表达式为：(Xmin≤X1min≤Xmax)AND(Ymin≤Y1min≤Ymax)OR(Xmax≥X1max≥Xmax)AND(Ymax≥Y1max≥Ymax)其中,Xmin，Ymin，Xmax，Ymax；X1min，Y1min，X1max，Y1max分别为两个外接矩形。第17页，共65页，2023年，2月20日，星期六2.2.2点、线、面的捕捉和判断1)点的捕捉设图幅上有一点A（x,y）,要捕捉该点可设定一捕捉半径D（通常为几个象素），当你选择点S（x,y）离A点距离小于D，认为，捕捉A点成功。实际中为避免作平方运算，常把捕捉区域设定成矩形。判断捕捉该点的逻辑表达式为：(Xmin≤Sx≤Xmax)AND(Ymin≤Sy≤Ymax)第18页，共65页，2023年，2月20日，星期六2)线的捕捉从理论上说，光标点坐标S（x,y）到弧段的各直线段之间距离d1,d2,,d3…中如有一个距离di满足di<D,认为该弧段被捕捉到。通过外接矩形可大大缩小寻找目标的范围；进一步捕捉第19页，共65页，2023年，2月20日，星期六3)多边形的捕捉多边形的捕捉实际上是求光标点S（x,y）是否在多边形内。通过外接矩形可大大缩小寻找目标的范围；进一步捕捉。第20页，共65页，2023年，2月20日，星期六4）点、弧段、多边形的位置判断点、弧段、多边形的位置判断方法，其基本原理同点、弧段、多边形的捕捉类似，只是在对点、弧段、多边形的判断时，有时要进一步定量化。如求离点D（x,y）最近的一弧段、求穿过多边形的弧段等。第21页，共65页，2023年，2月20日，星期六2.2.3弧段的求交在图形编辑中弧段的求交是一种基本工作，在拓扑关系建立、图形叠置分析、缓冲区建立、图形显示等很多地方均要用到弧段求交算法。假定两条弧段分别有m和n个坐标点，则求两条弧段的交点就要进行（m-1）*(n-1)次直线求交和判断直线是否相交的运算。为提高速度弧段求交初步判断直线求交运算第22页，共65页，2023年，2月20日，星期六2.2.4线和多边形目标的基本操作运算1）直线AB和CD之间求交的计算2）曲线平行线的计算3）曲线光滑的处理4）曲线从简的处理删除多余点5）点在多边形内的判断6）线与多边形交点的计算7）多边形之间交点的计算8）多边形内实现区域填充的算法第23页，共65页，2023年，2月20日，星期六直线与多边形交点的计算:用来判断线与多边形是否分离、包含、相交求线段与多边形的交点

线与多边形相交否两点在多边形内否端点在多边形内又与多边形不相交线在多边形内NY相交不相交端点在多边形外又与多边形不相交线与多边形相离第24页，共65页，2023年，2月20日，星期六多边形之间交点的计算:用来判断两个多边形是分离、包含、相交、相邻分离多边形分离还是包含判断两个多边形的所有线段间是否有相交有相交无相交有公共边界否NY相邻包含相交第25页，共65页，2023年，2月20日，星期六2.2.5图形的裁剪与合并在使用计算机处理图形信息时，计算机内部存储的图形往往比较大，而屏幕显示的只是图的一部分。因此需要确定图形中哪些部分落在显示区之内，哪些落在显示区之外，以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪(如下图所示)图多边形裁剪示意图第26页，共65页，2023年，2月20日，星期六2.2.5.1直线的窗口裁剪

直线的窗口裁剪算法的关键是：1、如何快速判断直线与窗口的关系？2、如何快速求出直线与窗口边的交点？任意平面线段和矩形窗口的位置关系只有如下3种：(1)完全落在窗口内，线段完全可见；(2)完全落在窗口外，线段显然不可见；(3)部分落在窗口内，部分落在窗口外，线段至少有一端点在窗口之外，但非显然不可见。如下图所示：第27页，共65页，2023年，2月20日，星期六直线的窗口裁剪的基本思想是：图线段端点与窗口的位置关系cafdeb窗口第28页，共65页，2023年，2月20日，星期六（1）在判断直线与窗口的关系，若全不在窗口内，是则结束；（2）若全在窗口内，则转向（4）；否则，继续执行（3）；（3）计算该直线段与窗口边的交点，以此将线段分为两部分，丢弃不可见的部分；对剩下的部分转（2）；（4）保留并显示该线段。从如何解决直线段裁剪的关键问题出发，产生了许多裁剪算法，常用的方法有如下几种：直接求交算法、Cohen-Sutherland，中点分割算法。第29页，共65页，2023年，2月20日，星期六一、直接求交算法又称矢量裁剪法直接求交算法的过程见下图，为了快速求出交点，可把直线与窗口边都写成参数形式，求参数值。假设直线端点坐标为P0（X0，Y0）、P1（X1，Y1），矩形窗口的左下角坐标为（XL，YB），右上角坐标为（XR，YT），则直线的参数方程为：第30页，共65页，2023年，2月20日，星期六窗口边的直线参数方程为：通过直线上的(x,y)来计算t，t1,如果均在[0,1]内，则此交点就是窗口的有效点。当然，对于平行于窗口边界的线段，应预先进行判断，特殊处理。第31页，共65页，2023年，2月20日，星期六图直接求交算法流程图第32页，共65页，2023年，2月20日，星期六线段两端点相对于矩形窗口的位置有如下几种情况：(1)两个端点均在窗口外，如下图a线段应予以保留。[>>](2)两个端点均在窗口边界线外同侧，如下图b、c线段全部落在窗口外，是完全不可见的，应予以舍弃。(3)一个端点在窗口内，另一个端点落在窗口外。如下图d线段，是部分可见的，求出交点。得到在窗口内的可见部分。(4)线段的两个端点均不在窗口内，但不处于窗口边界线外同侧，这时有可能是部分可见的(如下图e线段)，也有可能是完全不可见的(如下图f线段)。第33页，共65页，2023年，2月20日，星期六图线段端点与窗口的位置关系cafdeb窗口返回第34页，共65页，2023年，2月20日，星期六二、Cohen—Sutherland裁剪算法

Cohen—Sutherland裁剪算法就是按直线求交算法的思路来对线段进行裁剪的。并且在判断线段的两端点相对于矩形窗口的位置上，巧妙地运用了编码的思想，因此，也称为编码裁剪算法。首先，如下图所示，延长窗口的四条边界线，将平面划分成9个区域，然后，用四位二进制数CtCbCrCl对这9个区域进行编码，编码规则如下：第35页，共65页，2023年，2月20日，星期六100000000100101000100110100100010101cafdeb窗口线段端点的区域编码第36页，共65页，2023年，2月20日，星期六第1位Cl：当线段的端点在窗口的左边界之左时，该位编码为1，否则，该位编码为0。第2位Cr：当线段的端点在窗口的右边界之右时，该位编码为1，否则，该位编码为0。第3位Cb：当线段的端点在窗口的下边界之下时，该位编码为1，否则，该位编码为0。第4位Ct：当线段的端点在窗口的上边界之上时，该位编码为1，否则，该位编码为0。即第37页，共65页，2023年，2月20日，星期六其算法步骤可描述如下：步骤1：根据上述编码规则，对线段的两个端点进行编码，若该线段的一端点位于图6中的某一区域，则将该区域的编码赋予此点，若端点在窗口边界线上，则用窗口内的编码。步骤2：根据线段两端点的编码：判断相对于窗口的位置关系，从而决定对线段如何剪取。（1）先求出P1P2的编码code1，code2，若code1=0，且code2=0，说明线段完全位于窗口内，是完全可见的。于是显示此线段。第38页，共65页，2023年，2月20日，星期六(2)两端点编码逻辑与不为0时，，即code1&code2≠0，则说明两个端点同在窗口的上方、下方、左方或右方，即线段的两个端点位于窗口外同恻，此线段完全位于窗口外，是完全不可见的，于是全部舍弃，不显示此线段。例如，线段（b）的两端点编码为1001和0001，其逐位逻辑与不为0，因此是不可见的。第39页，共65页，2023年，2月20日，星期六(3)两端点编码逐位逻辑与为0时，说明此线段或者部分可见，或者完全不可见。如图6中的线段（e）和线段（f）的端点编码均为0001和0100，但是线段（e）是部分可见的，而线段（f）是完全不可见的，因此，此时需要要计算出该线段与窗口某一边界线或边界线的延长线的交点，在交点处把线段一分为二，对分成的两直线段继续采用编码方法判断，其中必有一段在窗口外，可弃之，再对另一段重复上述处理，直到找到完全在窗口内的那段直线，裁剪结束。第40页，共65页，2023年，2月20日，星期六在直线段与窗口边及延长线求交点时，矩形窗口共有4条边，最多需要求4次交点，求交边的顺序是任意设定的，如：右、上、左、下的顺序。为了加快检测交点的速度，避免无用的求交计算，仅当检测到端点编码的某位不为0时，才有必要把线段与该位所对应的窗口边界进行求交。如图7所示意，线段端点编码为P1：1001、P2：0110，P1、P2编码的逻辑与为0，需要进一步求线段与窗口边及延长线的交点，由P1的编码可知，Cl、Ct为1，故离P1最近的交点只能是上、左边的交点，也就是P3或P4，而不可能是右、下边的交点。第41页，共65页，2023年，2月20日，星期六P1P2P3P4图求交点顺序示意图10010110该算法的特点：（1）用编码方法可快速判断线段完全可见和显然不可见；（2）特别适用二种场合：大窗口场合；窗口特别小的场合(如，光标拾取图形时，光标看作小的裁剪窗口)，缺点：需要计算线段与窗口边界线的交点，这样就不可避免地要进行大量乘除运算，势必降低裁剪效率，不易用硬件实现。第42页，共65页，2023年，2月20日，星期六三、中点分割裁剪算法

思想：开始与Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况：全在、完全不在和线段和窗口有交。对前两种情况，进行与Cohen-Sutherland算法一样的处理。对于第三种情况，用中点分割的方法求出线段与窗口的交点。即从P0点出发找出距P0最近的可见点A和从P1点出发找出距P1最近的可见点B，两个可见点之间的连线即为线段P0P1的可见部分。第43页，共65页，2023年，2月20日，星期六P0ABP1PmA、B分别为距P0、P1最近的可见点，Pm为P0、P1中点图直线中点裁剪算法第44页，共65页，2023年，2月20日，星期六从P0出发找最近可见点采用中点分割方法：先求出P0P1的中点Pm，对于任何线段相对于凸多边形窗口进行裁剪后，落在窗口内的线段不会多于一条，由此可知：若P0Pm不是显然不可见的，并且P0P1在窗口中有可见部分，则距P0最近的可见点一定落在P0Pm上，所以用P0Pm代替P0P1；否则取PmP1代替P0P1。再对新的P0P1求中点Pm。重复上述过程，直到PmP1长度小于给定的控制常数为止，一般取一个象素宽即可，此时Pm收敛于交点。第45页，共65页，2023年，2月20日，星期六依据中点分割的方法，分别对直线段两端点求最近的可见点，即完成了裁剪。算法的核心是求某端点最近的可见点，步骤见下图。然后，依次把直线段的端点P0、P1输入函数，返回距P0、P1的最近可见点A、B，显示即可。第46页，共65页，2023年，2月20日，星期六图从P0点出发找出距P0最近的可见点的流程图第47页，共65页，2023年，2月20日，星期六2多边形的窗口裁剪

多边形的窗口裁剪是以线段裁剪为基础的，但又不同于线段的窗口裁剪。

多边形裁剪的关键在于：（1）如何把多边形落在窗口边界上的交点正确地、按序连接成裁剪后的多边形；（2）窗口边界及拐角点的取舍。其重要算法有：Sutherland-Hodgman算法

Weiler-Athenton算法第48页，共65页，2023年，2月20日，星期六Sutherland-Hodgman算法又称逐边裁剪法。由I.E萨瑟兰德(I.E.Sutherland)和霍德曼(G.W.Hodgman)在1974年提出。基本思想：通过用窗口各边所在的直线逐一对多边形进行裁剪来完成对多边形的裁剪。对于正规矩形窗口，就是依次用窗口的4条边线对多边形进行裁剪，即先用一条边线对整个多边形进行裁剪，得到一个或多个新的多边形，然后再用第二条边线对这些新产生的多边形进行裁剪，继续这一过程．直到多边形依次被窗口的所有边线裁剪完为止（如下图所示）第49页，共65页，2023年，2月20日，星期六地理信息系统基础东华理工学院郭先春第50页，共65页，2023年，2月20日，星期六Weiler-Athenton算法

又称双边裁剪法。此算法是在1977年韦勒(Weiler)和阿瑟顿(Atherton)提出来的。

思想：设用户多边形为主多边形PS，窗口为裁剪多边形PC。同时，设每一多边形按顺时针方向排列，因此，沿多边形的一条边走动，其右边为多边形的内部。

步骤：首先沿PS任一点出发，跟踪检测PS的每一条边，当PS与PC的有效边框相交时：第51页，共65页，2023年，2月20日，星期六（1）若PS的边进入PC，则继续沿PS的边往下处理，同时输出该线段；（2）若PS的边是从PC中出来，则从此点(称为前交点)开始，沿着窗口边框向右检测PC的边，即用PC的有效边框去裁剪PS的边，找到PS与PC最靠近前交点的新交点，同时输出由前交点到此新交点之间窗边上的线段；（3）返回到前交点，再沿PS处理各条边，直到处理完PS的每一条边，回到起点为止。

第52页，共65页，2023年，2月20日，星期六双边裁剪算法的特点：思路清楚，可适用于任何凸的或凹的多边形的裁剪，但这种算法由于需要反复求PS的每一条边与PC的4条边以及PC的每一条有效边与PS的全部边的交点，因而计算工作量很大。三、使用不规则多边形模板的裁剪

其实质是：多边形的叠置操作。四、图形的合并在GIS中经常需要将一幅图内的多层数据合并在一起，或者将相邻的多幅图的同一层数据或多层数合并在一起，此时涉及到空间拓扑关系的重建。第53页，共65页，2023年，2月20日，星期六但对于多边形数据，因为同一个目标在两幅图内已形成独立的多边形，合并时，需要去除掉公共边界。如下图所示：P1P2P(a)(b)实际处理过程是先删除两个多边形，解除空间拓扑关系，然后删除公共边(实际上是图廓边)，然后重建拓扑关系。第54页，共65页，2023年，2月20日，星期六由于空间数据采集的误差和人工操作的误差，两个相邻图幅的空间数据在结合处可能出现逻辑裂隙与几何裂隙。

逻辑裂隙指的是当一个地物在一幅图的数据文件中具有地物编码A，而在另一幅图的数据文件中具有地地物编码B，或者同一物体在这两个数据文件中具有不同的履带性信息，如公路的宽度等。

逻辑裂隙指的是由数据文件边界分开的一个地物的两部分不能精确地衔接。这就涉及到图幅接边问题。图幅接边包括几何与逻辑接边。第55页，共65页，2023年，2月20日，星期六1几何接边：调出需要接边的两幅或多幅图数据，以其中的一个作为活动图幅，其它图幅作为参考，沿图幅的边缘选取一定范围例如5cm的空间目标。以活动图幅为基准，根据图廓边上弧段的结点坐标查找相邻图幅对应弧段，若地物编码相同，结点坐标在一定的容差范围内，则将两边的结点坐标取中数自动吻合，空间关系不变，若地物编码不同，或超过接边的匹配容差，则须人工编辑与接边。第56页，共65页，2023年，2月20日，星期六2逻辑接边：包括两方面的含义：

(1)检查同一目标在相邻图幅的地物编码和属性值是否一致，若不一致，则进行人工编辑修改，这种接边容易处理；

(2)将同一目标在相邻图幅的空间实体数据在逻辑上连接在一起。第57页，共65页，2023年，2月20日，星期六1)图形的合并不同图层之间的合并；同一图层内不同目标合并成一个目标。2)图幅的接边主要对图廓边附近线段，以一幅图为基准进行操作。在图形分界面上不衔接处，给出容差，将自动吻合，必要时用人工结合。第58页，共65页，2023年，2月20日，星期六3.1线状目标基本操作的算法

1、线相交

2、曲线光滑处理

GIS在许多情况下需要将已知的离散采样点值