數(shù)字化成圖技術(shù)若干理論基礎(chǔ)

數(shù)字化成圖技術(shù)若干理論基礎(chǔ)第1頁，共65頁，2023年，2月20日，星期六§2.1.1測量坐標與屏幕坐標的轉(zhuǎn)換屏幕是進行數(shù)字化測圖常用的一個圖形輸出及編輯界面，它與測量坐標的定義方式如下圖：測量坐標一般以米為單位，取值與圖幅范圍有關(guān)；屏幕坐標以點陣為單位，取值大小與屏幕分辯率有關(guān)。其變換公式如下：第2頁，共65頁，2023年，2月20日，星期六為尺度比例系數(shù)；計算公式為：

在實際開發(fā)中，為了保證所選區(qū)域能顯示在屏幕上且圖形不變形，通常取

中較小的顯示的共同K值。第3頁，共65頁，2023年，2月20日，星期六§2.1.2測量坐標與繪圖坐標的轉(zhuǎn)換繪圖儀是一種常用的圖形輸出設(shè)備，其坐標與和測量坐標系對照如下：繪圖坐標單位一般為脈沖當量（或稱步長），多數(shù)字繪圖儀為0.025mm或0.00098英寸。第4頁，共65頁，2023年，2月20日，星期六由上圖可以得出兩坐標系的變換公式如下：

其中M為變換的比例系數(shù)。由測量坐標系的單位與繪圖儀的坐標單位確定。第5頁，共65頁，2023年，2月20日，星期六§2.1.3通用線性變換坐標數(shù)據(jù)的變換是空間數(shù)據(jù)處理的基本內(nèi)容，它是將地理實體從一個坐標系轉(zhuǎn)換為另一個坐標系，以建立其間的對應(yīng)關(guān)系。第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日，星期六組合變換多個基本變換組合的復(fù)雜變換稱組合變換。組合變換實際上是多個基本變換的連乘。矩陣乘不符合交換律，組合變換必需注意變換循序。如下組合變換表示先將圖形旋轉(zhuǎn)，再進行平移。第11頁，共65頁，2023年，2月20日，星期六第12頁，共65頁，2023年，2月20日，星期六§2.1.4圖幅定向在內(nèi)業(yè)數(shù)字化成圖中，為了便于數(shù)字地圖的使用，往往在數(shù)字地圖中儲存地物、地貌點的空間坐標系坐標。而我們所采集的點是基于數(shù)字化板或數(shù)字影像圖的坐標，這樣就要建立一種數(shù)字化坐標與測量坐標對應(yīng)關(guān)系的數(shù)學(xué)模型式。圖幅定向就是通過采集多個（一般為3個以上）共同點，分別獲取這些點的數(shù)字化坐標和測量坐標，從而建立兩坐標系間的變換關(guān)系。有時也稱這一工作為“圖形定向”。圖幅定向的作用：1、實現(xiàn)數(shù)字化坐標與測量坐標的轉(zhuǎn)換2、消除部分圖紙變形誤差一般測量中，通常采用雙線性方程進行圖形定向，在一些軟件內(nèi)為了削弱變換誤差的影響，還采用高次方程的進行參數(shù)解算。因此有時也稱為圖幅糾正，也叫幾何糾正。第13頁，共65頁，2023年，2月20日，星期六幾何糾正圖形編輯可消除數(shù)字化產(chǎn)生的錯誤，但無法糾正圖紙變形等誤差。幾何糾正是實現(xiàn)數(shù)字化數(shù)據(jù)的坐標轉(zhuǎn)換和圖紙變形的誤差糾正。常用的幾何糾正方法有高次變換、二次變換和仿射變換。仿射變換是使用最多的一種幾何變換。第14頁，共65頁，2023年，2月20日，星期六仿射變換方程為：x’=a1x+a2y+a3y’=b1x+b2y+b3a1、

a2、

a3

、b1、

b2、

b3為待定系數(shù)理論上只要不在一條直線上的3個控制點坐標值和理論值，即可求得帶定系數(shù)。實際上用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日，星期六外接矩形的應(yīng)用引入外接矩形可大大提高弧段求交、多邊形求交速度。判斷外接矩形相交的邏輯表達式為：(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)點的捕捉設(shè)圖幅上有一點A（x,y）,要捕捉該點可設(shè)定一捕捉半徑D（通常為幾個象素），當你選擇點S（x,y）離A點距離小于D，認為，捕捉A點成功。實際中為避免作平方運算，常把捕捉區(qū)域設(shè)定成矩形。判斷捕捉該點的邏輯表達式為：(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）是否在多邊形內(nèi)。通過外接矩形可大大縮小尋找目標的范圍；進一步捕捉。第20頁，共65頁，2023年，2月20日，星期六4）點、弧段、多邊形的位置判斷點、弧段、多邊形的位置判斷方法，其基本原理同點、弧段、多邊形的捕捉類似，只是在對點、弧段、多邊形的判斷時，有時要進一步定量化。如求離點D（x,y）最近的一弧段、求穿過多邊形的弧段等。第21頁，共65頁，2023年，2月20日，星期六2.2.3弧段的求交在圖形編輯中弧段的求交是一種基本工作，在拓撲關(guān)系建立、圖形疊置分析、緩沖區(qū)建立、圖形顯示等很多地方均要用到弧段求交算法。假定兩條弧段分別有m和n個坐標點，則求兩條弧段的交點就要進行（m-1）*(n-1)次直線求交和判斷直線是否相交的運算。為提高速度弧段求交初步判斷直線求交運算第22頁，共65頁，2023年，2月20日，星期六2.2.4線和多邊形目標的基本操作運算1）直線AB和CD之間求交的計算2）曲線平行線的計算3）曲線光滑的處理4）曲線從簡的處理刪除多余點5）點在多邊形內(nèi)的判斷6）線與多邊形交點的計算7）多邊形之間交點的計算8）多邊形內(nèi)實現(xiàn)區(qū)域填充的算法第23頁，共65頁，2023年，2月20日，星期六直線與多邊形交點的計算:用來判斷線與多邊形是否分離、包含、相交求線段與多邊形的交點

線與多邊形相交否兩點在多邊形內(nèi)否端點在多邊形內(nèi)又與多邊形不相交線在多邊形內(nèi)NY相交不相交端點在多邊形外又與多邊形不相交線與多邊形相離第24頁，共65頁，2023年，2月20日，星期六多邊形之間交點的計算:用來判斷兩個多邊形是分離、包含、相交、相鄰分離多邊形分離還是包含判斷兩個多邊形的所有線段間是否有相交有相交無相交有公共邊界否NY相鄰包含相交第25頁，共65頁，2023年，2月20日，星期六2.2.5圖形的裁剪與合并在使用計算機處理圖形信息時，計算機內(nèi)部存儲的圖形往往比較大，而屏幕顯示的只是圖的一部分。因此需要確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之外，以便只顯示落在顯示區(qū)內(nèi)的那部分圖形。這個選擇過程稱為裁剪(如下圖所示)圖多邊形裁剪示意圖第26頁，共65頁，2023年，2月20日，星期六2.2.5.1直線的窗口裁剪

直線的窗口裁剪算法的關(guān)鍵是：1、如何快速判斷直線與窗口的關(guān)系？2、如何快速求出直線與窗口邊的交點？任意平面線段和矩形窗口的位置關(guān)系只有如下3種：(1)完全落在窗口內(nèi)，線段完全可見；(2)完全落在窗口外，線段顯然不可見；(3)部分落在窗口內(nèi)，部分落在窗口外，線段至少有一端點在窗口之外，但非顯然不可見。如下圖所示：第27頁，共65頁，2023年，2月20日，星期六直線的窗口裁剪的基本思想是：圖線段端點與窗口的位置關(guān)系cafdeb窗口第28頁，共65頁，2023年，2月20日，星期六（1）在判斷直線與窗口的關(guān)系，若全不在窗口內(nèi)，是則結(jié)束；（2）若全在窗口內(nèi)，則轉(zhuǎn)向（4）；否則，繼續(xù)執(zhí)行（3）；（3）計算該直線段與窗口邊的交點，以此將線段分為兩部分，丟棄不可見的部分；對剩下的部分轉(zhuǎn)（2）；（4）保留并顯示該線段。從如何解決直線段裁剪的關(guān)鍵問題出發(fā)，產(chǎn)生了許多裁剪算法，常用的方法有如下幾種：直接求交算法、Cohen-Sutherland，中點分割算法。第29頁，共65頁，2023年，2月20日，星期六一、直接求交算法又稱矢量裁剪法直接求交算法的過程見下圖，為了快速求出交點，可把直線與窗口邊都寫成參數(shù)形式，求參數(shù)值。假設(shè)直線端點坐標為P0（X0，Y0）、P1（X1，Y1），矩形窗口的左下角坐標為（XL，YB），右上角坐標為（XR，YT），則直線的參數(shù)方程為：第30頁，共65頁，2023年，2月20日，星期六窗口邊的直線參數(shù)方程為：通過直線上的(x,y)來計算t，t1,如果均在[0,1]內(nèi)，則此交點就是窗口的有效點。當然，對于平行于窗口邊界的線段，應(yīng)預(yù)先進行判斷，特殊處理。第31頁，共65頁，2023年，2月20日，星期六圖直接求交算法流程圖第32頁，共65頁，2023年，2月20日，星期六線段兩端點相對于矩形窗口的位置有如下幾種情況：(1)兩個端點均在窗口外，如下圖a線段應(yīng)予以保留。[>>](2)兩個端點均在窗口邊界線外同側(cè)，如下圖b、c線段全部落在窗口外，是完全不可見的，應(yīng)予以舍棄。(3)一個端點在窗口內(nèi)，另一個端點落在窗口外。如下圖d線段，是部分可見的，求出交點。得到在窗口內(nèi)的可見部分。(4)線段的兩個端點均不在窗口內(nèi)，但不處于窗口邊界線外同側(cè)，這時有可能是部分可見的(如下圖e線段)，也有可能是完全不可見的(如下圖f線段)。第33頁，共65頁，2023年，2月20日，星期六圖線段端點與窗口的位置關(guān)系cafdeb窗口返回第34頁，共65頁，2023年，2月20日，星期六二、Cohen—Sutherland裁剪算法

Cohen—Sutherland裁剪算法就是按直線求交算法的思路來對線段進行裁剪的。并且在判斷線段的兩端點相對于矩形窗口的位置上，巧妙地運用了編碼的思想，因此，也稱為編碼裁剪算法。首先，如下圖所示，延長窗口的四條邊界線，將平面劃分成9個區(qū)域，然后，用四位二進制數(shù)CtCbCrCl對這9個區(qū)域進行編碼，編碼規(guī)則如下：第35頁，共65頁，2023年，2月20日，星期六100000000100101000100110100100010101cafdeb窗口線段端點的區(qū)域編碼第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：根據(jù)上述編碼規(guī)則，對線段的兩個端點進行編碼，若該線段的一端點位于圖6中的某一區(qū)域，則將該區(qū)域的編碼賦予此點，若端點在窗口邊界線上，則用窗口內(nèi)的編碼。步驟2：根據(jù)線段兩端點的編碼：判斷相對于窗口的位置關(guān)系，從而決定對線段如何剪取。（1）先求出P1P2的編碼code1，code2，若code1=0，且code2=0，說明線段完全位于窗口內(nèi)，是完全可見的。于是顯示此線段。第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）是完全不可見的，因此，此時需要要計算出該線段與窗口某一邊界線或邊界線的延長線的交點，在交點處把線段一分為二，對分成的兩直線段繼續(xù)采用編碼方法判斷，其中必有一段在窗口外，可棄之，再對另一段重復(fù)上述處理，直到找到完全在窗口內(nèi)的那段直線，裁剪結(jié)束。第40頁，共65頁，2023年，2月20日，星期六在直線段與窗口邊及延長線求交點時，矩形窗口共有4條邊，最多需要求4次交點，求交邊的順序是任意設(shè)定的，如：右、上、左、下的順序。為了加快檢測交點的速度，避免無用的求交計算，僅當檢測到端點編碼的某位不為0時，才有必要把線段與該位所對應(yīng)的窗口邊界進行求交。如圖7所示意，線段端點編碼為P1：1001、P2：0110，P1、P2編碼的邏輯與為0，需要進一步求線段與窗口邊及延長線的交點，由P1的編碼可知，Cl、Ct為1，故離P1最近的交點只能是上、左邊的交點，也就是P3或P4，而不可能是右、下邊的交點。第41頁，共65頁，2023年，2月20日，星期六P1P2P3P4圖求交點順序示意圖10010110該算法的特點：（1）用編碼方法可快速判斷線段完全可見和顯然不可見；（2）特別適用二種場合：大窗口場合；窗口特別小的場合(如，光標拾取圖形時，光標看作小的裁剪窗口)，缺點：需要計算線段與窗口邊界線的交點，這樣就不可避免地要進行大量乘除運算，勢必降低裁剪效率，不易用硬件實現(xiàn)。第42頁，共65頁，2023年，2月20日，星期六三、中點分割裁剪算法

思想：開始與Cohen-Sutherland算法一樣首先對線段端點進行編碼，并把線段與窗口的關(guān)系分為三種情況：全在、完全不在和線段和窗口有交。對前兩種情況，進行與Cohen-Sutherland算法一樣的處理。對于第三種情況，用中點分割的方法求出線段與窗口的交點。即從P0點出發(fā)找出距P0最近的可見點A和從P1點出發(fā)找出距P1最近的可見點B，兩個可見點之間的連線即為線段P0P1的可見部分。第43頁，共65頁，2023年，2月20日，星期六P0ABP1PmA、B分別為距P0、P1最近的可見點，Pm為P0、P1中點圖直線中點裁剪算法第44頁，共65頁，2023年，2月20日，星期六從P0出發(fā)找最近可見點采用中點分割方法：先求出P0P1的中點Pm，對于任何線段相對于凸多邊形窗口進行裁剪后，落在窗口內(nèi)的線段不會多于一條，由此可知：若P0Pm不是顯然不可見的，并且P0P1在窗口中有可見部分，則距P0最近的可見點一定落在P0Pm上，所以用P0Pm代替P0P1；否則取PmP1代替P0P1。再對新的P0P1求中點Pm。重復(fù)上述過程，直到PmP1長度小于給定的控制常數(shù)為止，一般取一個象素寬即可，此時Pm收斂于交點。第45頁，共65頁，2023年，2月20日，星期六依據(jù)中點分割的方法，分別對直線段兩端點求最近的可見點，即完成了裁剪。算法的核心是求某端點最近的可見點，步驟見下圖。然后，依次把直線段的端點P0、P1輸入函數(shù)，返回距P0、P1的最近可見點A、B，顯示即可。第46頁，共65頁，2023年，2月20日，星期六圖從P0點出發(fā)找出距P0最近的可見點的流程圖第47頁，共65頁，2023年，2月20日，星期六2多邊形的窗口裁剪

多邊形的窗口裁剪是以線段裁剪為基礎(chǔ)的，但又不同于線段的窗口裁剪。

多邊形裁剪的關(guān)鍵在于：（1）如何把多邊形落在窗口邊界上的交點正確地、按序連接成裁剪后的多邊形；（2）窗口邊界及拐角點的取舍。其重要算法有：Sutherland-Hodgman算法

Weiler-Athenton算法第48頁，共65頁，2023年，2月20日，星期六Sutherland-Hodgman算法又稱逐邊裁剪法。由I.E薩瑟蘭德(I.E.Sutherland)和霍德曼(G.W.Hodgman)在1974年提出?；舅枷耄和ㄟ^用窗口各邊所在的直線逐一對多邊形進行裁剪來完成對多邊形的裁剪。對于正規(guī)矩形窗口，就是依次用窗口的4條邊線對多邊形進行裁剪，即先用一條邊線對整個多邊形進行裁剪，得到一個或多個新的多邊形，然后再用第二條邊線對這些新產(chǎn)生的多邊形進行裁剪，繼續(xù)這一過程．直到多邊形依次被窗口的所有邊線裁剪完為止（如下圖所示）第49頁，共65頁，2023年，2月20日，星期六地理信息系統(tǒng)基礎(chǔ)東華理工學(xué)院郭先春第50頁，共65頁，2023年，2月20日，星期六Weiler-Athenton算法

又稱雙邊裁剪法。此算法是在1977年韋勒(Weiler)和阿瑟頓(Atherton)提出來的。

思想：設(shè)用戶多邊形為主多邊形PS，窗口為裁剪多邊形PC。同時，設(shè)每一多邊形按順時針方向排列，因此，沿多邊形的一條邊走動，其右邊為多邊形的內(nèi)部。

步驟：首先沿PS任一點出發(fā)，跟蹤檢測PS的每一條邊，當PS與PC的有效邊框相交時：第51頁，共65頁，2023年，2月20日，星期六（1）若PS的邊進入PC，則繼續(xù)沿PS的邊往下處理，同時輸出該線段；（2）若PS的邊是從PC中出來，則從此點(稱為前交點)開始，沿著窗口邊框向右檢測PC的邊，即用PC的有效邊框去裁剪PS的邊，找到PS與PC最靠近前交點的新交點，同時輸出由前交點到此新交點之間窗邊上的線段；（3）返回到前交點，再沿PS處理各條邊，直到處理完P(guān)S的每一條邊，回到起點為止。

第52頁，共65頁，2023年，2月20日，星期六雙邊裁剪算法的特點：思路清楚，可適用于任何凸的或凹的多邊形的裁剪，但這種算法由于需要反復(fù)求PS的每一條邊與PC的4條邊以及PC的每一條有效邊與PS的全部邊的交點，因而計算工作量很大。三、使用不規(guī)則多邊形模板的裁剪

其實質(zhì)是：多邊形的疊置操作。四、圖形的合并在GIS中經(jīng)常需要將一幅圖內(nèi)的多層數(shù)據(jù)合并在一起，或者將相鄰的多幅圖的同一層數(shù)據(jù)或多層數(shù)合并在一起，此時涉及到空間拓撲關(guān)系的重建。第53頁，共65頁，2023年，2月20日，星期六但對于多邊形數(shù)據(jù)，因為同一個目標在兩幅圖內(nèi)已形成獨立的多邊形，合并時，需要去除掉公共邊界。如下圖所示：P1P2P(a)(b)實際處理過程是先刪除兩個多邊形，解除空間拓撲關(guān)系，然后刪除公共邊(實際上是圖廓邊)，然后重建拓撲關(guān)系。第54頁，共65頁，2023年，2月20日，星期六由于空間數(shù)據(jù)采集的誤差和人工操作的誤差，兩個相鄰圖幅的空間數(shù)據(jù)在結(jié)合處可能出現(xiàn)邏輯裂隙與幾何裂隙。

邏輯裂隙指的是當一個地物在一幅圖的數(shù)據(jù)文件中具有地物編碼A，而在另一幅圖的數(shù)據(jù)文件中具有地地物編碼B，或者同一物體在這兩個數(shù)據(jù)文件中具有不同的履帶性信息，如公路的寬度等。

邏輯裂隙指的是由數(shù)據(jù)文件邊界分開的一個地物的兩部分不能精確地銜接。這就涉及到圖幅接邊問題。圖幅接邊包括幾何與邏輯接邊。第55頁，共65頁，2023年，2月20日，星期六1幾何接邊：調(diào)出需要接邊的兩幅或多幅圖數(shù)據(jù)，以其中的一個作為活動圖幅，其它圖幅作為參考，沿圖幅的邊緣選取一定范圍例如5cm的空間目標。以活動圖幅為基準，根據(jù)圖廓邊上弧段的結(jié)點坐標查找相鄰圖幅對應(yīng)弧段，若地物編碼相同，結(jié)點坐標在一定的容差范圍內(nèi)，則將兩邊的結(jié)點坐標取中數(shù)自動吻合，空間關(guān)系不變，若地物編碼不同，或超過接邊的匹配容差，則須人工編輯與接邊。第56頁，共65頁，2023年，2月20日，星期六2邏輯接邊：包括兩方面的含義：

(1)檢查同一目標在相鄰圖幅的地物編碼和屬性值是否一致，若不一致，則進行人工編輯修改，這種接邊容易處理；

(2)將同一目標在相鄰圖幅的空間實體數(shù)據(jù)在邏輯上連接在一起。第57頁，共65頁，2023年，2月20日，星期六1)圖形的合并不同圖層之間的合并；同一圖層內(nèi)不同目標合并成一個目標。2)圖幅的接邊主要對圖廓邊附近線段，以一幅圖為基準進行操作。在圖形分界面上不銜接處，給出容差，將自動吻合，必要時用人工結(jié)合。第58頁，共65頁，2023年，2月20日，星期六3.1線狀目標基本操作的算法

1、線相交

2、曲線光滑處理

GIS在許多情況下需要將已知的離散采樣點值