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

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

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

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

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

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

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

1 引 言

《地形圖圖式》［1］（GB／T 7929—1995）規(guī)定：斜坡指各種天然形成和人工修筑的坡度在70°以下的坡面地段。其樣式如圖1所示，符號的上沿實線表示斜坡的上棱線，長短線表示坡面。符號的長線一般繪至坡腳，當(dāng)坡面較寬且有明顯坡腳線時，可測繪坡腳線，以范圍線（點線）表示。計算機自動制圖軟件中斜坡符號的一般畫法：確定上棱線和坡腳線后繪制一組自上棱線開始指向坡腳線的長短相間的坡面線。坡面長短線有兩種畫法：等分法和法線法（圖1（a）和圖1（b））。其中法線法是將上棱線按固定長度等分，由各等分點出發(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)生成，無法提前定制；④ 坡面線在上棱線附近均為等間距的法線段，若不進行截取操作會在坡腳線附近大量交叉，破壞填充圖案的美觀性。而計算機圖形學(xué)專家往往將多邊形區(qū)域填充的研究重點集中在實現(xiàn)規(guī)則圖案的填充算法上［2－3］；制圖學(xué)專家的研究則將研究重點集中在GIS空間數(shù)據(jù)與地形圖圖式一體化的模型研究上［4－5］，符號或符號庫的合理設(shè)計和建立［6］，符號化效率［7－8］，隨時間變化的動態(tài)符號生成［9］，顏色、線條等組合方法對符號進行表達［10］等方面；文獻［11］甚至提出三維陡崖的自動建模方法。而少有學(xué)者系統(tǒng)地研究類似坡面線這類具有上述四個特點的圖式符號動態(tài)生成方法。一些測繪制圖軟件（如南方CASS6.1）或使用人機交互方式，或使用自動方式從技術(shù)上解決部分法線斜坡坡面線的交叉問題，但也僅限于形狀較規(guī)則的法線斜坡，對于是否適用于所有形狀坡面線的填充并未證明。本文在文獻［12］的基礎(chǔ)上提出一種基于實交點定理及其補充定理的動態(tài)繪制任何形狀斜坡的無交叉坡面線算法較好地解決這一問題。

2 算法介紹

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

2.1 前提假設(shè)

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

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

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

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

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

2.3 實交點定理及其缺陷

2.3.1 CASS算法及其缺陷

實交點的定義提供了尋找實交點的方法。由于確定初始實交點的位置更為重要，尋找第一對相交法線段便成為解決問題的關(guān)鍵。CASS算法是諸多尋找實交點的算法中應(yīng)用最廣的一個。它可描述為：自左向右（或自右向左）遍歷法線段，將第一對相交法線段的交點作為初始實交點，并進行裁剪處理；然后將處理后的法線段內(nèi)側(cè)的相鄰法線段的交點作為事實實交點，再進行裁剪處理，直到不再存在相交法線段為止。使用CASS算法生成的無交叉法線自然斜坡圖式如圖3所示。但是，該算法并不能對所有形狀的斜坡完成坡面區(qū)域的“美觀填充”。法線坡面線的美觀之處在于其沿上棱線夾角角平分線呈現(xiàn)一種對稱性。圖3（a）中斜坡圖式AB、BC段坡面線存在明顯的對稱性，而CD段坡面線存在一塊只有坡面短線而沒有坡面長線的空白區(qū)且不與BC段對稱，說明該區(qū)域的坡面長線因為找不到與其相交的坡面長線而被刪除，即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算法的貢獻在于為斜坡圖式提供一種繪制思路：如果找到最外圍的一個交點（即初始實交點），并以該點對線段進行裁剪操作，則該線段就不會再與更小范圍中的其他法線段產(chǎn)生交點。即只處理“相交”的坡面線，忽略上棱線角度和坡面線間隔的判斷。然而，“初始實交點存在第一對相交法線段上”并不是一個好的科學(xué)表述，要在眾多法線段中得到“第一對”相交法線段，需要進行大量空間運算和驗證，導(dǎo)致自動化算法復(fù)雜，可操作性降低。而筆者發(fā)現(xiàn)初始實交點的位置呈現(xiàn)一定的規(guī)律性，只存在于相鄰的兩條法線上。所以，因循CASS算法的思路，基于“相鄰”這一空間位置概念提出一種實交點存在性的科學(xué)表述——實交點定理。

2.3.2 實交點定理

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

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

2.4 基于實交點定理及補充定理的算法描述

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

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

3 理論證明

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

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

3.1 基于實交點定理算法生成無交叉坡面線的必要性證明

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

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

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

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

3.2 基于實交點定理及其補充定理算法生成無交叉坡面線的充分性證明

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

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

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

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

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

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

4.1 算法通用性對比驗證

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

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

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

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

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

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

4.3 算法效率驗證

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

圖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)象，對稱地選取兩條相鄰的相交法線段，對其進行裁剪交叉線段的操作，生成的法線坡面線不再會產(chǎ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）；浙江省重點攻關(guān)基金（2007C23091；2009C33011）；教育部博士點基金（20060335040；200803350017）

宋啟凡）

2010－04－02

2010－10－28

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

E－mail：rainfield.f＠gmail.com