一種動態(tài)繪制無交叉法線坡面線的新算法

方 雷，劉仁義，呂 干，杜震洪，姚申君

1.浙江大學(xué)浙江省資源與環(huán)境重點(diǎn)實(shí)驗(yàn)室，浙江杭州310028；2.浙江大學(xué)地理信息科學(xué)研究所，浙江杭州310027；3.香港大學(xué)地理系，香港999077

一種動態(tài)繪制無交叉法線坡面線的新算法

方 雷1，2，劉仁義2，呂 干1，2，杜震洪1，2，姚申君3

1.浙江大學(xué)浙江省資源與環(huán)境重點(diǎn)實(shí)驗(yàn)室，浙江杭州310028；2.浙江大學(xué)地理信息科學(xué)研究所，浙江杭州310027；3.香港大學(xué)地理系，香港999077

研究一種動態(tài)繪制任何形狀的無交叉法線坡面線的新算法，用以克服傳統(tǒng)手工繪制復(fù)雜坡面線及原有自動化技術(shù)的不足。并證明基于“實(shí)交點(diǎn)定理”及其“補(bǔ)充定理”的算法是生成無交叉坡面線的充分條件。進(jìn)一步說明使用該算法可以動態(tài)繪制地形圖所需要的任何形狀的法線自然（加固）斜坡、崩崖、陡崖、陡石山、堤岸等圖式符號。最后，通過三組試驗(yàn)驗(yàn)證算法的有效性，分析算法的特點(diǎn)及影響因素。

斜坡；填充圖案；制圖；地理信息系統(tǒng)

1 引 言

《地形圖圖式》［1］（GB／T 7929—1995）規(guī)定：斜坡指各種天然形成和人工修筑的坡度在70°以下的坡面地段。其樣式如圖1所示，符號的上沿實(shí)線表示斜坡的上棱線，長短線表示坡面。符號的長線一般繪至坡腳，當(dāng)坡面較寬且有明顯坡腳線時，可測繪坡腳線，以范圍線（點(diǎn)線）表示。計算機(jī)自動制圖軟件中斜坡符號的一般畫法：確定上棱線和坡腳線后繪制一組自上棱線開始指向坡腳線的長短相間的坡面線。坡面長短線有兩種畫法：等分法和法線法（圖1（a）和圖1（b））。其中法線法是將上棱線按固定長度等分，由各等分點(diǎn)出發(fā)分別向坡腳線做一組法線段（與上棱線垂直）生成坡面線的方法。通過該方法得到的坡面長短線稱為法線坡面長短線或法線坡面線，得到的斜坡稱為法線（加固）斜坡。由于上棱線段間的夾角、坡面線的間隔和長度三個因素的影響，法線法的坡面長線在填充坡面過程中會出現(xiàn)彼此交叉現(xiàn)象，使得法線法生成的坡面線非常雜亂（圖1（c）），因此使用法線法生成美觀的無交叉坡面長線算法是本文的主要研究內(nèi)容（圖1（d））。

圖1 自然斜坡線Fig.1 Natural slope lines

若將上棱線、坡腳線及其兩端邊緣的兩條坡面線看成是一個封閉的簡單多邊形，那么坡面線的生成則轉(zhuǎn)化成一個多邊形的填充圖案或者填充符號生成問題。平行線或交叉線等規(guī)則填充圖案的生成算法較成熟，多數(shù)流行的GIS軟件可以符號化“等長”的坡面長短線（即便存在交叉情況）。但是，法線坡面線具有特殊性：① 斜坡上棱線的重要性遠(yuǎn)遠(yuǎn)大于坡腳線；② 坡面線均從上棱線出發(fā)繪至坡腳線，具有指向性；③ 坡面線根據(jù)上棱線與坡腳線的相對位置、長度和角度動態(tài)生成，無法提前定制；④ 坡面線在上棱線附近均為等間距的法線段，若不進(jìn)行截取操作會在坡腳線附近大量交叉，破壞填充圖案的美觀性。而計算機(jī)圖形學(xué)專家往往將多邊形區(qū)域填充的研究重點(diǎn)集中在實(shí)現(xiàn)規(guī)則圖案的填充算法上［2－3］；制圖學(xué)專家的研究則將研究重點(diǎn)集中在GIS空間數(shù)據(jù)與地形圖圖式一體化的模型研究上［4－5］，符號或符號庫的合理設(shè)計和建立［6］，符號化效率［7－8］，隨時間變化的動態(tài)符號生成［9］，顏色、線條等組合方法對符號進(jìn)行表達(dá)［10］等方面；文獻(xiàn)［11］甚至提出三維陡崖的自動建模方法。而少有學(xué)者系統(tǒng)地研究類似坡面線這類具有上述四個特點(diǎn)的圖式符號動態(tài)生成方法。一些測繪制圖軟件（如南方CASS6.1）或使用人機(jī)交互方式，或使用自動方式從技術(shù)上解決部分法線斜坡坡面線的交叉問題，但也僅限于形狀較規(guī)則的法線斜坡，對于是否適用于所有形狀坡面線的填充并未證明。本文在文獻(xiàn)［12］的基礎(chǔ)上提出一種基于實(shí)交點(diǎn)定理及其補(bǔ)充定理的動態(tài)繪制任何形狀斜坡的無交叉坡面線算法較好地解決這一問題。

2 算法介紹

形成無交叉坡面線的基本方法是裁剪法線段交叉部分，其關(guān)鍵是求出恰當(dāng)?shù)慕稽c(diǎn)并裁剪掉交點(diǎn)至坡腳線的多余法線段。在同一平面內(nèi)，n（n為正整數(shù)）條直線最多可能有個交點(diǎn)，該情況下選擇出恰當(dāng)?shù)慕稽c(diǎn)非常困難。為此提出基于實(shí)交點(diǎn)定理及其補(bǔ)充定理算法（algorithm based on real intersection and complementary theorem，ABRICT）。本節(jié)首先明確算法的四個前提假設(shè)及相關(guān)概念，在分析CASS算法缺陷的基礎(chǔ)上提出實(shí)交點(diǎn)定理及補(bǔ)充定理，最后描述完整的ABRICT算法的實(shí)現(xiàn)步驟。

2.1 前提假設(shè)

研究對象為《地形圖圖式》［1］中斜坡圖式，算法和證明過程基于以下四條前提假設(shè)：① 由斜坡上棱線、坡腳線及坡面邊緣線組成的多邊形是非自相交多邊形；②坡面線不通過上棱線的節(jié)點(diǎn)，若坡面線自動生成過程中剛好通過上棱線節(jié)點(diǎn)，則可將其向節(jié)點(diǎn)一側(cè)進(jìn)行微小平移等價替換；③ 坡面線均與坡腳線同側(cè)；④ 斜坡上棱線單側(cè)生成坡面線，若出現(xiàn)兩條坡腳線在一條上棱線兩側(cè)的情況，則可用兩條上棱線和兩條坡腳線等價替換。

2.2 算法相關(guān)定義描述

整體整潔、無交叉、疏密程度均衡的坡面線稱為無交叉坡面線。即由上棱線和兩條坡面線組成的封閉多邊形內(nèi)部不包含這樣的線段，穿越封閉多邊形到達(dá)坡腳或者在多邊形外部與其他坡面線相交。如圖2中法線段3、5和上棱線構(gòu)成的封閉多邊形不滿足上述定義。

圖2 算法相關(guān)定義說明圖Fig.2 Illustrations of terms in relation with the algorithm

生成無交叉坡面線算法的關(guān)鍵是求出恰當(dāng)?shù)慕稽c(diǎn)并裁剪掉交點(diǎn)至坡腳線的多余法線段。然而，并不是所有的交點(diǎn)都要作裁剪多余線段的處理（如圖2中D點(diǎn)，法線段5在D點(diǎn)之前已與法線段4有交點(diǎn)A，所以D點(diǎn)實(shí)際上落在法線段5的多余線段上，該點(diǎn)無須做裁剪多余線段處理）。此類落在法線段的多余線段上，且又不做裁剪多余線段處理的交點(diǎn)為虛交點(diǎn)；需要做裁剪多余線段處理的交點(diǎn)稱為實(shí)交點(diǎn)。若兩條相交法線在相交之前均不與其他法線段相交，則稱其交點(diǎn)為初始實(shí)交點(diǎn)（如圖2中A點(diǎn)）。如果兩條相交法線在相交之前已與其他法線段的多余線段相交，則稱其交點(diǎn)為事實(shí)實(shí)交點(diǎn)（如圖2中C點(diǎn)）。此外，稱依次交于實(shí)交點(diǎn)的法線段為對稱法線段，并稱經(jīng)過交叉部分裁剪處理的坡面線與上棱線組成的封閉多邊形為法線多邊形。

2.3 實(shí)交點(diǎn)定理及其缺陷

2.3.1 CASS算法及其缺陷

實(shí)交點(diǎn)的定義提供了尋找實(shí)交點(diǎn)的方法。由于確定初始實(shí)交點(diǎn)的位置更為重要，尋找第一對相交法線段便成為解決問題的關(guān)鍵。CASS算法是諸多尋找實(shí)交點(diǎn)的算法中應(yīng)用最廣的一個。它可描述為：自左向右（或自右向左）遍歷法線段，將第一對相交法線段的交點(diǎn)作為初始實(shí)交點(diǎn)，并進(jìn)行裁剪處理；然后將處理后的法線段內(nèi)側(cè)的相鄰法線段的交點(diǎn)作為事實(shí)實(shí)交點(diǎn)，再進(jìn)行裁剪處理，直到不再存在相交法線段為止。使用CASS算法生成的無交叉法線自然斜坡圖式如圖3所示。但是，該算法并不能對所有形狀的斜坡完成坡面區(qū)域的“美觀填充”。法線坡面線的美觀之處在于其沿上棱線夾角角平分線呈現(xiàn)一種對稱性。圖3（a）中斜坡圖式AB、BC段坡面線存在明顯的對稱性，而CD段坡面線存在一塊只有坡面短線而沒有坡面長線的空白區(qū)且不與BC段對稱，說明該區(qū)域的坡面長線因?yàn)檎也坏脚c其相交的坡面長線而被刪除，即CASS算法沒有完成所有坡面區(qū)域的填充。又如圖3（b），其上棱線BC段與CD段夾角值較小，且BC段長度較小，生成的坡面線出現(xiàn)大量交叉情況。故上棱線段間的夾角、坡面線的間隔和長度是坡面線產(chǎn)生交叉的三個影響因素。

圖3 南方CASS6.1軟件生成的法線自然斜坡Fig.3 Normal－based natural slope created by South CASS6.1software

而CASS算法的貢獻(xiàn)在于為斜坡圖式提供一種繪制思路：如果找到最外圍的一個交點(diǎn)（即初始實(shí)交點(diǎn)），并以該點(diǎn)對線段進(jìn)行裁剪操作，則該線段就不會再與更小范圍中的其他法線段產(chǎn)生交點(diǎn)。即只處理“相交”的坡面線，忽略上棱線角度和坡面線間隔的判斷。然而，“初始實(shí)交點(diǎn)存在第一對相交法線段上”并不是一個好的科學(xué)表述，要在眾多法線段中得到“第一對”相交法線段，需要進(jìn)行大量空間運(yùn)算和驗(yàn)證，導(dǎo)致自動化算法復(fù)雜，可操作性降低。而筆者發(fā)現(xiàn)初始實(shí)交點(diǎn)的位置呈現(xiàn)一定的規(guī)律性，只存在于相鄰的兩條法線上。所以，因循CASS算法的思路，基于“相鄰”這一空間位置概念提出一種實(shí)交點(diǎn)存在性的科學(xué)表述——實(shí)交點(diǎn)定理。

2.3.2 實(shí)交點(diǎn)定理

實(shí)交點(diǎn)定理：初始實(shí)交點(diǎn)只存在于相鄰的兩條法線段上，而事實(shí)實(shí)交點(diǎn)則存在于初始實(shí)交點(diǎn)兩側(cè)的對稱法線段上。

由定理可知，所有實(shí)交點(diǎn)必然是未經(jīng)過裁剪操作的相鄰法線段的交點(diǎn)。該定理優(yōu)于CASS算法之處在于：① “相鄰”這一空間位置概念的表述比“第一對相交法線段”更容易判斷也更具一般性；② 實(shí)交點(diǎn)定理的初始實(shí)交點(diǎn)位置在上棱線的節(jié)點(diǎn)附近，而CASS算法的初始實(shí)交點(diǎn)位置則在坡面線附近，所以，根據(jù)實(shí)交點(diǎn)定理繪制的法線斜坡不會出現(xiàn)如圖3（a）的空白區(qū)域；③表述簡潔并足以描述一般形狀的無交叉斜坡圖式實(shí)交點(diǎn)的位置特征；④ 以該定理為核心的算法易于理解，操作簡單，在一個由法線段組成的有序序列中（如從左到右），容易得到未經(jīng)裁剪操作的相鄰法線段。然而，基于實(shí)交點(diǎn)定理的算法與CASS算法都存在一個共同的缺陷就是不能處理特殊情況下（圖3（b））的法線交叉問題。這是因?yàn)樵撍惴ㄖ皇墙鉀Q在法線多邊形內(nèi)部不會出現(xiàn)交叉的問題，無法處理法線多邊形外部的法線段與該多邊形相交的特殊情況。所以，本文進(jìn)一步提出實(shí)交點(diǎn)補(bǔ)充定理。

2.4 基于實(shí)交點(diǎn)定理及補(bǔ)充定理的算法描述

補(bǔ)充定理：若某連接上棱線與坡腳線的法線段與已經(jīng)找到實(shí)交點(diǎn)的法線段相交于一點(diǎn)，則該交點(diǎn)是該法線段的事實(shí)實(shí)交點(diǎn)。

根據(jù)實(shí)交點(diǎn)定理及補(bǔ)充定理提出一種遍歷及裁剪處理所有法線段生成無交叉法線坡面線的算法，稱為基于實(shí)交點(diǎn)定理及其補(bǔ)充定理算法（ABRICT）。算法流程如圖4所示。

3 理論證明

由2.3.1節(jié)可知，法線坡面線相交情況的產(chǎn)生源于三個要素，故可從三者的關(guān)系來論證某一繪制算法的通用性。而本節(jié)將從另一思路出發(fā)，采用反證法簡單證明實(shí)交點(diǎn)定理只是尋找實(shí)交點(diǎn)生成無交叉法線坡面線的必要非充分條件，從而解釋了基于實(shí)交點(diǎn)定理的算法或者與之類似的算法（如CASS算法）不適用于繪制所有形狀的法線斜坡坡面線的原因。并進(jìn)一步證明了ABRICT算法的充分性（通用性）。

圖4 算法流程圖（二維框圖對應(yīng)實(shí)交點(diǎn)定理部分，三維框圖對應(yīng)補(bǔ)充定理的增加部分）Fig.4 Flow chart of the algorithm（2Dframes illustrating the real－intersection theorem and 3Dframes illustrating the complementary theorem）

3.1 基于實(shí)交點(diǎn)定理算法生成無交叉坡面線的必要性證明

假設(shè)不使用基于實(shí)交點(diǎn)定理的算法也可以找到實(shí)交點(diǎn)并生成無交叉坡面線。即非對稱法線段的交點(diǎn)也可能是實(shí)交點(diǎn)。

那么，若坡面線出現(xiàn)交叉的情況，則必然存在一個由上棱線和兩條非對稱的經(jīng)過交叉部分裁剪處理的法線段組成的法線多邊形，該多邊形中至少含有一條不與其他法線段相交的法線段，從上棱線出發(fā)到達(dá)坡腳線，或者在到達(dá)坡腳線之前與該多邊形外部的法線段相交（如圖5的三種情況）。

圖5 法線段（虛線）與法線多邊形（點(diǎn)劃線）關(guān)系示意圖Fig.5 Illustrations of relationship between normalbased lines（dashed）and polygons（dash dotted）

已知法線多邊形是封閉多邊形，并且坡腳線在法線多邊形外。再由2.1節(jié)前提假設(shè)②可知該坡面線不通過上棱線的節(jié)點(diǎn)。易知，經(jīng)過封閉多邊形邊上任意一個異于頂點(diǎn)的點(diǎn)以及多邊形外一點(diǎn)的直線，與該多邊形的邊至少有兩個交點(diǎn)（該定理可以使用直線這一點(diǎn)集的緊致性和區(qū)域的連通性加以證明）。又由前提假設(shè)③知坡面線均與坡腳線同側(cè)。故上述法線段必然與上述多邊形相交。若該法線段相交于法線多邊形的實(shí)交點(diǎn)，則與“非對稱的法線段相交于實(shí)交點(diǎn)”的假設(shè)矛盾；若該法線段不相交于法線多邊形的實(shí)交點(diǎn)，則與坡面線或者上棱線相交，此時的坡面線不再是無交叉坡面線，與“生成無交叉坡面線”的假設(shè)矛盾。故假設(shè)錯誤，必要性得證。即只有使用實(shí)交點(diǎn)定理的方法在相鄰法線段上找到實(shí)交點(diǎn)，再對交叉部分進(jìn)行裁剪處理才能得到無交叉坡面線。

3.2 基于實(shí)交點(diǎn)定理及其補(bǔ)充定理算法生成無交叉坡面線的充分性證明

假設(shè)使用實(shí)交點(diǎn)定理及其補(bǔ)充定理的算法不能得到無交叉坡面線。下面分“法線段與法線多邊形關(guān)系”和“兩法線多邊形關(guān)系”兩種情況討論。

（1）任取一個法線多邊形，它與到達(dá)坡腳線的法線段的關(guān)系分以下兩種情況：① 法線段與法線多邊形相交，由于經(jīng)過實(shí)交點(diǎn)定理的方法處理后法線多邊形內(nèi)部不包含到達(dá)坡腳線的法線段，那么此法線段必從法線多邊形的外部與多邊形相交，這與補(bǔ)充定理矛盾，所以假設(shè)錯誤；② 法線段不與法線多邊形相交，則生成的坡面線就是無交叉坡面線，假設(shè)錯誤。

（2）任取兩個法線多邊形，它們的空間關(guān)系分為以下三種情況：① 法線多邊形重合，那么它與其他法線段的平面關(guān)系則轉(zhuǎn)化成上述法線段與法線多邊形關(guān)系的情況，它與其他法線多邊形的平面關(guān)系則轉(zhuǎn)化成分離或相交兩種情況；② 兩法線多邊形分離，則生成的坡面線就是無交叉坡面線，假設(shè)錯誤；③ 兩法線多邊形相交，又分為兩種情況。第一種情況，交點(diǎn)是法線多邊形的一個頂點(diǎn)，若不再有其他交點(diǎn)，則兩多邊形不交叉，生成的坡面線是無交叉坡面線，故假設(shè)錯誤；第二種情況，交點(diǎn)是法線多邊形一條邊上異于頂點(diǎn)的一點(diǎn)，則沿多邊形一邊任取距離該交點(diǎn)左右兩側(cè)Δr的兩點(diǎn)，當(dāng)Δr→0時則必有一點(diǎn)位于另一多邊形外部，與補(bǔ)充定理矛盾，假設(shè)錯誤。

綜上，所有的情況下均不會出現(xiàn)法線段交叉的情況。即使用實(shí)交點(diǎn)定理及其補(bǔ)充定理的算法尋找實(shí)交點(diǎn)，然后再進(jìn)行裁剪交叉部分操作可以生成任何形狀（符合前提假設(shè)）的無交叉坡面線，充分性得證。

4 結(jié)果驗(yàn)證與分析

為了進(jìn)一步驗(yàn)證算法的有效性，設(shè)計3組試驗(yàn)。試驗(yàn)結(jié)果表明，ABRICT算法在動態(tài)繪制任何形狀（符合前提假設(shè)）的法線斜坡方面以及繪制的響應(yīng)時間方面有良好的性能。所有試驗(yàn)的測試環(huán)境為1臺CPU為Pentium 2.4GHz，512MB內(nèi)存，80G硬盤的PC機(jī)。為提高準(zhǔn)確度，第二、三組試驗(yàn)都運(yùn)行30次，取其均值作為試驗(yàn)結(jié)果。需要說明，響應(yīng)時間指自動生成坡面填充線的時間，不包括繪制上棱線與坡腳線的時間。

4.1 算法通用性對比驗(yàn)證

第一組試驗(yàn)選取浙江省建德市所轄16個鄉(xiāng)鎮(zhèn)中的5個作為試驗(yàn)對象，使用其地形圖中的與斜坡圖式類似的地貌數(shù)據(jù)，稱為“類斜坡圖式”。本組試驗(yàn)將采用ABRICT算法和CASS算法重新繪制這些地貌數(shù)據(jù)的坡面填充線。表1給出了“類斜坡圖式”的數(shù)量。

表1 試驗(yàn)數(shù)據(jù)數(shù)量Tab.1 Data for the experiment

使用ABRICT算法的試驗(yàn)中共生成1 280 757條填充線，耗時6h19min 10s（說明實(shí)現(xiàn)計算機(jī)自動制圖的必要性），得到的新地形圖（局部，新安江街道建德大橋附近）如圖6所示。使用人工判讀方式，未發(fā)現(xiàn)交叉和漏繪坡面線。若每2mm間隔繪制坡面填充線（包括長短線）［1］，理論上需要繪制1 281 366條，試驗(yàn)結(jié)果比理論值少是因?yàn)樵囼?yàn)數(shù)據(jù)中存在長度過小的類斜坡圖式，上棱線長度不是2mm的整數(shù)倍。同時采用計算機(jī)自動統(tǒng)計方法（即用空間分析方法求出每條坡面線的交點(diǎn)個數(shù)，交點(diǎn)個數(shù)等于0或1的記錄為無交叉，交點(diǎn)個數(shù)大于1的記錄為有交叉，該方法雖有缺陷但是可以接受）檢測所有的坡面線，未發(fā)現(xiàn)有交叉的記錄。結(jié)果表明，與CASS算法相比，ABRICT算法在實(shí)際應(yīng)用中具有很好的通用性。特別是，經(jīng)試驗(yàn)結(jié)果分析發(fā)現(xiàn)，反復(fù)提到現(xiàn)有繪圖軟件無法處理“特殊形狀”的斜坡圖式并不“特殊”，在試驗(yàn)選擇區(qū)域內(nèi)的山地附近，斜坡或陡崖普遍都呈“U型”。如圖6（a）中的“U型”斜坡呈現(xiàn)上棱線節(jié)點(diǎn)密集的情況，ABRICT算法也能夠很好處理，而CASS軟件繪制的圖式則出現(xiàn)大量交叉和漏繪的情況（圖6（b））。此外，對于上棱線節(jié)點(diǎn)密集的情況可以采用制圖綜合中的線段化簡算法對上棱線進(jìn)行預(yù)處理來提高效率，這將是今后對ABRICT算法進(jìn)行改進(jìn)的研究重點(diǎn)之一。

圖6 通用性試驗(yàn)結(jié)果圖（局部）Fig.6 Result of the experiment examining the generality

4.2 算法結(jié)果唯一性驗(yàn)證

第二組試驗(yàn)采用自左向右和自右向左的順序遍歷法線段生成如圖7所示的斜坡圖式。從圖中可以看出，使用ABRICT算法生成無交叉法線斜坡的最終圖案還與遍歷法線段的方向有關(guān)。也就是說ABRICT算法的充分性只是說明采用該算法能夠生成任何形狀（符合前提假設(shè)）的無交叉法線斜坡圖式，并不能說明生成的法線坡面線填充圖案唯一。但是，無論遍歷法線段方向如何，只要是依順序遍歷，生成的均為無交叉的斜坡圖式。

4.3 算法效率驗(yàn)證

第三組試驗(yàn)研究交叉的坡面線數(shù)量增加對ABRICT算法性能的影響。對第二組試驗(yàn)中的斜坡圖式進(jìn)行橫向擴(kuò)展（上棱線向兩邊延長，得到三個含有124條、200條、306條坡面長線的斜坡）和縱向擴(kuò)展（上棱線與坡腳線之間的距離增加）以增加ABRICT算法處理交叉坡面線的數(shù)量和坡面長線的總量（坡面線數(shù)量增加等價于坡面線間隔變小）。該組試驗(yàn)得到的三個試驗(yàn)數(shù)據(jù)如圖8所示。從圖中可以看出，在坡面長線數(shù)量一定的情況下，隨著需要處理的相交法線段數(shù)量的增加，使用ABRICT算法生成無交叉法線斜坡圖式的時間也隨之增加，但是斜率較低說明增加緩慢。且三條擬合趨勢線均呈現(xiàn)“低斜率高截距”的特征，說明影響繪制斜坡圖式效率的主要因素是坡面長線段的生成過程，使用ABRICT算法尋找實(shí)交點(diǎn)和裁剪操作則是一個次要因素。由趨勢線斜率隨坡面長線總數(shù)的增加呈現(xiàn)遞增規(guī)律可知，坡面長線總數(shù)的增加會提高遍歷法線段的查詢代價（算法今后改進(jìn)重點(diǎn)之一），即坡面長線總數(shù)越大，使用ABRICT算法尋找實(shí)交點(diǎn)和裁剪操作對整個斜坡圖式繪制效率的影響越大。

圖7 ABRICT算法從不同方向遍歷法線段繪制的斜坡Fig.7 Slopes drawn by traversing the normal segments in different order based on ABRICT algorithm

圖8 坡面線數(shù)量增加對算法性能的影響Fig.8 Impacts of the number of slope lines on the efficiency of the algorithm

5 結(jié) 論

研究斜坡坡面線的圖形生成方式，發(fā)現(xiàn)其圖形由斜坡的上棱線和坡腳線決定，屬于不規(guī)則地形圖式符號的動態(tài)填充問題。并且，由法線法繪制的坡面線會出現(xiàn)交叉現(xiàn)象，影響圖式的美觀，若手動處理交叉線將是一個復(fù)雜的過程。ABRICT算法，不僅克服了原有技術(shù)的不足，而且揭示了“對稱美”的普遍現(xiàn)象，對稱地選取兩條相鄰的相交法線段，對其進(jìn)行裁剪交叉線段的操作，生成的法線坡面線不再會產(chǎn)生交叉。此外，簡單證明繪制這種簡潔的無交叉坡面線的充要條件，并通過多組試驗(yàn)驗(yàn)證算法的有效性。也就是說，在四個前提假設(shè)之下，該算法在動態(tài)繪制地形圖所需要的任何形狀的法線自然（加固）斜坡、崩崖、陡崖、陡石山、堤岸等圖式符號方面具有較好的適用性。同時，該算法也可為其他非規(guī)則的圖案動態(tài)填充提供借鑒與啟發(fā)。

［1］ CSBTS.GB／T 7929—1995.Specifications for Cartographic Symbols 1∶500，1∶1 000，1∶2 000Topographic Maps［S］.Beijing：Standards Press of China，1996：94－99.（國家技術(shù)監(jiān)督局.GB／T 7929—1995.1∶500、1∶1 000、1∶2 000地形圖圖式［S］.北京：中國標(biāo)準(zhǔn)出版社，1996：94－99.）

［2］ PINEDA J.A Parallel Algorithm for Polygon Rasterization［J］.Computer Graphics（ACM），1988，22（4）：17－20.

［3］ MUKHERJEE M，CHAKRABORTY K.A Randomized Greedy Algorithm for the Pattern Fill Problem for DFM Applications［C］∥Proceedings of ISQED 2008.Palm Springs：IEEE，2008：344－347.

［4］ YANG Yong，LI Lin，WANG Hong，et al.Cartographic System Based on National Fundamental Geographic Data［J］.Geomatics and Information Science of Wuhan University，2008，33（3）：261－264.（楊勇，李霖，王紅，等.基于國家基礎(chǔ)地理信息數(shù)據(jù)的地圖制圖系統(tǒng)［J］.武漢大學(xué)學(xué)報：信息科學(xué)版，2008，33（3）：261－264.）

［5］ BAIN K A，GILES J R A.A Standard Model for Storage of Geological Map Data［J］.Computer and Geosciences，1997，23（6）：613－620.

［6］ HE Zhonghuan.Designing Technique of Complicated Linear Symbols in GIS Symbol Database［J］.Geomatics and Infor－mation Science of Wuhan University，2004，29（2）：132－134.（何忠煥.GIS符號庫中復(fù)雜線狀符號設(shè)計技術(shù)的研究［J］.武漢大學(xué)學(xué)報：信息科學(xué)版，2004，29（2）：132－134.）

［7］ CAI Xianhua，WU Li.Study of Symbol Library Data Structure and Algorithm Based on Property Unit［J］.Acta Geodaetica et Cartographica Sinica，2004，33（3）：269－273.（蔡先華，武利.基于特征元的符號庫數(shù)據(jù)結(jié)構(gòu)及算法探討［J］.測繪學(xué)報，2004，33（3）：269－273.）

［8］ WANG Tonghe，YUE Chunsheng，ZHAO Fulai，et al.A Quick Drawing Algorithm for Map Symbols Based on Template in Embedded GIS［J］.Journal of Geomatics Science and Technology，2009，26（5）：330－332.（王同合，岳春生，趙夫來，等.基于模板的嵌入式GIS地圖符號快速繪制算法［J］.測繪科學(xué)技術(shù)學(xué)報，2009，26（5）：330－332.）

［9］ ZHU Guorui，XU Zhiyong，WU Xiaofang.Design of Dynamic Map Symbol Based on Multi－transform Assembly［J］.Geomatics and Information Science of Wuhan University，2006，31（6）：548－551.（祝國瑞，徐智勇，吳小芳.基于多重變換組合的動態(tài)地圖符號設(shè)計［J］.武漢大學(xué)學(xué)報：信息科學(xué)版，2006，31（6）：548－551.）

［10］ HURNI L，DAHINDEN T，HUTZLER E.Digital Cliff Drawing for Topographic Maps：Traditional Representations by Means of New Technologies［J］.Cartographica：The International Journal for Geographic Information and Geovisualization，2001，38（1）：55－65.

［11］ YANG Nai，GUO Qingsheng，SHEN Dayong.Automatic Modeling of 3DCliff Symbol［J］.Geomatics and Information Science of Wuhan University，2010，35（4）：411－414.（楊乃，郭慶勝，沈大勇.三維陡崖符號的自動建模研究［J］.武漢大學(xué)學(xué)報：信息科學(xué)版，2010，35（4）：411－414.）

［12］ LV Gan.Research on Database－driven Cartography and Its Processing System Framework［D］.Hangzhou：Zhejiang University，2008.（呂干.數(shù)據(jù)庫驅(qū)動的制圖建模及其數(shù)據(jù)處理框架研究［D］.杭州：浙江大學(xué)，2008.）

ANewAlgorithmforCreatingSlopeLineswithNoIntersections

FANGLei1，2，LIURenyi2，LVGan1，2，DUZhenhong1，2，YAOShenjun3
1.Zhejiang Provincial Key Laboratory of GIS，Zhejiang University，Hangzhou 310028，China；2.Department of Geographic Information Science，Zhejiang University，Hangzhou 310027，China；3.Department of Geography，The University of Hong Kong，Hong Kong 999077，China

This study develops a new algorithm to create any kinds of slope lines with no intersections automatically.It gives enough evidence to support that the real－intersection and the complementary theorem proposed in this research are sufficient conditions of the generation of slope lines without any intersections.This method can dynamically draw any kind of normal－based slopes，scarps，escarpments，steep rock hills or embankments.The efficiency of the algorithm is tested by using three experiments.

slope；filled hatch；cartography；geographic information system

FANG Lei（1982—），male，PhD candidate，majors in GIS applications and GIS algorithms.

1001－1595（2011）04－0524－07

P208

A

國家863計劃（2007AA12Z182；2009AA12Z222）；中國國家博士后基金（20070421161）；浙江省重點(diǎn)攻關(guān)基金（2007C23091；2009C33011）；教育部博士點(diǎn)基金（20060335040；200803350017）

宋啟凡）

2010－04－02

2010－10－28

方雷（1982—），男，博士生，主要從事GIS應(yīng)用系統(tǒng)和算法方向的研究。

E－mail：rainfield.f＠gmail.com