一種電子地圖要素和屬性的組織方式

鄭振貴，馬洪兵，陳從華

(1.清華大學 電子工程系，北京 100084; 2.廈門雅迅網(wǎng)絡股份有限公司，福建 廈門 361008)

0 引 言

電子地圖(Electronic Map)又稱數(shù)字地圖，通常將地圖數(shù)據(jù)以數(shù)字方式存儲并通過計算機系統(tǒng)處理后，最終在電子設備屏幕上顯示地圖數(shù)據(jù)信息[1]。隨著數(shù)字空間數(shù)據(jù)的廣泛應用以及計算機技術(shù)的不斷發(fā)展，電子地圖也越來越深入普通用戶生活中，如今在社會的各個領(lǐng)域幾乎都能看到電子地圖服務的應用。然而，電子地圖應用功能的不斷擴展，對電子地圖空間數(shù)據(jù)的組織和利用的要求也就越來越高。特別是以電子地圖作為核心的定位服務、智能交通系統(tǒng)，電子地圖數(shù)據(jù)的容量過大、更新不易等問題往往成為在這些應用領(lǐng)域的一個“瓶頸”。因此，如何建立一種高效、優(yōu)質(zhì)的電子地圖數(shù)據(jù)結(jié)構(gòu)具有重大的意義[2-5]。

1 地圖要素的組織

1.1 多層級的區(qū)塊劃分

由于大容量的電子地圖數(shù)據(jù)不適合一次性讀取并進行操作，即使全部讀取后往往也不需要全部進行顯示，這樣大大浪費了電子設備有限的資源。采用區(qū)塊劃分的方式組織地圖數(shù)據(jù)，能明顯減少電子地圖顯示設備的資源消耗，緩解強勢數(shù)據(jù)與弱勢資源之間的矛盾[6]。

傳統(tǒng)的地圖數(shù)據(jù)格式（KIWI、SDAL等）在進行區(qū)塊劃分時往往采用了集成、分割格網(wǎng)等復雜的邏輯結(jié)構(gòu)，以不規(guī)則多邊形或者存在重疊的拓撲關(guān)系進行組織。這種方式在進行地圖數(shù)據(jù)增量更新和維護時顯得過于煩瑣復雜，小部分的地圖數(shù)據(jù)改動可能牽扯到大量的邏輯結(jié)構(gòu)調(diào)整。針對上述問題，本文采用了一種更為高效且易于維護的多層級區(qū)塊劃分方式。

首先，采用規(guī)則矩形格網(wǎng)進行區(qū)塊劃分，即在同一地圖顯示層級內(nèi)按照相等的矩形劃分出多個區(qū)塊，區(qū)塊內(nèi)的地圖要素信息存儲在該區(qū)塊的地圖數(shù)據(jù)中，從而確保每一個地圖要素的位置可以被唯一地確定。每一個地圖要素必須是完全包含在一個區(qū)塊或跨多個區(qū)塊，如圖1所示。

圖1 地圖要素按區(qū)塊劃分Fig.1 Block division of map elements

任何地圖要素如果其幾何形狀延伸超過一個以上的區(qū)塊，則按區(qū)塊邊界進行修剪并且修整的各個部分被分配到相應的區(qū)塊內(nèi)。

其次，為滿足用戶在不同尺度上觀察地圖要素的分布及相互關(guān)系的需要，采用多個層級尺度的形式來表達地圖要素的詳細程度。不同層次下區(qū)塊的大小不同，層級越高區(qū)塊越大，層級越低區(qū)塊越小。地圖要素在高層級的區(qū)塊存放的數(shù)據(jù)比較粗略，而在低層級的塊存放的數(shù)據(jù)比較詳細，隨著層級由低至高的變化地圖要素會被綜合，次要的信息將被過濾掉，以滿足用戶對多層次地圖顯示詳盡不一需求[7]，如圖2所示。

圖2 地圖多層級區(qū)塊劃分Fig.2 Scale level of map elements

電子地圖的多層級的表達本質(zhì)上是滿足了用戶的視覺認知要求，不同層級的地圖展示過程中,用戶對于地圖要素的認識也得以深化[8]。在最終地圖應用上，當?shù)貓D需要顯示更大比例尺的范圍，高層級的地圖數(shù)據(jù)便能支持快速顯示細節(jié)較少的大面積區(qū)域。另外，類似長距離路徑規(guī)劃的應用，可以很快地計算和考慮到更重要的道路類型。當?shù)貓D應用需要顯示更小比例尺的地圖詳情，如街區(qū)道路及建筑以及短距離路徑規(guī)劃應用等，低層級的地圖數(shù)據(jù)由于含有更多的地圖細節(jié)信息便能更好地支持這些場景[9]。

這種地圖數(shù)據(jù)多層級的區(qū)塊劃分方式，由于相同層級下區(qū)塊間不重疊，不同層級的區(qū)塊相對獨立，不用像傳統(tǒng)的地圖數(shù)據(jù)格式那樣維護復雜的區(qū)塊邏輯結(jié)構(gòu)，進行地圖的增量更新時也僅僅將對應層級的區(qū)塊數(shù)據(jù)替換即可，從而提高了地圖更新的效率和穩(wěn)定性。

1.2 地圖要素分類

所有真實世界的對象都可以被電子地圖以一個或多個地圖要素在不同層級上展現(xiàn)。地圖要素按照空間矢量數(shù)據(jù)組織的基本形式一般分為點、線和面三種要素主類[10]。

點狀地圖要素一般是不能按比例尺表示，只能按點定位的符號標識，如行政區(qū)標識、POI等；線狀地圖要素主要包括道路、水系和邊界等能夠在地圖上通過多點連線進行展示的地物或符號；面狀地圖要素一般是具有復雜形狀的地物，其形狀可近似由一個或多個多邊形的組合來展示。每個要素主類又根據(jù)地圖要素的具體功能劃分出多種子類，如圖3所示[11-14]。

圖3 地圖要素的分類Fig.3 Classification of map elements

同個區(qū)塊下的相同種類的要素數(shù)據(jù)存儲在同一個集合當中，并且通過各自的要素子類來區(qū)分具體的地圖要素類型。

在傳統(tǒng)的電子地圖數(shù)據(jù)格式中，為了提高計算的效率引入了許多復雜的抽象要素類型，從而導致要素結(jié)構(gòu)龐大，要素的信息過于分散。相比之下，本文提出的地圖要素模型結(jié)構(gòu)更為簡潔、要素間的關(guān)系更清晰，而且同類地圖要素的數(shù)據(jù)結(jié)構(gòu)上一致，集中存儲對于地圖數(shù)據(jù)的操作以及更新也更加容易。

1.3 地圖要素索引

為了在地圖數(shù)據(jù)中識別和查找不同的地圖要素，通過要素所在的區(qū)域索引、區(qū)域內(nèi)要素類的索引以及該類要素中的偏移索引來標識一個地圖要素數(shù)據(jù)[15-16]。各類型的索引功能見表1。

表1 地圖要素的索引類型及用途Tab.1 Index type and use of map elements

查找處于不同區(qū)塊的地圖要素時，先通過要素的區(qū)塊索引確定對方屬于哪一個區(qū)塊，再根據(jù)要素類索引確定要素屬于該區(qū)塊下的哪一個要素類集合中，最后根據(jù)偏移索引定位到要素類集合中的指定要素，索引過程如圖4所示。

圖4 地圖要素的索引過程Fig.4 Index process of map elements

這種采用區(qū)塊、要素類、偏移三個索引來標識一個地圖要素的方式，相對別的電子地圖要素索引方式具有更好的靈活性，使用時也更加直觀，方便上層應用進行分析和管理，提高數(shù)據(jù)操作的效率。

2 要素屬性的組織

2.1 固定屬性與可選屬性

地圖要素的屬性描述了要素附帶的不同功能的細節(jié)，隨著電子地圖功能的不斷擴展，地圖要素附帶的信息也越來越豐富，要素屬性也就越來越復雜。地圖要素屬性組織是否高效靈活，將影響電子地圖數(shù)據(jù)的質(zhì)量及功能的擴展。

傳統(tǒng)的電子地圖格式中（如SHP、TAB格式等），地圖要素數(shù)據(jù)及其附帶的屬性數(shù)據(jù)通常具有較強的耦合程度，并且在存儲上將同一要素的屬性數(shù)據(jù)集中在同一數(shù)據(jù)結(jié)構(gòu)之中。這樣的屬性數(shù)據(jù)組織方式，在地圖要素的新增時往往改動及影響較大，不利于地圖功能的擴展。

為了更好地組織要素屬性數(shù)據(jù)，根據(jù)屬性特征將其分為：固定屬性、可選屬性兩種類型進行組織。其中，固定屬性描述了地圖要素的不可缺的基本特征，其與地圖要素存儲在同一塊數(shù)據(jù)結(jié)構(gòu)上，常見的固定屬性如道路的類型、POI的名稱等?？蛇x屬性作為描述地圖要素的擴展和補充，因此不一定所有的地圖要素都擁有，并且各可選屬性集中存儲在數(shù)據(jù)結(jié)構(gòu)上與地圖要素分開，常見的可選屬性如道路的限速等?？蛇x屬性與地圖要素通過要素索引進行關(guān)聯(lián)，即每一個可選屬性集數(shù)據(jù)中都會含有各可選屬性關(guān)聯(lián)的地圖要素索引。

區(qū)分固定屬性和可選屬性的數(shù)據(jù)組織方式，一方面使得要素固定屬性的讀取和操作更為便捷；另一方面減少了可選屬性與地圖要素間的耦合程度，使得可選屬性的擴展更為方便和靈活。

2.2 可選屬性組合

在地圖要素中存在關(guān)聯(lián)關(guān)系的多個可選的屬性可以合并成一個屬性組合，組合中的屬性又分為主屬性和次要屬性兩種類型：主要屬性定義了該屬性組合描述的主要規(guī)則，可與一個或多個次要屬性進行組合，但不能與另一個主屬性同主；次要屬性定義了規(guī)則適用的條件。

這種屬性組合提供了對真實世界情況更加柔性的建模，如一個地圖道理的要素中，包含一個限速的屬性組合，該組合中主屬性為行駛速度上限值，而次要屬性為限速針對的特定車輛類型，或者限速的時間段等。

3 地圖要素與屬性的關(guān)聯(lián)

3.1 屬性映射的結(jié)構(gòu)

地圖要素的可選屬性按照其屬性類型被單獨存儲在一起，這樣的好處是可以減少數(shù)據(jù)存放的冗余，也方便針對屬性進行增量更新。由于可選數(shù)據(jù)和地圖要素不在一起，因此地圖要素和屬性需要通過屬性映射進行關(guān)聯(lián)。屬性映射中包含要素屬性值和相應的地圖要素的索引。在地圖區(qū)塊數(shù)據(jù)中，屬性類型和地圖要素類型的每個組合都必須設置獨立的屬性映射。如果一個屬性映射包含多個屬性類型，則表示該映射中含有屬性組合，如圖5所示。

圖5 單類型和多類型屬性映射Fig.5 Single and mulitple type attributes mapping

3.2 屬性映射的類型

屬性映射的類型，分為一對一映射和一對多映射兩種，一對一映射即該屬性映射中的屬性或?qū)傩越M合只屬于一個地圖要素，而一對多的映射類型可以將屬性或?qū)傩越M合引用給多個地圖要素。這樣具有相同屬性的多個地圖要素只要在對應屬性映射中添加該地圖要素的索引即可，如圖6所示。

圖6 一對多屬性映射Fig.6 One to many attributes mapping

一對多屬性映射，由于一個屬性可以映射給多個地圖要素，因此，在數(shù)據(jù)存儲空間上可以減少很大的冗余，另外，對于地圖數(shù)據(jù)的更新也將更加方便[13]。

3.3 屬性映射的快速查找

當電子地圖的應用程序通過直接解析屬性映射數(shù)據(jù)來獲取所需的地圖要素屬性時，解析過程中就會遇到其他不需要屬性類型，這樣要素屬性查找效率就會受到影響。為了提高對地圖要素指定類型的屬性查找效率，在建立屬性映射數(shù)據(jù)的同時，生成一份針對屬性映射數(shù)據(jù)的屬性類型索引列表，用來快速定位指定屬性類型的屬性映射，進而找到指定的屬性值。每一個屬性類型索引數(shù)據(jù)包含屬性類型值、屬性映射的偏移兩個部分：其中屬性類型值與該索引指向的屬性映射中的屬性類型值一致；屬性映射的偏移即該索引指向的屬性映射在屬性映射集合中的位置。屬性類型索引與屬性映射的匹配過程如圖7所示。

圖7 屬性類型索引與屬性映射的匹配Fig.7 Matching the attributes type index with attributes mapping

4 數(shù)據(jù)模型的應用實驗

實驗利用本文中提到的電子地圖數(shù)據(jù)模型，呈現(xiàn)一個簡單的電子地圖區(qū)域，并以一個具體的數(shù)據(jù)更新實例，驗證該數(shù)據(jù)模型增量更新的效果。

需要呈現(xiàn)的地圖區(qū)域包含高低兩個層次，其中高層次包含4個區(qū)塊，低層次則對應的有16個區(qū)塊。該地圖區(qū)域包含的地圖要素見表2。

表2 實驗中包含的地圖要素Tab.2 Map elements in the experiment

實驗中對地圖數(shù)據(jù)讀取和操作流程主要有以下幾個步驟：

1）讀取地圖顯示范圍所在的區(qū)塊數(shù)據(jù)；

2）按照地圖要素分類解析要素集合；

3）解析地圖要素的可選屬性集合；

4）解析具體地圖要素的固定屬性；

5）查找并解析具體地圖要素的可選屬性；

6）通過可選屬性識別各地圖要素的關(guān)聯(lián)關(guān)系及具體功能；

7）根據(jù)顯示順序?qū)⒔馕鐾瓿傻牡貓D要素進行繪制。

地圖的呈現(xiàn)利用Open GL在PC上進行地圖符號的繪制，其呈現(xiàn)效果如圖8所示。

圖8 應用實驗的地圖呈現(xiàn)效果Fig.8 Map rendering experiment

圖8 中，左邊的效果圖為該實驗的高層次地圖數(shù)據(jù)，并且將其包含的4個區(qū)塊邊界用紅線標識，可見各區(qū)塊彼此之間沒有重疊，且各地圖要素按照區(qū)塊劃分；右邊的效果圖為對應左圖中第一個區(qū)塊使用低層次地圖數(shù)據(jù)時的呈現(xiàn)，其又被劃分為更小的4個區(qū)塊，且相比高層次地圖數(shù)據(jù)，其數(shù)據(jù)內(nèi)容更加豐富多樣，呈現(xiàn)的效果也更加詳細。

實驗通過新增一條道路數(shù)據(jù)來驗證電子地圖的增量更新效果，具體情況如圖9所示。

圖9 電子地圖增量更新前Fig.9 Before the electronic map updated

新增的道路數(shù)據(jù)涉及圖9示意的區(qū)塊3，因此，更新操作將針對區(qū)塊3中道路類數(shù)據(jù)集合及其相關(guān)屬性集合進行，更新后的地圖數(shù)據(jù)變更如圖10所示。

圖10 電子地圖增量更新后Fig.10 After the electronic map updated

由此可見，本文提出的電子地圖數(shù)據(jù)模型在進行增量更新操作時，只要編輯增量數(shù)據(jù)所屬的區(qū)塊中的特點要素類集合或?qū)傩约舷嚓P(guān)記錄即可，如果在實際應用中地圖數(shù)據(jù)使用類似SQLite等數(shù)據(jù)庫進行存儲，則具體的更新操作表現(xiàn)在對發(fā)生更新的數(shù)據(jù)庫表中的一行進行新增或替換操作，其優(yōu)勢將更為明顯高效。增量更新前后地圖呈現(xiàn)的效果如圖11所示。

圖11 電子地圖增量更新呈現(xiàn)效果Fig.11 Incremental updating experiment of electronic map

5 結(jié)束語

隨著各種電子地圖的位置服務應用需求的不斷增加，空間地理數(shù)據(jù)的內(nèi)容也越來越豐富、復雜，對電子地圖數(shù)據(jù)的組織效率、合理性、擴展性的要求也越來越高。在這種應用背景下，本文提出了一種高效、易于操作和擴展的地圖數(shù)據(jù)組織模型：通過對電子地圖進行多層級的區(qū)塊劃分、地圖要素分類管理存儲以及建立統(tǒng)一的索引機制，提高了地圖數(shù)據(jù)的讀取和查找效率；將地圖要素屬性分為固定和可選兩種性質(zhì)類型區(qū)分管理，可選屬性又能通過組合的方式關(guān)聯(lián)一個或多個地圖要素，這種要素屬性的組織方式提高了地圖數(shù)據(jù)的利用率和擴展性，減少了數(shù)據(jù)冗余程度；采用屬性映射作為地圖要素與要素屬性的索引媒介，使得兩者的關(guān)聯(lián)更加方便。