胡殿常，王晉秀

(解放軍1206地理信息中心，河北廊坊065000)

最短路徑分析在MapInfo中的實(shí)現(xiàn)

胡殿常，王晉秀

(解放軍1206地理信息中心，河北廊坊065000)

采用MapBasic語言，對(duì)MapInfo進(jìn)行功能擴(kuò)充，在MapInfo中實(shí)現(xiàn)最短路徑分析。程序首先完善路網(wǎng)表結(jié)構(gòu)，增加路網(wǎng)拓?fù)渌匦璧淖侄?然后進(jìn)行路網(wǎng)拓?fù)?，建立拓?fù)潢P(guān)系，并在此基礎(chǔ)上采用Floyd算法實(shí)現(xiàn)最短路徑分析。

MapInfo;最短路徑分析;MapBasic;Floyd;GIS

一、引 言

近幾年，GIS在我國快速發(fā)展，并隨著計(jì)算機(jī)軟、硬件技術(shù)的不斷成熟，這一高新技術(shù)已由研究室走向?qū)嶋H應(yīng)用領(lǐng)域，融入了人們的日常生活。電子導(dǎo)航是最重要的應(yīng)用之一，其中最短路徑分析是構(gòu)成電子導(dǎo)航的靈魂。此外，最短路徑分析在通信網(wǎng)絡(luò)、電力網(wǎng)絡(luò)等地理信息系統(tǒng)中也有著廣泛的應(yīng)用。

MapInfo是一款桌面地理信息系統(tǒng)軟件，以簡單易學(xué)、性能穩(wěn)定等特點(diǎn)，在GIS領(lǐng)域占有一定優(yōu)勢。由于其數(shù)據(jù)結(jié)構(gòu)相對(duì)簡單，無拓?fù)潢P(guān)系，因此軟件中沒有提供諸如最短路徑分析等基于拓?fù)潢P(guān)系的功能。但MapInfo提供了強(qiáng)大的二次開發(fā)接口，很多功能可通過二次開發(fā)解決。

MapInfo提供了3種二次開發(fā)方法:MapBasic語言、MapX組件和OLE技術(shù)。MapX和OLE適合開發(fā)獨(dú)立的應(yīng)用系統(tǒng)，而MapBasic比較適合MapInfo功能擴(kuò)展編程。MapBasic是MapInfo自帶的二次開發(fā)語言，是一種類似Basic的解釋性語言，利用Map-Basic編程生成的*.mbx文件可在MapInfo軟件平臺(tái)上運(yùn)行。本文主要介紹采用 MapBasic語言在MapInfo中實(shí)現(xiàn)最短路徑分析的方法。

二、完善表結(jié)構(gòu)

在MapInfo中，路網(wǎng)或其他網(wǎng)絡(luò)都以“線”的方式表現(xiàn)。每條線有“起點(diǎn)”和“終點(diǎn)”，統(tǒng)稱“端點(diǎn)”。線與線首尾相連，構(gòu)成路網(wǎng)，連接處稱為“頂點(diǎn)”或“節(jié)點(diǎn)”。然而，路段編號(hào)(ID)、路段起止點(diǎn)、路段長度等屬性，并沒有被記錄。因此，首先要完善表結(jié)構(gòu)，增加字段，記錄拓?fù)湫畔ⅰ?/p>

增加的字段有 LineID、Fnode、Tnode、Length、Selected，分別記錄路段編號(hào)、道路起點(diǎn)號(hào)、道路終點(diǎn)號(hào)、路段長度(m)和是否為選出的路段(計(jì)算結(jié)果圖形顯示時(shí)用)。主要程序片段為

Alter Table表名 (Add LineID Integer，F(xiàn)node Integer，Tnode Integer，Length float，Selected Logical)Interactive

三、建立拓?fù)潢P(guān)系

建立拓?fù)潢P(guān)系，主要需完成3項(xiàng)工作:給每個(gè)路段編號(hào);計(jì)算各路段長度;計(jì)算各路段的連接關(guān)系。前兩項(xiàng)可簡單計(jì)算賦值，第3項(xiàng)的算法核心是:先選定任一路段;然后尋找所有與該路段起點(diǎn)相連的路段，將相連處各路段端點(diǎn)(路段起點(diǎn)或終點(diǎn))賦相同編號(hào);路段終點(diǎn)作相同運(yùn)算。遍歷所有路段，作以上相同運(yùn)算。具體算法如下:

1)針對(duì)路網(wǎng)表，生成查詢表RoadNet。該表中，計(jì)算出路網(wǎng)中各路段的起點(diǎn)坐標(biāo)(Xf，Yf)和終點(diǎn)坐標(biāo)(Xt，Yt)，并將各路段起止點(diǎn)編號(hào)賦初值0(Fnode=0、Tnode=0)。

2)i=0。

3)查找RoadNet中第一個(gè)路段。

4)如果被查到的路段起點(diǎn)編號(hào)不為0，說明已賦過值，執(zhí)行步驟5);如果起點(diǎn)編號(hào)等于0，i=i+ 1，F(xiàn)node=i，即該頂點(diǎn)編號(hào)為i。

在RoadNet其他路段中查找起點(diǎn)與i點(diǎn)坐標(biāo)值相同的路段，給起點(diǎn)賦相同號(hào)(Fnode=i)。

在RoadNet其他路段中查找終點(diǎn)與i點(diǎn)坐標(biāo)值相同的路段，給終點(diǎn)賦相同號(hào)(Tnode=i)。

5)如果被查到的路段終點(diǎn)編號(hào)不為0，說明已賦過值，執(zhí)行步驟6);如果終點(diǎn)編號(hào)等于0，i=i+ 1，Tnode=i，即該頂點(diǎn)編號(hào)為i。

在RoadNet其他路段中查找起點(diǎn)與i點(diǎn)坐標(biāo)值相同的路段，給起點(diǎn)賦相同號(hào)(Fnode=i)。

在RoadNet其他路段中查找終點(diǎn)與i點(diǎn)坐標(biāo)值相同的路段，給終點(diǎn)賦相同號(hào)(Tnode=i)。

6)找到RoadNet中下一個(gè)路段，重復(fù)步驟4)、步驟5)。

7)遍歷所有路段，結(jié)束。

程序片段如下

采用相似的算法，計(jì)算與上路段終點(diǎn)相連的路段。遍歷全部路段，結(jié)束。

四、最短路徑計(jì)算

迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd)算法，是解決最短路徑問題的經(jīng)典算法。Dijkstra算法又稱為單源最短路徑，是從一個(gè)頂點(diǎn)出發(fā)，求該頂點(diǎn)至所有可到達(dá)頂點(diǎn)的最短路徑;Floyd算法可以計(jì)算出所有頂點(diǎn)之間的最短路徑，計(jì)算結(jié)果為兩個(gè)矩陣，一個(gè)是任意兩個(gè)頂點(diǎn)之間的最短距離;另一個(gè)是任意兩點(diǎn)之間的最短路徑。很顯然，F(xiàn)loyd算法時(shí)間復(fù)雜度要高。但一般情況下，路網(wǎng)不會(huì)在短時(shí)間內(nèi)更新，路網(wǎng)拓?fù)潢P(guān)系也相對(duì)固定，所以可采用Floyd算法，將計(jì)算結(jié)果矩陣以文件的形式保存，在最短路徑分析時(shí)，隨時(shí)調(diào)用，不再重復(fù)計(jì)算，這樣可大幅提高效率。MapInfo平臺(tái)上比較適合采用這種方法。該算法簡捷，這里不再介紹，但在算法實(shí)現(xiàn)中有兩點(diǎn)需要說明。

1.二維數(shù)組

在MapBasic語言支持的數(shù)據(jù)類型中，包含一維數(shù)組，不包含二維數(shù)組。但Floyd算法的鄰接矩陣需要用二維數(shù)組存儲(chǔ)、運(yùn)算，因此，在程序中需要用一維數(shù)組實(shí)現(xiàn)二維數(shù)組功能。程序片段如下

要訪問二維數(shù)組G(m，n)時(shí)，采用G(a(m，n))的方式調(diào)用，這樣就實(shí)現(xiàn)了用一維數(shù)組替代二維數(shù)組。

2.計(jì)算結(jié)果的展示

在MapInfo中，計(jì)算結(jié)果要以圖形(可視化)的方式表現(xiàn)，因?yàn)閳D形能更好地識(shí)別和解釋，達(dá)到所見即所得的效果。為方便處理，在路網(wǎng)表中，增加了Selected字段，最短路徑分析時(shí)，將最短路徑所包含路段的Selected值賦為1，最后在路網(wǎng)表中查找Selected=1即可。程序如下

五、效果展示

1)啟動(dòng)MapInfo，打開或新建一個(gè)路網(wǎng)表。

2)運(yùn)行最短路徑分析程序，MapInfo中增加了“最短路徑分析”菜單，如圖1所示。

圖1 程序運(yùn)行界面

3)依次點(diǎn)擊“最短路徑分析”、“路網(wǎng)拓?fù)洹?，進(jìn)行路網(wǎng)拓?fù)?每個(gè)路網(wǎng)只進(jìn)行一次路網(wǎng)拓?fù)浼纯?。

4)依次點(diǎn)擊“最短路徑分析”、“查找最短路徑”，選取最短路徑分析工具，在圖中起點(diǎn)處按下鼠標(biāo)左鍵，移動(dòng)到終點(diǎn)處松開鼠標(biāo)，即可顯示出起點(diǎn)至終點(diǎn)的最短路徑，如圖2、圖3所示。

圖2 定義最短路徑起止點(diǎn)

六、結(jié)束語

最短路徑分析是GIS的重要組成部分，有著廣泛的應(yīng)用。本文提供了一種在MapInfo中實(shí)現(xiàn)這一功能的算法。通過實(shí)際驗(yàn)證，該方法界面友好、操作簡捷、運(yùn)算速度快、計(jì)算結(jié)果準(zhǔn)確、性能穩(wěn)定，有一定的實(shí)用價(jià)值。

圖3 最短路徑分析結(jié)果

［1］ 沙宗堯，邊馥苓.單源最短路徑算法的圖示教學(xué)設(shè)計(jì)與實(shí)踐［J］.測繪通報(bào)，2010(4):58-61.

［2］ 彭波.數(shù)據(jù)結(jié)構(gòu)［M］.北京:清華大學(xué)出版社，2002.

［3］ 張劍平，任福繼，葉榮華，等.地理信息系統(tǒng)與MapInfo應(yīng)用［M］.北京:科學(xué)出版社，1999.

［4］ 李勝樂，陸遠(yuǎn)忠，車時(shí).MapInfo地理信息系統(tǒng)二次開發(fā)實(shí)例［M］.北京:電子工業(yè)出版社，2004.

［5］ 王曉東，趙全磊，吳建民.MapBasic在MapInfo功能擴(kuò)展中的應(yīng)用［J］.測繪通報(bào)，2007(8):51-54.

［6］ 陳繼山，須鼎興.使用Shape文件進(jìn)行最短路徑的分析與跟蹤［J］.測繪通報(bào)，2004(12):8-10.

［7］ 張虎，施一民.基于MapX的公安110報(bào)警系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)［J］.測繪通報(bào)，2004(9):23-25，39.

［8］ 司連法，王文靜.快速Dijkstra最短路徑優(yōu)化算法的實(shí)現(xiàn)［J］.測繪通報(bào)，2005(8):15-18.

［9］ 夏松，韓用順.GIS中最短路徑算法的改進(jìn)實(shí)現(xiàn)［J］.測繪通報(bào)，2004(9):40-42.

Realization of the Shortest Path Analysis in MapInfo

HU Dianchang，WANG Jinxiu

0494-0911(2012)06-0087-03

P208

B

2011-12-02

胡殿常(1968—)，男，河北淶水人，工程師，主要從事GIS工作。