判斷折線自相交的完備算法與快速顯示技術(shù)

魏志云 王國(guó)光 李成翔

摘要：折線自相交是地理信息系統(tǒng)（Geographic Information System，簡(jiǎn)稱GIS）空間線性數(shù)據(jù)檢查處理中的一個(gè)重要問(wèn)題，如何快速判斷、準(zhǔn)確定位是這個(gè)問(wèn)題的關(guān)鍵。在對(duì)MicroStation API熟練掌握并運(yùn)用的基礎(chǔ)上，對(duì)折線自相交中存在交叉、重復(fù)、重疊的情況進(jìn)行全面分析，解決了API開(kāi)發(fā)庫(kù)函數(shù)無(wú)法對(duì)線段重疊情況下的相交判斷問(wèn)題，并最終實(shí)現(xiàn)求交結(jié)果的預(yù)覽和快速顯示功能，極大方便用戶快捷、準(zhǔn)確地辨識(shí)折線自相交的類型和位置。

關(guān)鍵詞：GIS；MicroStation；自相交；快速顯示

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）06-0229-03

在地理信息數(shù)據(jù)質(zhì)量控制中，折線自相交是影響線型數(shù)據(jù)質(zhì)量的關(guān)鍵因素，在地圖綜合、空間分析等領(lǐng)域有著廣泛的應(yīng)用。例如，地圖上的等高線、水系、境界等線狀要素的綜合，要求同代表某一要素的折線自身不能相交。但是由于地圖上的曲線具有復(fù)雜、多樣和密集等特點(diǎn)，運(yùn)用一定的算法化簡(jiǎn)后不可避免地產(chǎn)生自相交，因此需要設(shè)計(jì)一套合適的算法來(lái)消除這種現(xiàn)象。

近年來(lái)，國(guó)內(nèi)外學(xué)者在判斷折線自相交方面開(kāi)展了一些工作，但都存在效率不高的問(wèn)題。MicroStation是一款三維CAD設(shè)計(jì)軟件，具有強(qiáng)大的API開(kāi)發(fā)庫(kù)函數(shù)，為該軟件的二次開(kāi)發(fā)提供了很好的接口。目前該軟件庫(kù)函數(shù)對(duì)于線段內(nèi)部相交的情況有較好的解決，而對(duì)于線段重疊的情況則沒(méi)有考慮，因此設(shè)計(jì)一套完備的求交算法，彌補(bǔ)線段求交的不足顯得非常必要。

本文利用MicroStation API開(kāi)發(fā)庫(kù)函數(shù)求解一般情況下的折線自相交，詳細(xì)分析了折線自相交在重復(fù)、重疊情況下的自相交，全面而又準(zhǔn)確地判斷出折線自相交的類型和位置，為用戶快速判斷折線自相交提供了一種可靠方法。

1折線自相交判斷相關(guān)定義

1.1折線自相交的定義

設(shè)有折線L={p₁，…p_i，…p_n}，（i=1，2，…，n），p_i是折線上順次相連線段的端點(diǎn)。若除了相鄰線段間的連接端點(diǎn)p₁，p₂，…，p_n外，折線上的線段之間還存在其他的交點(diǎn)，則定義此折線為自相交折線。

1.2判斷折線自相交的一般算法

判斷折線自相交一般采用如下算法：對(duì)于折線三上的線段，按照其連接順序分解為n-1條兩點(diǎn)組成的線段，然后兩兩判斷這些線條之間是否相交，根據(jù)交點(diǎn)情況和自相交的定義來(lái)判斷折線L是否自相交。該算法很成熟，在相關(guān)論文中已經(jīng)有介紹，在此不予給出。

折線自相交的一般算法對(duì)于線段內(nèi)部相交適用，但對(duì)于線段重疊情況下的相交無(wú)法判斷，如完全重疊、部分重疊等。本文在MicroStation已有函數(shù)的基礎(chǔ)上，補(bǔ)充折線自相交在重疊情況下的判斷，完善了折線自相交的全部情況。

1.3折線自相交的分類

為了更好的說(shuō)明問(wèn)題，將自相交分為：重點(diǎn)式自相交、交叉式自相交、重疊式自相交三種情況，相交結(jié)果分成重復(fù)點(diǎn)、交點(diǎn)＼重疊點(diǎn)、重疊線三類。

（1）重點(diǎn)式自相交判斷

重點(diǎn)式自相交是折線中連續(xù)兩個(gè)或者多個(gè)頂點(diǎn)出現(xiàn)在同一位置，也即折線中存在長(zhǎng)度為零的線段，它是折線自相交中一種常見(jiàn)類型。在繪制地圖線性要素的時(shí)候，難免會(huì)出現(xiàn)重復(fù)點(diǎn)現(xiàn)象，如圖1所示。

對(duì)折線中重復(fù)點(diǎn)進(jìn)行排除算法比較簡(jiǎn)單，只需要比較當(dāng)前點(diǎn)與下一個(gè)節(jié)點(diǎn)坐標(biāo)是否相等即可，若該點(diǎn)與下一頂點(diǎn)坐標(biāo)一樣，則判斷該點(diǎn)為重復(fù)點(diǎn)，并將下一頂點(diǎn)刪除，依此循環(huán)判斷。

（2）交叉式自相交判斷

交叉式自相交是折線中不平行線段之間產(chǎn)生交點(diǎn)，包括內(nèi)部點(diǎn)和端點(diǎn)，它是折線自相交的一種普遍類型。交叉式自相交判斷用到MicorStation API中三維線段求交函數(shù)mdlVec_inter-sectXYZLines，該函數(shù)需要分別輸入兩條線段的首尾端點(diǎn)坐標(biāo)以及容差，輸出交點(diǎn)坐標(biāo)、交點(diǎn)分別在兩條線段中的比例參數(shù)paramAP和paramBP。

根據(jù)比例參數(shù)paramAP、paramBP，在排除外部相交的情況下，可將交叉式自相交分為如下4類。

（3）重疊式自相交判斷

為了加快判斷速度，在判斷重疊式自相交之前，增加兩線段是否平行的判斷，這里用到MicroStation API中向量平行測(cè)試函數(shù)mdlVec_areParallel。

重疊式自相交是折線中平行線段間的重疊，包括重疊點(diǎn)和重疊線，它是折線自相交的一種特殊類型。重疊點(diǎn)是指兩線段中某一端點(diǎn)坐標(biāo)相同；重疊線是指兩線段中某一段坐標(biāo)相同。為了全面分析相交的情況，本文采取端點(diǎn)距離判斷法，實(shí)現(xiàn)重疊式自相交的判斷，其算法思想如下：

2）一端點(diǎn)重合

如果端點(diǎn)距離Dist（i，j）、Dist（i，j+1）、Dist（i+1，j）、Dist（i+1，j+1）中僅有一個(gè)為零，則判斷為一端點(diǎn)重合，相交結(jié)果為重疊點(diǎn)或重疊線。首先將其分為如下4大類，然后每大類又可分成3種具體情況，需要根據(jù)其余四個(gè)距離之間的關(guān)系進(jìn)一步判斷相交結(jié)果，其示意圖解如表3。

3）無(wú)端點(diǎn)重合

如果端點(diǎn)距離Dist（i，j）、Dist（i，j+1）、Dist（i+1，j）、Dist（i+1，j+1）都不為零，則判斷為無(wú)端點(diǎn)重合，相交結(jié)果要么是部分重合，也即相交結(jié)果為重疊線，要么不相交。本文對(duì)于部分重合的情況羅列如下。

2判斷折線自相交的完備算法

基于以上對(duì)折線自相交判斷的詳細(xì)分類和求解方法介紹，研究出一套完整的折線自相交判斷算法，該算法基本步驟如下。

第一步：設(shè)折線選擇集LS的個(gè)數(shù)為m，遍歷LS，獲取折線LS（i）的坐標(biāo)信息，其中i=0，1，…，m-1；

第二步：首先對(duì)折線LS（i）進(jìn)行重點(diǎn)式自相交判斷，若有重復(fù)點(diǎn)，則將重復(fù)點(diǎn)添加到相交集合中，并將該重復(fù)點(diǎn)從折線點(diǎn)集中刪去。

第三步，設(shè)折線LS（i）上點(diǎn)的個(gè)數(shù)為n，則將折線看成n-1條依次相連的線段構(gòu)成，判斷折線自相交即可分解為判斷這n-1條線段兩兩之間是否相交。將第i條線段記為L(zhǎng)（j），其中j=0，1，…，n-3；其后的n-j-1條線段中的一段記為L(zhǎng)（k），其中k=j+1，…，n-2。第{條都要與其后的n-j-1條線段進(jìn)行求交計(jì)算，時(shí)間復(fù)雜度為O（n²）。

第四步：判斷線段L（j）與線段L（k）矩形外包是否有交集，若有交集，則跳到第五步，否則返回到第三步進(jìn)行下一對(duì)線段的相交判斷；

第五步：應(yīng)用MicroStation自帶三維求交函數(shù)mdlVec_inter-sectXYZLines進(jìn)行求交計(jì)算，若求交成功，則根據(jù)比例參數(shù)進(jìn)一步判斷是否交叉式自相交，若是交叉式自相交則求出交點(diǎn)，并將交點(diǎn)添加到相交集合中，返回到第三步進(jìn)行下一對(duì)線段的相交判斷；若不成功，則跳到第六步。

第六步：應(yīng)用MicroStation自帶向量平行測(cè)試函數(shù)mdlVec_areParallel判斷兩條線段是否平行，若平行，則進(jìn)行重疊式自相交判斷，并求出重疊點(diǎn)或重疊線的坐標(biāo)，并將相交結(jié)果添加到相交集合中，最后返回到第三步進(jìn)行下一對(duì)線段的相交判斷。

根據(jù)以上步驟，其算法流程圖如圖4所示。

3計(jì)算結(jié)果的預(yù)覽和快速顯示

為了讓用戶更加方便地了解相交的位置和類型，本算法增加了相交結(jié)果的預(yù)覽和陜速高亮顯示功能。

相交結(jié)果預(yù)覽采取序號(hào)和相交類型組成，相交類型可分為三種：交點(diǎn)/重疊點(diǎn)、重疊線、重復(fù)點(diǎn)，分別用0、1、2及以上表示，其對(duì)應(yīng)關(guān)系如表4所示。

在MicroStation中，開(kāi)發(fā)者可以通過(guò)繪制臨時(shí)元素和臨時(shí)幾何圖形兩種方式實(shí)現(xiàn)相交結(jié)果的高亮顯示。二者的區(qū)別在于MicroStation Development Library（MDL）函數(shù)只能創(chuàng)建一個(gè)普通的元素，然后將該元素轉(zhuǎn)化為臨時(shí)元素，當(dāng)視圖變化、元素較多時(shí)，臨時(shí)元素會(huì)不斷地被創(chuàng)建，占用較大內(nèi)存，顯示延遲；而通過(guò)MicroStation API中的IviewTransients接口可以定義任意幾何形狀，無(wú)需創(chuàng)建元素，能更方便快速地控制其在視圖更新過(guò)程中的顯示。

顯然，用戶期望知道相交結(jié)果的位置，然后手動(dòng)修改，而不希望該相交結(jié)果變成臨時(shí)元素被不斷添加到視圖中，影響效率。因此，本文采取第二種方法，通過(guò)IviewTransients接口生成臨時(shí)幾何圖形，用戶可以通過(guò)雙擊預(yù)覽數(shù)據(jù)列表行，精確定位該相交位置。

從圖5、圖6測(cè)試實(shí)例中我們可以得出，根據(jù)以上算法求解的自相交情況與實(shí)際情況相當(dāng)吻合，用戶可以掌握全部自相交的數(shù)據(jù)，并能快速定位，提高了查找效率，為用戶進(jìn)一步調(diào)整提供了很大的方便。

4結(jié)束語(yǔ)

本文在MicroStation API的基礎(chǔ)上，對(duì)折線自相交進(jìn)行了詳細(xì)分類，?？紤]了折線自相交會(huì)出現(xiàn)的所有情況，采用距離判斷法解決折線某段重合下的自相交，從而設(shè)計(jì)出判斷折線自相交的完備算法。由于在進(jìn)行自相交計(jì)算之前需要通過(guò)矩形外包交集測(cè)試，因此該算法能快速判斷線性元素是否自相交。

利用IviewTransients接口實(shí)現(xiàn)相交結(jié)果的快速顯示，對(duì)于海量數(shù)據(jù)自相交結(jié)果的顯示，其優(yōu)越性更加明顯。該算法提高了數(shù)據(jù)處理效率和數(shù)據(jù)的準(zhǔn)確性，便于用戶準(zhǔn)確定位并進(jìn)行手動(dòng)調(diào)整，具有實(shí)現(xiàn)簡(jiǎn)單、檢查全面、易于查找、穩(wěn)定性好等特點(diǎn)。