車載導航電子地圖的路網模型

摘要：建立適合于車載導航系統的路網數據是車載導航系統的關鍵。該文描述了如何表達真實世界的交通要素，并結合實際情況給出數據模型。

關鍵詞：汽車導航；路網模型

中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2008)26-1803-02

Road Network Model for Vehicle Navigation System

XU Rui

(ECRIEE， Hefei 230031， China)

Abstract: The construction of road network for vehicle navigation system is the key part of navigation system. This paper firstly describes the traffic elements of the real world， then designs the road network model which considers the real traffic limits.

Key words: vehicle navigation; road network model

1 引言

路網數據是車載導航電子地圖中主要研究的內容。傳統路網模型的缺陷在于對真實世界的描述不夠詳盡，難以完整表達道路之間的拓撲關系和用戶所關心的交通信息。而且一般車載導航系統均在嵌入式環境下實現，對軟硬件要求很高，數據量過于龐大時將無法實現實時處理。因此必須對傳統路網模型進行改進，以適應車載導航系統的要求。

本文主要針對車載導航系統，從路網的邏輯層次、交通要素和數據模型三個方面來探討建立路網數據的方案。

2 邏輯層次

路網數據的邏輯描述常采用三個層次，即數據層(Level-0)、描述層(Level-1)和綜合層(Level-2)。數據層通過點、線和面等圖形數據描述地物的幾何外形和空間關系，用于儲存道路形狀。描述層在數據層的基礎上，將現實對象的特征提取為屬性值，即交通要素，用于地圖顯示和路徑引導。綜合層則對描述層進行綜合，描述要素間拓撲關系，用于路線計算。

如圖1所示，長江路由隔離帶分隔為正逆兩向車道，并與另兩條道路相交形成路口C1、C2。使用分層邏輯描述時，在數據層上，儲存長江路各車道的外形和路口位置。在描述層上，道路經雙向化后，長江路被表達為L1、L2，路口C1被表達為S1和S2，路口C2為S3和S4。在綜合層上，L1、L2被綜合為CL1，S1和S2為CS1，S3和S4為CS2。從圖中可看到數據層、描述層和綜合層三者之間的關系。

3 交通要素

道路錯綜復雜，路口千變萬化，描述哪些信息，之間的關系如何，是建立完整可靠的電子地圖的關鍵。參照歐洲地理數據文件格式標準(GDF)，導航電子地圖內容應包括道路與輪渡、隧道與橋梁等12大類。簡化后，路網數據可表達為簡單路段、連接點、綜合道路、綜合交叉口、道路附屬設施等交通要素。

簡單路段指兩個連接點之間的道路。在描述層中，路段和連接點均是最小可描述單元。路段的兩端各有一個連接點，按其數字化方向，第一個連接點稱為左節點，第二個連接點成為右節點。路段之間是互相獨立的，當一個路段的屬性發生變化是不會影響其它路段的。如圖2所示，LAB、LBE、LED、LDC和LCA是圖中所有的路段，它們在描述層中是獨立的，如果在LCD路段設置柵欄，此時LCD路段不可通行，但LCD路段的通行狀態的改變不會影響其它路段。

綜合道路指連接兩個綜合路口的道路。在綜合層中，一條道路可以包括一條或多條路段，這些路段一般屬性相同（如路名相同），但允許的交通流方向不同。如圖1所示，道路CL1包含了路段L1和L2，其兩端的交叉口分別是CS1和CS2。

綜合路口一般由一個路口內的多個連接點組成。在綜合層中，綜合路口可以包括一個或多個連接點，且這些連接點相互關聯，連接路段可由內部路段通達。如圖1所示，綜合路口CS1包含連接點S1和S2，綜合路口CS2包含連接點S3和S4。綜合路口的類型可由路口的圖形特征和交通功能來描述，一般按照路口連接道路的數量來區分：1) 三叉路口；2) 四叉或多叉路口(圖3-A)；3) 環島(圖3-B)；4) 立交橋(圖3-C)。

道路附屬設施指設立在道路兩旁固定位置上的一些用于交通指引和服務的設施。一般按照設施對交通流的控制功能來區分：1) 轉向限制，如禁左、禁止駛入等交通指示牌。描述了路段間轉向或通行路線的限制，包含時間限制信息和通行車輛限制信息；2) 方向路牌，描述道路出入口或分叉口處路牌所示的方向信息；3) 紅綠燈和測速點；4) 收費站、加油站和服務區。

4 數據模型

路網數據由三類實體集組成：節點集、邊集和交通限制集。它們之間的關系可用數學公式表述：RW = {N，R，LR}，R = {|x， y∈N，且L(x， y)}，L R = {|m，n∈N，L'(m，n)，且m與n存在公共節點}。RW代表路網。N代表節點集合。R代表邊集合，其元素是有序對，謂詞L(x， y)表示由節點x到節點y存在一條有向通路。LR代表交通限制集合，其元素是有序對，謂詞L'(m，n)表示從邊m到邊n存在限制。不同邏輯層次上的實體集表達的內容是不同的。在描述層，節點表達為連接點，邊為簡單路段。在綜合層，節點表達為綜合路口，邊為綜合道路。交通限制也不僅僅指轉向限制，還包括路牌、收費站等道路附屬設施。

在建立路網數據庫時，有效的組織數據庫表可減少數據冗余，提高效率。一般路網數據庫包含8個表，如圖4所示。綜合道路表包括路網中的各條道路。綜合道路由簡單路段組成，綜合路口由連接點組成，兩個相鄰連接點之間由簡單路段連接，線由點組成。

路網數據應以分級分簇方式組織。在地圖顯示過程中，選用的顯示比例尺越大，顯示的地理區域也越大，為保證地圖清晰并突出重點內容，須控制載入的數據量，并剔除次要要素。在拓撲分析過程中也存在同樣的問題。分級組織是把全體要素按重要性區分等級，具體的等級設定由要素的應用特性和數據特性共同決定。同一等級L的要素放置在一起組織成數據子集，稱該數據子集的等級為L。參考Kiwi-W標準，假定一共有n個等級，記為L0、L1、…、Ln，L0為最低等級，依次遞增，Ln為最高等級。以道路的修建等級作為劃分標準，將全國路網劃分為5級，完整路網作為L0級，市區主干道為L1級，縣鄉道為L2級，省道為L3級，國道、高速作為L4級。分簇組織是將空間上相近的要素組成集合，同一等級的數據子集分為若干簇。簇是地圖顯示、拓撲運算訪問接口所選用的最小單元。可參照《國家基本比例尺地形圖分幅和編號》的分幅標準結合K樹或R*樹進行分簇。

5 結束語

層次化的邏輯結構、完整的交通要素類型、精練的數據結構、高效且受控的數據組織方式是一個優秀的車載導航路網模型應具有的重要特征。本文在實際應用基礎上出發，說明了在車載導航電子地圖的各類交通要素，論述了它們之間的關系，并詳細描述了如何設計和組織路網數據庫。

基于上述模型，我們以分區方式建立全國的全境路網數據庫，并成功的應用到公司的產品之中，如圖5所示。經過長期實踐的檢驗，本文提出的路網模型能較完整的表達用戶對車載導航系統的使用需求，并保證了程序具有較低的性能要求和較高的運算效率。

參考文獻：

[1] Version3.0-95， European committee for standardization: Geographic data file (GDF)[S]，1999.

[2] 趙亦林.車輛定位與導航系統[M].北京:電子工業出版社，1999

[3] Consortium K W.Input for ISO Physical Storage Format[EB/OL].[2006-09-15].http://kiwi-w.mapmaster.co.jp/format_english/format_kihon.html.