字符、裁剪算法

2014地理空間圖形學(xué)地理信息工程教研室信息工程大學(xué)地理空間信息學(xué)院學(xué)習(xí)內(nèi)容字符及漢字生成二維圖形裁剪信息工程大學(xué)地理空間信息學(xué)院學(xué)習(xí)要點1、了解字符和漢字編碼；2、理解字符及漢字的生成原理，掌握點陣漢字及矢量漢字的文件結(jié)構(gòu)和顯示過程；3、掌握點、直線段在區(qū)域內(nèi)、外的判別方法；4、掌握直線段裁剪的幾種常用方法；5、了解多邊形的逐邊裁剪法以及其他圖形的裁剪方法。信息工程大學(xué)地理空間信息學(xué)院一、字符及漢字生成信息工程大學(xué)地理空間信息學(xué)院 字符是指數(shù)字、字母、漢字等，用于圖形標(biāo)注、說明等字符及漢字編碼

點陣字符、漢字

矢量字符、漢字

輪廓字型技術(shù)

信息工程大學(xué)地理空間信息學(xué)院ASCII碼：

“美國信息交換用標(biāo)準(zhǔn)代碼集”

1、字符及漢字編碼規(guī)定了128個字符代碼。代碼0—31：控制字符代碼32—127：表示英文字母、標(biāo)點符號、各種運算符以及特殊符號。每個ASCII碼用一個字節(jié)(實際上只要七位二進(jìn)制)代碼表示。

信息工程大學(xué)地理空間信息學(xué)院

GB2312—80：我國最常用的字符集是“信息交換用漢字編碼字符集基本集”。該字符集包含了六千多個常用漢字，以及英文字母、數(shù)字和其它圖形符號。編碼原則：漢字用兩個字節(jié)表示，每個字節(jié)用七位碼（高位為0），前字節(jié)的編碼稱為區(qū)碼，后字節(jié)的編碼稱為位碼，此即區(qū)位碼，如“?！弊衷诙S代碼表中處于17區(qū)第3位，區(qū)位碼即為“1703”。信息工程大學(xué)地理空間信息學(xué)院

國標(biāo)碼：并不等于區(qū)位碼，它是由區(qū)位碼稍作轉(zhuǎn)換得到,其轉(zhuǎn)換方法為：先將十進(jìn)制區(qū)碼和位碼轉(zhuǎn)換為十六進(jìn)制的區(qū)碼和位碼，這樣就得了一個與國標(biāo)碼有一個相對位置差的代碼，再將這個代碼的第一個字節(jié)和第二個字節(jié)分別加上20H，就得到國標(biāo)碼。如：“?！弊值膰鴺?biāo)碼為3123Ｈ，它是經(jīng)過下面的轉(zhuǎn)換得到的：1703D－>1103H->+20H－>3123H。信息工程大學(xué)地理空間信息學(xué)院

國標(biāo)碼問題？：

國標(biāo)碼是漢字信息交換的標(biāo)準(zhǔn)編碼，但因其前后字節(jié)的最高位為0，與ASCII碼發(fā)生沖突？如“?！弊?，國標(biāo)碼為31H和23H，而西文字符“1”和“#”的SCII也為31H和23H，現(xiàn)假如內(nèi)存中有兩個字節(jié)為31H和23H，這到底是一個漢字，還是兩個西文字符“1”;和“#”?于是就出現(xiàn)了二義性。顯然，國標(biāo)碼是不可能在計算機內(nèi)部直接采用。信息工程大學(xué)地理空間信息學(xué)院

機內(nèi)碼：計算機內(nèi)部表示碼，采用變形國標(biāo)碼。變換方法：將國標(biāo)碼的每個字節(jié)都加上128，即將兩個字節(jié)的最高位由0改1，其余7位不變?nèi)纾河缮厦嫖覀冎溃氨！弊值膰鴺?biāo)碼為3123H，前字節(jié)為00110001B，后字節(jié)為00100011B，高位改1為10110001B和10100011B即為B1A3H，因此，“?！弊值臋C內(nèi)碼就是B1A3H。

機內(nèi)碼高位=區(qū)碼+

A0H（10100000D） 機內(nèi)碼低位=位碼+

A0H信息工程大學(xué)地理空間信息學(xué)院

輸入碼:就是使用英文鍵盤輸入漢字時的編碼。目前，我國已推出的輸入碼有數(shù)百種，但用戶使用較多的約為十幾種，按輸入碼編碼的主要依據(jù)，大體可分為順序碼、音碼、形碼、音形碼四類。如“?！弊?，用全拼，輸入碼為碼為“BAO”，用區(qū)位碼，輸入碼為“1703”，用五筆字型則為“WKS”。

信息工程大學(xué)地理空間信息學(xué)院

漢字在計算機中如何表示？

字庫：把所有漢字的字模組織起來，并統(tǒng)一組織存儲在一起形成的文件叫字庫。2、點陣字符、漢字采用圖形（對應(yīng)）的方法，顯示(或繪制)一個漢字就是顯示一個圖形符號，這個圖形符號稱為漢字字模。每個漢字在計算機中都對應(yīng)一個字模，字模分為兩種類型。一是點陣字模，一種是矢量字模。

信息工程大學(xué)地理空間信息學(xué)院FE3F008220FA2F0220A2208220FA2F82202F9220B220FE3F0220FA022000

16×16點陣字形實例(國)，整個漢字占32個字節(jié)，整個字庫的大小為32*6763=210K。點陣漢字是漢字字形最基本的表示法。

點陣漢字原理：信息工程大學(xué)地理空間信息學(xué)院

點陣漢字缺點：數(shù)據(jù)量大，放大后會出現(xiàn)明顯的鋸齒邊，這嚴(yán)重地影響了大字的輸出質(zhì)量信息工程大學(xué)地理空間信息學(xué)院

點陣漢字顯示：例如16*16點陣漢字的每一橫行占2個字節(jié)(2*8位/字節(jié)=16位)。也就是說16*16大方格的橫行的黑白點是由這兩個字節(jié)來決定的。將其數(shù)字轉(zhuǎn)化為二進(jìn)制，0的地方不填充，1的地方填充為黑色信息工程大學(xué)地理空間信息學(xué)院

矢量漢字原理：3、矢量字符、漢字特點：與點陣字相比較，矢量字體的最大優(yōu)點是數(shù)據(jù)壓縮量大；可以任意縮放。

是把漢字所在的方形區(qū)域畫成一個N*N的坐標(biāo)圖，然后把漢字的每一個筆劃分解成線、圓弧，記錄其坐標(biāo)位置，并將其坐標(biāo)位置和圖形都存儲起來，這樣形成的漢字字模稱之為矢量字?！噶繚h字。信息工程大學(xué)地理空間信息學(xué)院(63,63)P4P0P1P2P3P5字符的編碼X0Y00P0X1Y11P1X2Y20P2X3Y31P3X4Y40P4X5Y51P5-1不連線

連線

字符結(jié)束

字符矢量表示，記錄字符的筆畫信息信息工程大學(xué)地理空間信息學(xué)院

矢量漢字顯示步驟：

1、根據(jù)給定的字符編碼，在字庫中檢索出表示該字符的數(shù)據(jù)。

2、取出端點的坐標(biāo)，對其適當(dāng)?shù)膸缀巫冃?，再根?jù)各端點的標(biāo)志顯示字符。信息工程大學(xué)地理空間信息學(xué)院

輪廓字：字符的外輪廓由一系列直線段來描述，矢量字體中保存的是該字符外輪廓一系列直線坐標(biāo)。（一次直線方程）4、輪廓字型技術(shù)信息工程大學(xué)地理空間信息學(xué)院大字仍有“刀割”現(xiàn)象信息工程大學(xué)地理空間信息學(xué)院

曲線字：以高次曲線代替矢量字輪廓的一次直線的方程，即為曲線字。信息工程大學(xué)地理空間信息學(xué)院 曲線字庫在放大后仍能保證光滑。信息工程大學(xué)地理空間信息學(xué)院兩種曲線字：PostScript字體

（Adobe

公司）：

AdobeType1、AdobeType3

三次Bezier曲線來描述的(精度高)TrueType字體

（Apple和Microsoft公司聯(lián)手推出的） 二次B樣條曲線來描述的(內(nèi)置系統(tǒng))信息工程大學(xué)地理空間信息學(xué)院字符的屬性包括字體、字形、大小、字符間距、字符傾斜角、字符串路徑、字符串對齊方式等。信息工程大學(xué)地理空間信息學(xué)院二、二維圖形裁剪信息工程大學(xué)地理空間信息學(xué)院1、線段的裁剪

2、多邊形的裁剪

3、其它圖形的裁剪

編碼裁剪法、矢量裁剪法、中點分割裁剪法

逐邊裁剪法 曲線的裁剪、字符的裁剪信息工程大學(xué)地理空間信息學(xué)院為什么裁剪？

例子：計算機內(nèi)可以存儲全國地圖。如果全部顯示在屏幕上，則看不見局部細(xì)節(jié)。這時，可以使用縮放技術(shù)，把地圖中的局部區(qū)域放大顯示，這時需要確定地圖中那一部分落在顯示區(qū)域之外，那些部分落在顯示區(qū)域之內(nèi)，以便顯示落在顯示區(qū)域之內(nèi)的那部分圖形?！?/p>

裁剪信息工程大學(xué)地理空間信息學(xué)院信息工程大學(xué)地理空間信息學(xué)院裁剪定義

——確定圖形對象的哪些部分在指定區(qū)域內(nèi)部，哪些部分在指定區(qū)域外部的過程。裁剪有關(guān)概念圖形裁剪算法，直接影響圖形系統(tǒng)的效率。信息工程大學(xué)地理空間信息學(xué)院

裁剪實質(zhì)

——

數(shù)據(jù)集合中抽取信息的過程，是許多圖形操作的基礎(chǔ)。

裁剪方法

——判斷圖形元素是否落在裁剪窗口之內(nèi)并找出其位于內(nèi)部的部分。裁剪有關(guān)概念信息工程大學(xué)地理空間信息學(xué)院

裁剪窗口

——多邊形區(qū)域、曲線邊界的區(qū)域、矩形窗口。其中最簡單最常用的裁剪窗口是矩形窗口。裁剪有關(guān)概念由上、下、左、右四條邊界圍成，通常通過其左下角坐標(biāo)（XL，YB）和右上角坐標(biāo)（XR，YT）來定義。(Xr,Yt)(Xl,Yb)信息工程大學(xué)地理空間信息學(xué)院裁剪分類點的裁剪；線段裁剪；圓的裁剪；多邊形的裁剪；字符裁剪等裁剪有關(guān)概念信息工程大學(xué)地理空間信息學(xué)院

點的裁剪是最簡單的一種，是裁剪其他元素的基礎(chǔ)。判斷點的可見性可用下式，若P（x，y）1、點的裁剪P(x,y)XlXrYtYb滿足：Xl<=x<=Xr Yb<=y<=Yt點P為可見（在窗口內(nèi)）否則不可見。

別的圖形裁剪是否可以利用這種方法？信息工程大學(xué)地理空間信息學(xué)院2、線段的裁剪

直線段是組成一切其它圖形的基礎(chǔ)，直線段裁剪算法是復(fù)雜圖形裁剪的基礎(chǔ)。

編碼裁剪法 矢量裁剪法

中點分割裁剪法信息工程大學(xué)地理空間信息學(xué)院下圖表示直線段與窗口的位置關(guān)系

每條線段無非三種可能性：

完全不可見（那些？）完全可見（？）部分可見（？）信息工程大學(xué)地理空間信息學(xué)院

結(jié)論：

1、對于任意一條直線段，它要么被完全排斥在窗口之外（？）；

2、要么在窗口內(nèi)留下一個可見段，并且只能有一個可見段；

可通過對線段端點的簡單判別，判斷線段與窗口的關(guān)系。信息工程大學(xué)地理空間信息學(xué)院直接求交算法：信息工程大學(xué)地理空間信息學(xué)院（1）編碼裁剪法（CoHen和Sutherland）基本思想：

線段P1P2分為三種情況處理:（1）若P1P2完全在窗口內(nèi)，則顯示該線段P1P2。（2）若P1P2明顯在窗口外，則丟棄該線段。（3）若線段不滿足（1）或（2）的條件，則在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復(fù)上述處理。信息工程大學(xué)地理空間信息學(xué)院為快速判斷，采用如下編碼方法:100100010101100000000100101000100110ABCD

將窗口邊線兩邊沿長，得到九個區(qū)域，每一個區(qū)域都用一個四位二進(jìn)制數(shù)標(biāo)識，直線的端點都按其所處區(qū)域賦予相應(yīng)的區(qū)域碼，用來標(biāo)識出端點相對于裁剪矩形邊界的位置。信息工程大學(xué)地理空間信息學(xué)院將區(qū)域碼的各位從右到左編號，則坐標(biāo)區(qū)域與各位的關(guān)系為： 上下右左 XXXX 編碼規(guī)律：任何位賦值為1，代表端點落在相應(yīng)的位置上，否則該位為0。例如：若端點在剪取矩形內(nèi)，區(qū)域碼為0000。若端點落在矩形的左下角，區(qū)域碼為0101。信息工程大學(xué)地理空間信息學(xué)院具體點P(x,y)編碼方法：

信息工程大學(xué)地理空間信息學(xué)院具體判斷方法：給定所有的線段端點的區(qū)域碼，快速判斷哪條直線完全在窗口內(nèi)，哪條直線完全在窗口外。若P1P2完全在窗口內(nèi)code1=0,且code2=0,則“取”；若P1P2明顯在窗口外code1&code2≠0，則“棄”；在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復(fù)上述處理。(處理P1、P2)信息工程大學(xué)地理空間信息學(xué)院具體算法步驟：（設(shè)端點P1,P2的代碼為C1,C2)兩端點P1(X1,Y1)和P2(X2,Y2)在區(qū)域內(nèi)0000,C1=C2=0全保留。當(dāng)兩個端點在窗口邊線外的同側(cè)位置,C1、C2按位與不等零，全舍棄。其它情況，需計算出直線與窗口邊線的交點？，將直線分段后繼續(xù)進(jìn)行檢查判斷。信息工程大學(xué)地理空間信息學(xué)院裁剪例子：信息工程大學(xué)地理空間信息學(xué)院算法總結(jié)：特點：可快速判斷線段的完全可見和不可見。簡單，易于實現(xiàn)。算法中求交點（求法？）是很重要的，他決定了算法的速度。另外，本算法對于其他形狀的窗口未必同樣有效。特別適用二種場合：大窗口場合（大部分線段完全可見）；窗口特別小的場合（大部分線段完全不可見的情況下）——該算法特別有效。

在一般情況下，該算法有時要做不必要的求交運算，因而效率不是太高。信息工程大學(xué)地理空間信息學(xué)院（2）矢量裁剪法（自學(xué)）基本思想：與編碼裁剪算法相類似，只是判別端點是否落在窗口內(nèi)的過程不同。如圖所示，我們同樣用四條窗口邊框直線把平面分割成九個區(qū)域，每一個區(qū)域分別標(biāo)上相應(yīng)的編號。XlXr316027845YtYbAB信息工程大學(xué)地理空間信息學(xué)院（3）中點分割裁剪法基本思想：分別尋找直線段兩個端點各自對應(yīng)最遠(yuǎn)的可見點，這兩個可見點的連線就是原線段的可見部分。P1P2S2S1P2P2P2P1P1P1PmPmebadc信息工程大學(xué)地理空間信息學(xué)院最遠(yuǎn)的可見點只有兩種選擇：P1P2S2S1P2P2P2P1P1P1PmPmebadc要么是直線段一個相應(yīng)端點；要么是在不斷的中點再分過程中產(chǎn)生的某個子段的中點；信息工程大學(xué)地理空間信息學(xué)院具體實現(xiàn)：與編碼裁剪算法一樣首先對線段端點進(jìn)行編碼，并把線段與窗口的關(guān)系分為三種情況，對前兩種情況，進(jìn)行一樣的處理；對于第三種情況，用中點分割的方法求出線段與窗口的交點。P1P2S2S1P2P2P2P1P1P1PmPmebadc信息工程大學(xué)地理空間信息學(xué)院例子：以找出直線段P1P2上離點P1最遠(yuǎn)的可見點

算法步驟：P1P2S2S1P2P2P2P1P1P1PmPmebadc（1）檢驗直線段P1、P2是否完全被排斥在窗口之外。如果是，過程結(jié)束且無輸出線段（如圖線段b）；否則繼續(xù)執(zhí)行下一步。信息工程大學(xué)地理空間信息學(xué)院（2）檢驗點P2是否可見。如果是，則點P2就是離點P1最遠(yuǎn)的可見點，過程結(jié)束（圖線段a）。如果點P2是不可見的（如圖線段c或線段d），那么繼續(xù)執(zhí)行下一步。P1P2S2S1P2P2P2P1P1P1PmPmebadc信息工程大學(xué)地理空間信息學(xué)院（3）分割直線段P1P2于中點Pm。如果線段PmP2被完全排斥在窗口之外，那么原估計不足（如圖線段d），便以P1Pm線段作為新的線段從算法的第一步重新開始執(zhí)行。反之，則以線段PmP2作為新的線段（如圖線段c）從算法的第一步重新開始執(zhí)行。P1P2S2S1P2P2P2P1P1P1PmPmebadc反復(fù)執(zhí)行上述三步，直至找到離點P1最遠(yuǎn)的可見點。信息工程大學(xué)地理空間信息學(xué)院算法特點：

中點分割算法是編碼裁剪算法的硬件版本。中點分割裁剪法只需用到加法和除2運算，而除2在計算機中可以簡單地用右移一位來完成，從而提高了算法的效率，用硬件實現(xiàn)既簡單又有效。信息工程大學(xué)地理空間信息學(xué)院3、多邊形的裁剪

多邊形定義：是由若干直線段圍成的平面封閉圖形。裁剪的結(jié)果，應(yīng)是一個封閉的圖形。平面多邊形和窗口之間存在的三種位置關(guān)系：信息工程大學(xué)地理空間信息學(xué)院基本思路：多邊形裁剪是以線段裁剪為基礎(chǔ)，如果重復(fù)利用直線段的裁剪方法，對多邊形進(jìn)行裁剪，其結(jié)果出現(xiàn)問題？問題1、邊界不再封閉，需要用窗口邊界的恰當(dāng)部分來封閉它，如何確定其邊界？信息工程大學(xué)地理空間信息學(xué)院問題2、凹多邊形可能被裁剪成幾個小的多邊形，如何確定這些小多邊形的邊界？信息工程大學(xué)地理空間信息學(xué)院多邊形裁剪首要解決兩個問題：封閉多邊形經(jīng)裁剪后一般不再是封閉的需要用窗口邊界適當(dāng)部分來封閉；矩形窗口的四個角點在裁剪中是否要與其它交點連線；逐邊裁剪法雙邊裁剪法分區(qū)編碼裁剪法信息工程大學(xué)地理空間信息學(xué)院（1）逐邊裁剪法逐邊裁剪法是薩瑟蘭德和霍德曼在1974年提出。基本思路：依次用窗口的一條邊裁剪多邊形，每次形成一個新的多邊形。最后裁剪出來的多邊形就是所需多邊形。信息工程大學(xué)地理空間信息學(xué)院信息工程大學(xué)地理空間信息學(xué)院 具體步驟：(1)將多邊形表示為頂點表，即｛P1，P2，…

…

Pn-1，Pn

｝,并生成邊表P1P2，P2P3，…

…

Pn-1Pn，PnP1

(2)用窗口邊裁剪原多邊形，生成中間多邊形(3)對中間多邊形重復(fù)步驟(2)，直至被窗口所有邊裁剪完為止信息工程大學(xué)地理空間信息學(xué)院

分割處理：

第一次分解：將多邊形關(guān)于矩形窗口的裁剪分解為它 關(guān)于窗口四邊所在直線的裁剪；

第二次分解：將多邊形關(guān)于一條直線的裁剪分解為多 邊形各邊關(guān)于該直線的裁剪；

流水線過程(左上右下)：前邊的結(jié)果是后邊的輸入。信息工程大學(xué)地理空間信息學(xué)院裁剪后的多邊形的頂點序列如何組成？考慮窗口的一條邊以及延長線構(gòu)成的裁剪線該線把平面分成兩個部分:可見一側(cè)；不可見一側(cè)。根據(jù)多邊形的各條邊與裁剪線位置關(guān)系決定輸出幾個頂點到多邊形的頂點表中。多邊形的各條邊的兩端點S、P。它們與裁剪線的位置關(guān)系只有四種：信息工程大學(xué)地理空間信息學(xué)院情況（1）僅輸出頂點P（S作為前一條終點輸出）；情況（2）輸出0個頂點；情況（3）輸出線段SP與裁剪線的交點I；情況（4）輸出線段SP與裁剪線的交點I和終點P信息工程大學(xué)地理空間信息學(xué)院裁剪多邊形的頂點由兩部分組成： 落在多邊形內(nèi)側(cè)的原多邊形的頂點； 多邊形的邊與裁剪邊的交點；只要將這兩部分頂點順序連接起來，就得到裁剪結(jié)果多邊形。信息工程大學(xué)地理空間信息學(xué)院算法特點：1、改進(jìn)后的算法是通用的裁剪算法，任一多邊形無論是凸多邊形還凹多邊形均可用這一算法進(jìn)行剪取。2、算法簡單，易于程序?qū)崿F(xiàn)，但計算量較大，需要比較大的存貯區(qū)來存放剪取過程中待剪取的多邊形。3、裁剪算法采用流水線方式，適合硬件實現(xiàn)。信息工程大學(xué)地理空間信息學(xué)院4、其它圖形的裁剪（1）曲線的裁剪基本思