移動導航電子地圖數(shù)據(jù)結(jié)構(gòu)設(shè)計

移動導航電子地圖數(shù)據(jù)結(jié)構(gòu)設(shè)計和特殊數(shù)據(jù)表示方法目錄CONTENTS二、特殊數(shù)據(jù)表示方法一、數(shù)據(jù)結(jié)構(gòu)一、數(shù)據(jù)結(jié)構(gòu)交通網(wǎng)絡(luò)中道路網(wǎng)是移動導航電子地圖數(shù)據(jù)中最為重要的內(nèi)容，也是路徑規(guī)劃、路徑引導、地圖匹配等功能實現(xiàn)的基礎(chǔ)。它的基本元素可以抽象為點、線、面，在連續(xù)歐氏空間中，點為零維元素、線為一維元素、面為二維元素。為實現(xiàn)實時的路徑搜索與信息查詢功能，點、線之間需要具有簡單的拓撲關(guān)系，因此,整個地圖平面可視為點、線組成的網(wǎng)絡(luò)，而面由封閉的線段組成。數(shù)據(jù)結(jié)構(gòu)具體說來，移動導航電子地圖數(shù)據(jù)可抽象為：（1）節(jié)點：表示空間對象所在的位置，或者線段的起始、終止點，它具有特定的拓撲性質(zhì)。（2）孤立點：表示線、面經(jīng)過的點，不具有拓撲性質(zhì)。（3）線（弧線）：起始與終止點為節(jié)點，并且具有若干孤立點的有序點集。（4）面：由若干弧線相連的封閉曲線圍成的區(qū)域稱為面。面以弧線的形式表示，但通過編碼與弧線區(qū)別，且其內(nèi)部填充方式可以設(shè)置。包含以上數(shù)據(jù)的電子地圖數(shù)據(jù)結(jié)構(gòu)稱為面向弧線的數(shù)據(jù)結(jié)構(gòu)，其圖形文件有ARC,NOD,IDX等三種。數(shù)據(jù)結(jié)構(gòu)ARC文件既包括了弧線的幾何參數(shù)，也包括弧線與節(jié)點、弧線與弧線之間的拓撲關(guān)系，其數(shù)據(jù)格式為：數(shù)據(jù)結(jié)構(gòu)ARC_IDCODEFrom_NODTo_NODHead_ARCTail_ARCPoint_Number（x,y）坐標串ARC_ID弧線標示號；CODE弧線編碼；From_NOD起始節(jié)點；To_NOD終止節(jié)點；Head_ARC指向弧線起始節(jié)點的下一弧線（入弧線）；Tail_ARC以弧線終止節(jié)點為起點的下一弧線（出弧線）；Tail_ARC弧線包含的點數(shù)；（x,y）坐標串各點的空間坐標。NOD文件表示了節(jié)點的幾何參數(shù)及節(jié)點與弧線的拓撲關(guān)系，通過節(jié)點標示號，還可實現(xiàn)節(jié)點與非空間數(shù)據(jù)的鏈接，其數(shù)據(jù)格式為:數(shù)據(jù)結(jié)構(gòu)NOD_IDIN_ARCOUT_ARC(x,y)NOD_ID節(jié)點標示號；IN_ARC以該節(jié)點為終止的第一條弧線（入弧線）；OUT_ARC以該節(jié)點為起始的第一條弧線（出弧線）；(x,y)該節(jié)點的空間坐標。IDX文件表示地圖中路的映射。一條路由若干條弧線構(gòu)成，通過IDX文件可以進行索引，同時Key_Item可用于實現(xiàn)與非空間數(shù)據(jù)的鏈接，其數(shù)據(jù)格式為:數(shù)據(jù)結(jié)構(gòu)Key_ItemARC_NumberARC_1ARC_2.......Key_Item道路名稱ARC_Number包括的弧線數(shù)ARC_1第一條弧線的標示號ARC_2第二條弧線的標示號圖1為點、線、面組成的某地圖區(qū)域，其中A、B、C為節(jié)點，D、E為孤立點，AB,BC,ADC,ADB,CEA,BDC為四條弧線,對應于該地圖的面向弧線的數(shù)據(jù)結(jié)構(gòu)文件分別見表1至表3。數(shù)據(jù)結(jié)構(gòu)設(shè)計圖1面向弧線的地圖表數(shù)據(jù)結(jié)構(gòu)設(shè)計表1ARC文件數(shù)據(jù)結(jié)構(gòu)ARC_IDCODEFrom_NODTo_NODHead_ARCTail_ARCPoint_Number(x,y)坐標串AB0ABCEABC2(xA,yA)(xB,yB)BC1BCADBCEA2(xB,yB)(xC,yC)ADC2ACCEACEA3(xA,yA)(xD,yD)(xC,yC)ADB3ABCEABC3(xA,yA)(xD,yD)(xB,yB)CEA4CAADCAB3(xC,yC)(xE,yE)(xA,yA)BDC5BCABCEA3(xB,yB)(xD,yD)(xC,yC)數(shù)據(jù)結(jié)構(gòu)設(shè)計表2NOD文件數(shù)據(jù)結(jié)構(gòu)NOD_IDIN_ARCOUT_ARC(x,y)ACEAAB(xA,yA)BABBC(xB,yB)CADCCEA(xC,yC)數(shù)據(jù)結(jié)構(gòu)設(shè)計表3IDX文件數(shù)據(jù)結(jié)構(gòu)Key_ItemARC_NumberARC_1ARC_2Road12ABBCRoad22ADCCEA二、特殊數(shù)據(jù)表示方法一、項目概況現(xiàn)代交通網(wǎng)發(fā)展越來越完善，復雜度也越來越大。在交通網(wǎng)中進行最短路徑査詢，不同于一般簡單有向拓撲網(wǎng)中的最短路徑查詢，它有其特殊性：特殊數(shù)據(jù)表示方法道路分級別高等級道路(高速公路、國道等)的通行條件好，速度快；低等級道路(街道、鄉(xiāng)村路等)的通行條件差，速度慢，還有其他等級的道路通行狀況好壞各不相同。一、項目概況道路有通行條件:

很多道路是單向通行的，且很多高等級道路以隔離帶劃分為兩條道路，均是單向通行，在拓撲網(wǎng)中表現(xiàn)為有向性。不僅如此還有其他限制。特殊數(shù)據(jù)表示方法一、項目概況道路交叉點有限制條件:

交通網(wǎng)在道路交叉點處有各種各樣的規(guī)制條件，最為常見的就是禁止向左轉(zhuǎn)彎，如圖1所示轉(zhuǎn)彎(1-0-2)是禁止的，所以在計算最短路徑時不能從道路(1-0)轉(zhuǎn)到道路(0-2)。有時并沒有交通規(guī)制說向哪里轉(zhuǎn)彎不行，但是有潛在的禁止轉(zhuǎn)彎規(guī)制。比如圖2，圖中箭頭表示單向通行方向。特殊數(shù)據(jù)表示方法圖1禁止轉(zhuǎn)圖2單向通一、項目概況道路交叉點有限制條件：

針對上述現(xiàn)實道路網(wǎng)中的特殊性，要實現(xiàn)移動導航電子地圖系統(tǒng)，首先要建立仿真的交通道路網(wǎng)絡(luò)拓撲模型，并且能對海量數(shù)據(jù)進行道路最短路徑計算。特殊數(shù)據(jù)表示方法圖3轉(zhuǎn)彎規(guī)則特殊數(shù)據(jù)表示方法在表中，特殊轉(zhuǎn)彎規(guī)則編碼指的是對通行時間、通行車輛的限制，通過該編碼在另外一張數(shù)據(jù)表中就可以查到該通行限制。自節(jié)點鄰節(jié)點道路等級距離