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

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

中較小的顯示的共同K值。第三頁(yè)，共六十五頁(yè)，2022年，8月28日§2.1.2測(cè)量坐標(biāo)與繪圖坐標(biāo)的轉(zhuǎn)換繪圖儀是一種常用的圖形輸出設(shè)備，其坐標(biāo)與和測(cè)量坐標(biāo)系對(duì)照如下：繪圖坐標(biāo)單位一般為脈沖當(dāng)量（或稱步長(zhǎng)），多數(shù)字繪圖儀為0.025mm或0.00098英寸。第四頁(yè)，共六十五頁(yè)，2022年，8月28日由上圖可以得出兩坐標(biāo)系的變換公式如下：

其中M為變換的比例系數(shù)。由測(cè)量坐標(biāo)系的單位與繪圖儀的坐標(biāo)單位確定。第五頁(yè)，共六十五頁(yè)，2022年，8月28日§2.1.3通用線性變換

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

a2、

a3

、b1、

b2、

b3為待定系數(shù)理論上只要不在一條直線上的3個(gè)控制點(diǎn)坐標(biāo)值和理論值，即可求得帶定系數(shù)。實(shí)際上用4個(gè)以上控制點(diǎn)，通過最小二乘法進(jìn)行處理，以提高處理精度。誤差方程為：Ex=X–(a1x+a2y+a3）Ey=Y–(b1x+b2y+b3)X，Y為已知理論值，求誤差最小。第十五頁(yè)，共六十五頁(yè)，2022年，8月28日2.2圖形的編輯2.2.1弧段和多邊形的外接矩形弧段坐標(biāo)鏈中最大最小值XminYminXmaxYmax組成的矩形稱該弧段的外接矩形。多邊形坐標(biāo)鏈中最大最小值XminYminXmaxYmax組成的矩形稱該多邊形的外接矩形。第十六頁(yè)，共六十五頁(yè)，2022年，8月28日外接矩形的應(yīng)用引入外接矩形可大大提高弧段求交、多邊形求交速度。判斷外接矩形相交的邏輯表達(dá)式為：(Xmin≤X1min≤Xmax)AND(Ymin≤Y1min≤Ymax)OR(Xmax≥X1max≥Xmax)AND(Ymax≥Y1max≥Ymax)其中,Xmin，Ymin，Xmax，Ymax；X1min，Y1min，X1max，Y1max分別為兩個(gè)外接矩形。第十七頁(yè)，共六十五頁(yè)，2022年，8月28日2.2.2點(diǎn)、線、面的捕捉和判斷1)點(diǎn)的捕捉設(shè)圖幅上有一點(diǎn)A（x,y）,要捕捉該點(diǎn)可設(shè)定一捕捉半徑D（通常為幾個(gè)象素），當(dāng)你選擇點(diǎn)S（x,y）離A點(diǎn)距離小于D，認(rèn)為，捕捉A點(diǎn)成功。實(shí)際中為避免作平方運(yùn)算，常把捕捉區(qū)域設(shè)定成矩形。判斷捕捉該點(diǎn)的邏輯表達(dá)式為：(Xmin≤Sx≤Xmax)AND(Ymin≤Sy≤Ymax)第十八頁(yè)，共六十五頁(yè)，2022年，8月28日2)線的捕捉從理論上說(shuō)，光標(biāo)點(diǎn)坐標(biāo)S（x,y）到弧段的各直線段之間距離d1,d2,,d3…中如有一個(gè)距離di滿足di<D,認(rèn)為該弧段被捕捉到。通過外接矩形可大大縮小尋找目標(biāo)的范圍；進(jìn)一步捕捉第十九頁(yè)，共六十五頁(yè)，2022年，8月28日3)多邊形的捕捉多邊形的捕捉實(shí)際上是求光標(biāo)點(diǎn)S（x,y）是否在多邊形內(nèi)。通過外接矩形可大大縮小尋找目標(biāo)的范圍；進(jìn)一步捕捉。第二十頁(yè)，共六十五頁(yè)，2022年，8月28日4）點(diǎn)、弧段、多邊形的位置判斷點(diǎn)、弧段、多邊形的位置判斷方法，其基本原理同點(diǎn)、弧段、多邊形的捕捉類似，只是在對(duì)點(diǎn)、弧段、多邊形的判斷時(shí)，有時(shí)要進(jìn)一步定量化。如求離點(diǎn)D（x,y）最近的一弧段、求穿過多邊形的弧段等。第二十一頁(yè)，共六十五頁(yè)，2022年，8月28日2.2.3弧段的求交在圖形編輯中弧段的求交是一種基本工作，在拓?fù)潢P(guān)系建立、圖形疊置分析、緩沖區(qū)建立、圖形顯示等很多地方均要用到弧段求交算法。假定兩條弧段分別有m和n個(gè)坐標(biāo)點(diǎn)，則求兩條弧段的交點(diǎn)就要進(jìn)行（m-1）*(n-1)次直線求交和判斷直線是否相交的運(yùn)算。為提高速度弧段求交初步判斷直線求交運(yùn)算第二十二頁(yè)，共六十五頁(yè)，2022年，8月28日2.2.4線和多邊形目標(biāo)的基本操作運(yùn)算1）直線AB和CD之間求交的計(jì)算2）曲線平行線的計(jì)算3）曲線光滑的處理4）曲線從簡(jiǎn)的處理刪除多余點(diǎn)5）點(diǎn)在多邊形內(nèi)的判斷6）線與多邊形交點(diǎn)的計(jì)算7）多邊形之間交點(diǎn)的計(jì)算8）多邊形內(nèi)實(shí)現(xiàn)區(qū)域填充的算法第二十三頁(yè)，共六十五頁(yè)，2022年，8月28日直線與多邊形交點(diǎn)的計(jì)算:用來(lái)判斷線與多邊形是否分離、包含、相交求線段與多邊形的交點(diǎn)

線與多邊形相交否兩點(diǎn)在多邊形內(nèi)否端點(diǎn)在多邊形內(nèi)又與多邊形不相交線在多邊形內(nèi)NY相交不相交端點(diǎn)在多邊形外又與多邊形不相交線與多邊形相離第二十四頁(yè)，共六十五頁(yè)，2022年，8月28日多邊形之間交點(diǎn)的計(jì)算:用來(lái)判斷兩個(gè)多邊形是分離、包含、相交、相鄰分離多邊形分離還是包含判斷兩個(gè)多邊形的所有線段間是否有相交有相交無(wú)相交有公共邊界否NY相鄰包含相交第二十五頁(yè)，共六十五頁(yè)，2022年，8月28日?qǐng)D形的裁剪與合并在使用計(jì)算機(jī)處理圖形信息時(shí)，計(jì)算機(jī)內(nèi)部存儲(chǔ)的圖形往往比較大，而屏幕顯示的只是圖的一部分。因此需要確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之外，以便只顯示落在顯示區(qū)內(nèi)的那部分圖形。這個(gè)選擇過程稱為裁剪(如下圖所示)圖多邊形裁剪示意圖第二十六頁(yè)，共六十五頁(yè)，2022年，8月28日2.2.5.1直線的窗口裁剪

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

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

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

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

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

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

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

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

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

第五十二頁(yè)，共六十五頁(yè)，2022年，8月28日雙邊裁剪算法的特點(diǎn)：思路清楚，可適用于任何凸的或凹的多邊形的裁剪，但這種算法由于需要反復(fù)求PS的每一條邊與PC的4條邊以及PC的每一條有效邊與PS的全部邊的交點(diǎn)，因而計(jì)算工作量很大。三、使用不規(guī)則多邊形模板的裁剪

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

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

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

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

(2)將同一目標(biāo)在相鄰圖幅的空間實(shí)體數(shù)據(jù)在邏輯上連接在一起。第五十七頁(yè)，共六十五頁(yè)，2022年，8月28日1)圖形的合并不同圖層之間的合并；同一圖層內(nèi)不同目標(biāo)合并成一個(gè)目標(biāo)。2)圖幅的接邊主要對(duì)圖廓邊附近線段，以一幅圖為基準(zhǔn)進(jìn)行操作。在圖形分界面上不銜接處，給出容差，將自動(dòng)吻合，必要時(shí)用人工結(jié)合。第五十八頁(yè)，共六十五頁(yè)，2022年，8月28日3.1線狀目標(biāo)基本操作的算法

1、線相交

2、曲線光滑處理

GIS在許多情況下需要將已知的離散采樣點(diǎn)值連