劉盾

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

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

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

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

1.1圖論概要介紹

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

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

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

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

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

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

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

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

2基于圖論組織平面圖元

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

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

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

2.1平面圖元方向的智能識別

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

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

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

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

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

2.2平面圖元樁號的智能識別

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

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

2.3平面圖元交點的智能識別與拖動

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

2.3.1交點的處理判斷

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

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

2.從起點開始，判斷起點的圖元。

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

4.往后面開始遍歷。

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

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

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

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

2.3.2自動識別交點后的圖形的動態(tài)拖動

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

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

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

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

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

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

參考文獻(xiàn)：

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

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

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

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

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