利用圖論解決平面圖元的關(guān)系算法

劉盾

摘要：本文將道路設(shè)計(jì)中三個(gè)圖元直線、圓曲線和緩和曲線，利用圖論組織起來(lái)。解決了方向、樁號(hào)和交點(diǎn)的自動(dòng)識(shí)別，實(shí)現(xiàn)了交點(diǎn)的動(dòng)態(tài)拖動(dòng)。

關(guān)鍵詞：圖論 道路平面設(shè)計(jì) 平面圖元

1圖論組織平面數(shù)據(jù)

道路平面設(shè)計(jì)中主要有三個(gè)元素，直線，圓曲線和緩和曲線[1]。這三個(gè)元素都擁有相同的公共屬性和自己獨(dú)特的屬性。本文采用圖論來(lái)組織這三個(gè)元素，解決了道路設(shè)計(jì)中路網(wǎng)和道路相交的問(wèn)題。

1.1圖論概要介紹

圖論是一種先進(jìn)和方便的理論，是最接近描述事物本身及事物之間關(guān)系的理論方法。圖論中有兩個(gè)基本構(gòu)成元素：節(jié)點(diǎn)和邊。節(jié)點(diǎn)是圖論中的元素，而邊依賴與點(diǎn)存在，邊用于連接兩個(gè)有關(guān)系的節(jié)點(diǎn)。而通常邊分為有方向和沒(méi)有方向兩種，邊的這種性質(zhì)將圖分為兩種有向圖和無(wú)向圖。

節(jié)點(diǎn)是圖論中的兩個(gè)基本要素之一。在描述事物關(guān)系中，節(jié)點(diǎn)通常用于描述事物本身。節(jié)點(diǎn)自身可以加上各種屬性。所以在各種數(shù)據(jù)結(jié)構(gòu)的表達(dá)方式中圖論是最為方便的。

邊是圖論的另一個(gè)基本要素。在描述事物關(guān)系中，邊通常用于描述事物與事物之間的關(guān)系。一般的數(shù)據(jù)結(jié)構(gòu)，比如鏈表、數(shù)組之類，對(duì)于事物之間的關(guān)系不太好表示。

總的來(lái)說(shuō)，圖論作為一種適用最為廣泛和靈活的理論，是用于描述現(xiàn)實(shí)世界實(shí)體的較為貼切的數(shù)學(xué)模型。在道路平面設(shè)計(jì)中，圖論正好用于組織三個(gè)平面的基本圖元，來(lái)表示道路交叉，以及更復(fù)雜的路網(wǎng)模型。

1.2平面圖元的圖論實(shí)現(xiàn)

道路平面設(shè)計(jì)中主要有三個(gè)元素，直線，圓曲線和緩和曲線[2]。這三個(gè)元素都擁有相同的公共屬性和自己獨(dú)特的屬性。在建模的時(shí)候，更具三個(gè)圖元的相通的地方，可以建立統(tǒng)一的公共屬性[3]。在圖論中用節(jié)點(diǎn)來(lái)對(duì)應(yīng)表示這三個(gè)圖元的起點(diǎn)和終點(diǎn)，用邊來(lái)表示這三個(gè)圖元。

關(guān)于圖論這個(gè)數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)。在各個(gè)語(yǔ)言中都已經(jīng)有較為成熟的解決方案。本文主要采用C#來(lái)做主要的編程語(yǔ)言，所以不能采用上面講述到的BGL庫(kù)，采用另一個(gè)開(kāi)源庫(kù)Quick Graph。將平面的三個(gè)圖元作為圖論中的邊，將這些圖元的起點(diǎn)和終點(diǎn)作為圖論中的節(jié)點(diǎn)。

每個(gè)圖元都具有起點(diǎn)和終點(diǎn)兩個(gè)屬性。這兩個(gè)屬性定義為圖論中的點(diǎn)。圖元的本身和圖元自帶的其他樁號(hào)方向類型的數(shù)據(jù)定義為圖論中的邊。因?yàn)閳D論中每個(gè)節(jié)點(diǎn)可以和多個(gè)邊相連接，所以利用圖論就可以處理道路相交和路網(wǎng)的情況。

2基于圖論組織平面圖元

圖論作為一個(gè)強(qiáng)大的理論工具用于道路設(shè)計(jì)中的平面圖元的組織，具有很好的適應(yīng)性。當(dāng)前處理平面圖元的方法，采用的是不靈活、速度慢、適用范圍狹窄的鏈表的理論。鏈表方法的缺點(diǎn)很多導(dǎo)致道路設(shè)計(jì)關(guān)于平面圖元的處理非常的被動(dòng)和臃腫[4]。

采用鏈表來(lái)組織平面圖元的原因，可能是因?yàn)橹塾谝粭l路。采用鏈表的線性結(jié)構(gòu)，來(lái)保存平面圖元的信息，有很多的缺點(diǎn)。首先，鏈表是一個(gè)線性結(jié)構(gòu)，并不能或者說(shuō)很難表示一個(gè)路與其他道路相交的情況。另外由于鏈表的限制，道路的數(shù)據(jù)變得非常臃腫，道路的設(shè)計(jì)方法變得單一。采用鏈表這個(gè)數(shù)據(jù)結(jié)構(gòu)，那么道路必須按順序依次設(shè)計(jì)，使得設(shè)計(jì)的方法受到了局限。

在涉及到道路與道路相交的交叉口時(shí)，鏈表并不能表示這種情況。使得有關(guān)系的兩條道路無(wú)法建立聯(lián)系。這樣的結(jié)果就是導(dǎo)致人工來(lái)處理相交的點(diǎn)的高程等一系列問(wèn)題。

2.1平面圖元方向的智能識(shí)別

在圖論中有一種特殊的圖，就是有向圖。有向圖的定義很簡(jiǎn)單，連接點(diǎn)與點(diǎn)之間的邊有一個(gè)特殊的屬性：方向。根據(jù)方向，講點(diǎn)與邊的關(guān)系細(xì)化。對(duì)于一個(gè)點(diǎn)P，連接它的邊有兩種，出邊和入邊。出邊就是邊的方向是從點(diǎn)P出發(fā)到另一個(gè)點(diǎn)。同樣，入邊就是邊的方向從另一個(gè)點(diǎn)出發(fā)回到點(diǎn)P。

在這里假設(shè)在一條道路中不會(huì)出現(xiàn)分叉和交匯，也不會(huì)出現(xiàn)循環(huán)。在道路設(shè)計(jì)中，平面中線通常是由各個(gè)平面圖元組成而成的。根據(jù)平面圖元的屬性，可以判斷平面圖元屬于哪條道路。

根據(jù)上面的方法，即可智能判斷和修正一條道路中出現(xiàn)方向錯(cuò)誤的圖元。首先，要求手動(dòng)點(diǎn)選道路上的某一個(gè)圖元。程序讀出該圖元的方向并顯示出來(lái)。詢問(wèn)方向是否正確。用戶選擇是或者否，根據(jù)用戶的反饋。程序讀取跟該圖元起點(diǎn)相連接的圖元，檢查道路名稱跟選中圖元一樣的平面圖元，檢查該圖元的方向。

在傳統(tǒng)的軟件設(shè)計(jì)中，由于采用的是鏈?zhǔn)浇Y(jié)構(gòu)，并不能存儲(chǔ)支路的情況，對(duì)于較為復(fù)雜的路網(wǎng)更是無(wú)能為力。通常傳統(tǒng)程序采用一根線的形式來(lái)組織數(shù)據(jù)，不方便修改更新，對(duì)于相交道路也沒(méi)有辦法處理。

而采用圖論的知識(shí)，可以讀取所有相交的情況，根據(jù)路名的不同加以分辨。在用戶只用指定一個(gè)圖元的方向的情況下，就可以識(shí)別整條道路的所有方向，速度快且方便。

2.2平面圖元樁號(hào)的智能識(shí)別

平面設(shè)計(jì)中首先是各個(gè)基本圖元的設(shè)計(jì)，其次將這些圖元連成一個(gè)整體，構(gòu)成平面路網(wǎng)，將數(shù)據(jù)用圖論的方式加以保存。第一個(gè)要處理的是平面設(shè)計(jì)中路網(wǎng)的方向的處理。

樁號(hào)的初始化處理采用圖論的知識(shí)加以處理顯得較為簡(jiǎn)單。首先，要求用戶選定平面中的任意圖元，設(shè)定其樁號(hào)。然后程序會(huì)根據(jù)圖元所在的位置和其他圖元的關(guān)系，進(jìn)行上游和下游的搜索來(lái)一個(gè)個(gè)的進(jìn)行樁號(hào)的初始化。對(duì)于每個(gè)平面圖元首先要讀取圖元的長(zhǎng)度屬性，根據(jù)長(zhǎng)度屬性計(jì)算樁號(hào)。

2.3平面圖元交點(diǎn)的智能識(shí)別與拖動(dòng)

通過(guò)圖元法來(lái)構(gòu)建一個(gè)平面道路，優(yōu)點(diǎn)是要求十分松散，用戶自主性大，可不按順序設(shè)計(jì)平面道路，設(shè)計(jì)比較自由。缺點(diǎn)是程序需要判斷的方面較多。需要程序自動(dòng)計(jì)算交點(diǎn)的坐標(biāo)等等。

2.3.1交點(diǎn)的處理判斷

計(jì)算交點(diǎn)的坐標(biāo)，較為復(fù)雜，涉及到自動(dòng)識(shí)別圖元，圖元順序，圖元的偏轉(zhuǎn)方向等。

1.保證道路的方向已經(jīng)自動(dòng)識(shí)別過(guò)了。

2.從起點(diǎn)開(kāi)始，判斷起點(diǎn)的圖元。

3.圖元若是直線，記錄直線所在的向量。若圖元不是直線，那么記錄圖元的起點(diǎn)切線方向所在的向量。設(shè)置偏轉(zhuǎn)方向變量為0。偏轉(zhuǎn)方向向量為1表示左偏，為-1表示右偏，為0表示為初始值，還沒(méi)有確定偏轉(zhuǎn)的方向。

4.往后面開(kāi)始遍歷。

5.（1）遇到直線圖元，則計(jì)算此直線圖元和先前向量的交點(diǎn)，若有交點(diǎn)則表示計(jì)算交點(diǎn)過(guò)程結(jié)束，程序回到第三步，循環(huán)求取交點(diǎn)。

（2）若遇到不是直線，那么檢查其偏轉(zhuǎn)方向，若偏轉(zhuǎn)向量為0則將偏轉(zhuǎn)向量賦值，程序回到第四步。若偏轉(zhuǎn)向量不為0，檢查偏轉(zhuǎn)向量的表示的偏轉(zhuǎn)方向和當(dāng)前圖元的偏轉(zhuǎn)方向是否一致。若一致，則程序回到第四步。若不一致，計(jì)算第三步保存的向量和現(xiàn)圖元終點(diǎn)切線的交點(diǎn)，這時(shí)求交點(diǎn)結(jié)束程序回到第三步。

（3）若此為最后一個(gè)圖元，計(jì)算圖元終點(diǎn)的切線向量和第三步求得的向量的交點(diǎn)。程序結(jié)束。

（4）圖元的終點(diǎn)的向量和第三步求得的向量的偏轉(zhuǎn)角度已經(jīng)大于180度，則計(jì)算此圖元的終點(diǎn)的切線向量和第三步求得的向量的交點(diǎn)。

2.3.2自動(dòng)識(shí)別交點(diǎn)后的圖形的動(dòng)態(tài)拖動(dòng)

動(dòng)態(tài)拖動(dòng)功能，能大大節(jié)約設(shè)計(jì)人員的設(shè)計(jì)時(shí)間，使得設(shè)計(jì)工作從以前緩慢的輸入數(shù)據(jù)不斷生成圖形來(lái)試錯(cuò)，一舉變成簡(jiǎn)單的鼠標(biāo)拖動(dòng)設(shè)計(jì)，設(shè)計(jì)完畢自動(dòng)給出設(shè)計(jì)參數(shù)的靈活多變的設(shè)計(jì)模式。對(duì)于具體的設(shè)計(jì)工作中，除了動(dòng)態(tài)拖動(dòng)之外，也能在拖動(dòng)中，鎖定某個(gè)參數(shù)，從而得到更好的設(shè)計(jì)結(jié)果。

下面以緩和曲線的基本型舉例，說(shuō)明拖動(dòng)交點(diǎn)，動(dòng)態(tài)設(shè)計(jì)的算法?；拘偷臉?gòu)成元素是緩和曲線中最基本的也是最普遍的。基本型的構(gòu)成是：直線1、緩和曲線1、圓曲線、緩和曲線2和直線2動(dòng)態(tài)拖動(dòng)基本型緩和曲線算法如下：

1.用鼠標(biāo)點(diǎn)選交點(diǎn)。根據(jù)點(diǎn)選的坐標(biāo)，搜索到交點(diǎn)。

2.根據(jù)交點(diǎn)，從圖中搜索交點(diǎn)對(duì)應(yīng)的道路的元素：直線1、緩和曲線1、圓曲線、緩和曲線2和直線2。

3.根據(jù)要求，讀出各段平面圖元的參數(shù)。直線1的兩個(gè)端點(diǎn)，緩和曲線1的A值A(chǔ)1，圓曲線的半徑R，緩和曲線2的A值A(chǔ)2和直線2的兩個(gè)端點(diǎn)。

4.根據(jù)先前的基本型的計(jì)算模塊，重新計(jì)算基本型的各個(gè)圖元的形狀和位置，并繪制出來(lái)，實(shí)現(xiàn)動(dòng)態(tài)拖動(dòng)的效果。

參考文獻(xiàn)：

[1]盧彭真. 道路中心線勘測(cè)CAD編程的方法. 云南交通科技， 2000（3）： 第55-57頁(yè).

[2]楊東援，朱照宏. 關(guān)于路線CAD系統(tǒng)中平面線形模型的研究. 華東公路， 1991（4）： 第36-40頁(yè).

[3]李全信. 線路中線坐標(biāo)計(jì)算的通用數(shù)學(xué)模型. 勘察科學(xué)技術(shù)， 2001（5）： 第43-47頁(yè).

[4]萬(wàn)年良. 市政道路線CAD系統(tǒng)的開(kāi)發(fā)與實(shí)現(xiàn). 黑龍江科技信息， 2008（29）： 第41頁(yè).

（作者單位：武漢市政工程設(shè)計(jì)研究院有限責(zé)任公司）