【文章內(nèi)容簡(jiǎn)介】 整體多邊形結(jié)構(gòu)、對(duì)偶獨(dú)立地圖編碼結(jié)構(gòu)及 ARCNODE 結(jié)構(gòu)。②柵格結(jié)構(gòu)該結(jié)構(gòu)用點(diǎn)的像素表示空間對(duì)象。其優(yōu)點(diǎn)是結(jié)構(gòu)簡(jiǎn)單、顯示速度快。缺點(diǎn)是精度較差、網(wǎng)絡(luò)拓?fù)浣⒗щy。根據(jù)像素的存貯結(jié)構(gòu)及空間單元不同，具體又分為柵格編碼結(jié)構(gòu)、嵌套結(jié)構(gòu)、不規(guī)則結(jié)構(gòu)等多種形式。③矢量柵格一體化結(jié)構(gòu)該結(jié)構(gòu)綜合了兩種結(jié)構(gòu)的優(yōu)點(diǎn)，在許多電子地圖中得到了應(yīng)用。（2）屬性數(shù)據(jù)的數(shù)據(jù)模型目前，屬性數(shù)據(jù)采用的模型有層次模型、網(wǎng)狀模型和關(guān)系模型。①層次模型該模型的基本結(jié)構(gòu)是樹(shù)形結(jié)構(gòu)。層次模型數(shù)據(jù)庫(kù)系統(tǒng)是數(shù)據(jù)庫(kù)領(lǐng)域發(fā)展最早的一種，目前已基本不用，但其在數(shù)據(jù)庫(kù)發(fā)展歷史上有著重大的作用和影響，以后的模型均受其影響。②網(wǎng)狀模型網(wǎng)狀模型明顯優(yōu)于層次模型，數(shù)據(jù)顯示和數(shù)據(jù)操作方法均呈現(xiàn)高效、成熟的特點(diǎn)，但是，網(wǎng)狀模型不足之處在于使用時(shí)涉及系統(tǒng)內(nèi)部因素較多，用戶(hù)操作使用不方便，數(shù)據(jù)模式與系統(tǒng)實(shí)現(xiàn)也甚不理想。GPS 車(chē)載導(dǎo)航儀的路徑規(guī)劃研究10③關(guān)系模型關(guān)系模型是完全不同于前兩種模型的一種新的模型，前兩種模型一般被稱(chēng)為格式化模型，而關(guān)系模型一般稱(chēng)為非格式化模型，其基本結(jié)構(gòu)是二維表，簡(jiǎn)稱(chēng)表（table） 。二維表由表框架和元組組成，表框架由 n 個(gè)屬性（或稱(chēng)為列）組成，而存放于框架內(nèi)的每行數(shù)據(jù)稱(chēng)為元組（或稱(chēng)為行） ，因此，一張二維表是由一個(gè)n 元屬性的框架及 m 個(gè)元組組成。關(guān)系模型中的操作是建立在二維表上的操作，包括對(duì)一張表及多張表間的查詢(xún)、刪除、插入及修改等操作。面向?qū)ο蟮恼w數(shù)據(jù)模型是將面向?qū)ο螅╫bject oriented）思想和面向?qū)ο蟮姆治鲈O(shè)計(jì)方法應(yīng)用到空間數(shù)據(jù)模型的設(shè)計(jì)中，將各種空間實(shí)體抽象為某一類(lèi)具有公共屬性的對(duì)象，如點(diǎn)、線、面等對(duì)象，每個(gè)具體的地理實(shí)體是該對(duì)象的一個(gè)實(shí)例，具有自己的屬性，各種對(duì)象分層管理，實(shí)現(xiàn)空間數(shù)據(jù)與屬性數(shù)據(jù)的統(tǒng)一管理。面向?qū)ο蟮恼w數(shù)據(jù)模型強(qiáng)調(diào)的是整體與面向?qū)ο蟮母拍?。它不僅將地理世界以實(shí)體為單位進(jìn)行組織，而且將客觀世界作為一個(gè)整體看待，即每個(gè)實(shí)體不僅自身具有空間特性和屬性特性的聯(lián)系，更重要的是它與其它實(shí)體之間同時(shí)還具有邏輯上的語(yǔ)義聯(lián)系，此外，它也具有時(shí)間屬性。面向?qū)ο蟮姆椒閿?shù)據(jù)模型的建立提供了四種數(shù)據(jù)抽象技術(shù)（分類(lèi)、概括、聯(lián)合、聚集）和兩種數(shù)據(jù)抽象工具（繼承和傳播） ，利用這些技術(shù)所構(gòu)造的數(shù)據(jù)模型要比傳統(tǒng)的數(shù)據(jù)模型豐富的多，更適用于定義復(fù)雜的地理實(shí)體和對(duì)復(fù)雜對(duì)象的直接操作。因此，面向?qū)ο蟮恼w數(shù)據(jù)模型是一種有效的空間數(shù)據(jù)模型。面向?qū)ο蟮姆椒槊枋鰪?fù)雜的空間信息提供了一種直觀有效的方法。與傳統(tǒng)的導(dǎo)航電子地圖數(shù)據(jù)模型相比，面向?qū)ο蟮臄?shù)據(jù)模型具有的優(yōu)點(diǎn)是：結(jié)構(gòu)清晰、組織有序，所有空間實(shí)體都以對(duì)象的形式封裝；可以定義和處理復(fù)雜的空間實(shí)體；易于擴(kuò)充和二次開(kāi)發(fā)；面向?qū)ο蟮挠脩?hù)界面更便于用戶(hù)操作和使用。 導(dǎo)航電子地圖數(shù)據(jù)庫(kù)的設(shè)計(jì)原則在智能車(chē)輛導(dǎo)航系統(tǒng)中，導(dǎo)航電子地圖工作于實(shí)時(shí)、多任務(wù)的環(huán)境，圖形的顯示、刷新、信息查詢(xún)、拓?fù)潢P(guān)系等是數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)必須考慮的重要因素。一般設(shè)計(jì)導(dǎo)航電子地圖數(shù)據(jù)庫(kù)應(yīng)遵循以下原則：第三章 路徑規(guī)劃的分析及設(shè)計(jì) 11①圖形結(jié)構(gòu)簡(jiǎn)單。由于導(dǎo)航電子地圖主要包含點(diǎn)、線、面等空間對(duì)象，簡(jiǎn)單的圖形結(jié)構(gòu)具有數(shù)據(jù)量少、刷新快、圖形剪裁方便等特點(diǎn)。②冗余度小。小的地圖數(shù)據(jù)冗余度將使地圖信息查詢(xún)、路徑搜索的速度都得以提高，同時(shí)降低數(shù)據(jù)的儲(chǔ)存空間。③拓?fù)潢P(guān)系簡(jiǎn)單。簡(jiǎn)單明了的拓?fù)潢P(guān)系將縮短最優(yōu)路徑規(guī)劃及地圖匹配時(shí)間。④空間信息查詢(xún)速度快。好的數(shù)據(jù)結(jié)構(gòu)將提高空間信息的查詢(xún)速度。⑤數(shù)據(jù)接口開(kāi)放。電子地圖中的非空間數(shù)據(jù)具有良好的數(shù)據(jù)接口，能夠兼容商用的非空間數(shù)據(jù)庫(kù)。 導(dǎo)航電子地圖數(shù)據(jù)庫(kù)的結(jié)構(gòu)設(shè)計(jì)與實(shí)現(xiàn)導(dǎo)航電子地圖數(shù)據(jù)庫(kù)是整個(gè)系統(tǒng)的基石，系統(tǒng)中幾乎所有的模塊都直接或間接的與其相關(guān)，其結(jié)構(gòu)設(shè)計(jì)的好壞將直接影響整個(gè)系統(tǒng)的最終性能。綜合考慮各方面因素，采用三層結(jié)構(gòu)模式，以便充分利用面向?qū)ο蟪绦蛟O(shè)計(jì)方法的特性，使各層之間保持低耦合、高內(nèi)聚的特點(diǎn)，層與層之間以通過(guò)的接口方式保持通訊，其層次結(jié)構(gòu)如圖 所示?？臻g對(duì)象 屬性數(shù)據(jù)對(duì)象訪問(wèn) 索引操作 屬性操作二進(jìn)制文件讀寫(xiě)模塊其他文件DBF 文件OBJ文件IDX文件圖 導(dǎo)航電子地圖數(shù)據(jù)庫(kù)的層次結(jié)構(gòu)第一層為接口層，包括空間對(duì)象與屬性結(jié)構(gòu)。該層為設(shè)計(jì)的數(shù)據(jù)庫(kù)進(jìn)行二次開(kāi)發(fā)提供了一系列的接口。應(yīng)用軟件設(shè)計(jì)人員可以調(diào)用該結(jié)構(gòu)訪問(wèn)數(shù)字地圖文件，接口層核心層讀寫(xiě)層GPS 車(chē)載導(dǎo)航儀的路徑規(guī)劃研究12并對(duì)地圖對(duì)象和屬性數(shù)據(jù)進(jìn)行操作，例如屬性數(shù)據(jù)的查詢(xún)等。第二層為核心層，是實(shí)現(xiàn)整個(gè)數(shù)據(jù)庫(kù)的關(guān)鍵部分，涉及到得數(shù)據(jù)結(jié)構(gòu)和算法在這部分實(shí)現(xiàn)。第三層為讀寫(xiě)層，完成對(duì)二進(jìn)制文件底層讀寫(xiě)操作。系統(tǒng)的其他部分不能對(duì)數(shù)據(jù)庫(kù)文件直接進(jìn)行操作。讀寫(xiě)層抽象了對(duì)文件進(jìn)行操作的特性，封裝了對(duì)磁盤(pán)鏈的管理和讀寫(xiě)操作等。圖 給出了導(dǎo)航電子地圖數(shù)據(jù)庫(kù)實(shí)現(xiàn)流程，整個(gè)過(guò)程可以分為文件層、用戶(hù)層和接口層三部分?？臻g對(duì)象/索引對(duì)象/ 屬性對(duì)象空間數(shù)據(jù)人機(jī)接口界面（地圖顯示、信息查詢(xún)、路徑規(guī)劃及地圖匹配等功）屬性數(shù)據(jù)地圖數(shù)據(jù)庫(kù)文件讀寫(xiě)導(dǎo)航電子地圖數(shù)據(jù)庫(kù)文件（ 、.IDX、.DBF 文件）接口層用戶(hù)層文件層 圖 導(dǎo)航電子地圖數(shù)據(jù)庫(kù)實(shí)現(xiàn)流程 導(dǎo)航電子地圖中道路網(wǎng)絡(luò)的拓?fù)渖煞椒?導(dǎo)航電子地圖中道路網(wǎng)絡(luò)的模型與儲(chǔ)存道路網(wǎng)絡(luò)的數(shù)據(jù)模型，是指導(dǎo)航電子地圖道路網(wǎng)絡(luò)用來(lái)組織其數(shù)據(jù)所采用的格式轉(zhuǎn)換及拓?fù)渖蓴?shù)據(jù)格式分析/關(guān)鍵數(shù)據(jù)解析外部地圖數(shù)據(jù)源第三章 路徑規(guī)劃的分析及設(shè)計(jì) 13模型，它是生成具有拓?fù)浣Y(jié)構(gòu)道路網(wǎng)絡(luò)的基礎(chǔ)。目前，有關(guān)道路網(wǎng)絡(luò)的數(shù)據(jù)模型用的較多有基于路段連接和基于 ArcNode（弧節(jié)點(diǎn)法）等若干種。本文采用ArcNode 結(jié)構(gòu)，其主要特點(diǎn)是，容易表達(dá)實(shí)際路網(wǎng)的拓?fù)潢P(guān)系，且形式簡(jiǎn)潔。ArcNode 模型的基本原理是，將顯示中的真實(shí)道路用一系列折線段來(lái)模擬和近似，即在一定精度的允許范圍內(nèi)，采用以直代曲的思想，用分段連續(xù)的小段直線段所組成的折線段來(lái)代替和逼近真實(shí)的道路曲線，將其中小段的直線段稱(chēng)作Arc，Arc 的端點(diǎn)稱(chēng)為 Node,這樣，整個(gè)道路網(wǎng)絡(luò)將由 Arc 和 Node 組成，其形式化定義為Rw = (N,R)N = {x|x∈Ns}R = {NR}NR = {＜x,y＞|L(x,y)...(x,y∈N)}式中：Rw ——道路網(wǎng)絡(luò)； Ns ——道路網(wǎng)絡(luò)的節(jié)點(diǎn)集； NR——道路網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)間拓?fù)潢P(guān)系的集合； ＜x,y＞——節(jié)點(diǎn) x 和 y 之間存在的一條弧； L(x,y) ——節(jié)點(diǎn) x 和 y 之間的權(quán)值，節(jié)點(diǎn)和節(jié)點(diǎn)之間連接的權(quán)值可以用節(jié)點(diǎn)之間的集合長(zhǎng)度或者其他費(fèi)用來(lái)表示。 根據(jù)實(shí)際交通網(wǎng)絡(luò)的特點(diǎn)，我們作如下分析假設(shè)： ①所有的編制都是直線。對(duì)于彎曲弧度較大的路段，可以通過(guò)在該路段上插入一系列節(jié)點(diǎn)使該路段由一些弧度較小的路段構(gòu)成，弧度較小的路段可以認(rèn)為是一條邊。如圖 ，節(jié)點(diǎn) 2 之間路段的弧度較大，在路段上加入節(jié)點(diǎn) 2，把原來(lái)的路段分成兩個(gè)弧度相對(duì)較小的路段。 ②邊通常是雙向可通的，邊的權(quán)值為正值。 ③網(wǎng)絡(luò)中有較多的節(jié)點(diǎn)和邊。 ④和節(jié)點(diǎn)相關(guān)聯(lián)的邊數(shù)為常數(shù)，且遠(yuǎn)小于網(wǎng)絡(luò)中總的節(jié)點(diǎn)數(shù)。GPS 車(chē)載導(dǎo)航儀的路徑規(guī)劃研究14節(jié)點(diǎn) 3節(jié)點(diǎn) 2節(jié)點(diǎn) 1圖 弧度較大的路段處理計(jì)算機(jī)存儲(chǔ)的是矢量化的道路網(wǎng)絡(luò)，網(wǎng)絡(luò)的存儲(chǔ)結(jié)構(gòu)是影響路徑規(guī)劃算法搜索速度和事件復(fù)雜度的一個(gè)重要因素。一個(gè)簡(jiǎn)單直觀的存儲(chǔ)方法是對(duì)道路網(wǎng)絡(luò)圖中的每一個(gè)節(jié)點(diǎn)進(jìn)行編號(hào)，采用鄰接表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在鄰接表中，對(duì)圖的每個(gè)節(jié)點(diǎn)建立一個(gè)單鏈表，每個(gè)單鏈表都由表節(jié)點(diǎn)和表頭節(jié)點(diǎn)構(gòu)成。第 i 個(gè)單鏈表的 w 個(gè)表節(jié)點(diǎn)分別對(duì)應(yīng)著和圖中第 i 個(gè)節(jié)點(diǎn)相關(guān)聯(lián)的 w 條邊。鏈表的表頭節(jié)點(diǎn)以順序結(jié)構(gòu)形式存儲(chǔ)，以便隨機(jī)訪問(wèn)圖中任一節(jié)點(diǎn)的單鏈表。因此，采用鄰接表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，很容易找到和圖中任一節(jié)點(diǎn)相關(guān)聯(lián)的邊。單鏈表的表頭節(jié)點(diǎn)和表節(jié)點(diǎn)的結(jié)構(gòu)如圖 所示，圖中，Name：節(jié)點(diǎn)編號(hào)；Position：節(jié)點(diǎn)位置坐標(biāo)；First：指向鏈表中的第一個(gè)表節(jié)點(diǎn)；Next：指向鏈表中的下一個(gè)表節(jié)點(diǎn)；Weight：邊的權(quán)值。 折線道路網(wǎng)絡(luò)的拓?fù)渖煞ㄕ劬€道路網(wǎng)絡(luò)組成的最大特點(diǎn)是，每一條道路都是由帶有寬度值的折線段（簡(jiǎn)稱(chēng)道路中心線）表示。有時(shí)，為了數(shù)據(jù)獲取方便，也可能以近似的道路中心線來(lái)表示。各種來(lái)源提供的實(shí)際數(shù)據(jù)使得折線道路網(wǎng)絡(luò)中可能存在以下情況：①線段間的虛交特性，即兩條實(shí)際相交的路段，在給定的道路網(wǎng)絡(luò)數(shù)據(jù)中卻Name NamePosition First NextWeightPosition圖 鏈表結(jié)構(gòu)表節(jié)點(diǎn)表頭節(jié)點(diǎn)第三章 路徑規(guī)劃的分析及設(shè)計(jì) 15不存在與交點(diǎn)對(duì)應(yīng)的節(jié)點(diǎn)。如圖 （a）所示，路段 AB 與路段 CD 實(shí)際應(yīng)相交于節(jié)點(diǎn) O，而節(jié)點(diǎn) O 并未出現(xiàn)在路段 AB 與路段 CD 的給定數(shù)據(jù)中。②線段間的虛段特性，即兩條實(shí)際相交的路段，因其中一條路段偏短導(dǎo)致沒(méi)能相交。如圖 （b）所示，路段 AB 與路段 CD 實(shí)際應(yīng)相交于節(jié)點(diǎn) B，而節(jié)點(diǎn) B并未出現(xiàn)在路段 CD 的給定數(shù)據(jù)中，將節(jié)點(diǎn) B 稱(chēng)為虛斷點(diǎn)。③線段間的過(guò)交特性，即兩條相交的路段，因其中一條路段偏長(zhǎng)而導(dǎo)致過(guò)短的毛刺路段出現(xiàn)。如圖 （c）所示，路段 AB 與路段 CD 相交于節(jié)點(diǎn) O，過(guò)短路段 BO 應(yīng)該不存在，然而，節(jié)點(diǎn) B 卻出現(xiàn)在路段 AB 給定數(shù)據(jù)中，將節(jié)點(diǎn) B 稱(chēng)為過(guò)交點(diǎn)。④節(jié)點(diǎn)的冗余特性，一種情況是，實(shí)際應(yīng)該是同一節(jié)點(diǎn)的點(diǎn)卻存在多個(gè)相鄰的節(jié)點(diǎn)。如圖 （d）所示，節(jié)點(diǎn) A、B、C、D 實(shí)際表示的地圖中的同一點(diǎn)，換言之，此時(shí)應(yīng)該只用一個(gè)節(jié)點(diǎn)來(lái)表示地圖中的該點(diǎn)，然而，給定的道路網(wǎng)絡(luò)數(shù)據(jù)中卻存在節(jié)點(diǎn) A、B、C、D；另一種情況是，本來(lái)可以由兩個(gè)節(jié)點(diǎn)表示的路段，給定的道路網(wǎng)絡(luò)數(shù)據(jù)中卻存在其他節(jié)點(diǎn)，如圖 （e）所示，路段 AB 只需節(jié)點(diǎn) A和 B 便能在精度允許范圍內(nèi)準(zhǔn)確表示，而實(shí)際數(shù)據(jù)中卻包括節(jié)點(diǎn) C 和 D。 算法的原理可以簡(jiǎn)單的描述為：依據(jù)折線道路網(wǎng)絡(luò)的組成特點(diǎn)及 ArcNode數(shù)據(jù)模型，由給定的折線道路網(wǎng)絡(luò)數(shù)據(jù)生成表示其拓?fù)浣Y(jié)構(gòu)的 ArcNode 數(shù)據(jù)結(jié)構(gòu)。具體生成過(guò)稱(chēng)分為兩步：第一步是完善給定的折線道路網(wǎng)絡(luò)數(shù)據(jù)，即對(duì)前面介紹的道路網(wǎng)絡(luò)的幾種特(a)線段間的虛交特性(d)表示同一點(diǎn)的多個(gè)節(jié)點(diǎn) (e)可以壓縮掉的中間節(jié)點(diǎn)(b)線段間的虛斷特性(c)線段間的過(guò)交特性 (c)線 段 間 的 過(guò) 交 特 性 DOACB CDABAOBC D圖 實(shí)際數(shù)據(jù)中折線道路網(wǎng)絡(luò)的情況ACDBADBCGPS 車(chē)載導(dǎo)航儀的路徑規(guī)劃研究16性進(jìn)行相應(yīng)的處理。具體的處理方法是：虛交時(shí)，將實(shí)際應(yīng)該有的交點(diǎn)分別插入兩條路段中，從而兩條路段分裂成四條路段，如圖 （a）中，應(yīng)將節(jié)點(diǎn) O 分別插入路段 AB 和路段 CD 中，從而使路段 AB 與路段 CD 分裂成路段 AO、OB、CO 和OD；虛斷時(shí)，應(yīng)以偏短路段延長(zhǎng)線與另一路段的交點(diǎn)代替偏短路段中靠近該交點(diǎn)節(jié)點(diǎn)，如圖 （b）中，應(yīng)將路段 AB 的節(jié)點(diǎn) B 用路段 AB 的延長(zhǎng)線與路段 CD 之交點(diǎn)來(lái)代替；過(guò)交時(shí)，應(yīng)該刪除過(guò)短路段，如圖 （c）中，應(yīng)將路段 OB 刪除，即將節(jié)點(diǎn) B 從路段 AB 中刪除；節(jié)點(diǎn)冗余時(shí)，如果是第一種情況，應(yīng)以冗余節(jié)點(diǎn)的中心點(diǎn)代替這些冗余點(diǎn)；如果是第二種情況，則應(yīng)將所有的冗余節(jié)點(diǎn)刪除，如圖 （d）中，應(yīng)將 A、B、C、D 用它們的中心點(diǎn)來(lái)代替，該中心點(diǎn)的縱橫坐標(biāo)分別為這些冗余節(jié)點(diǎn)縱橫坐標(biāo)的均值，如圖 （e）中，應(yīng)將路段 AB 中的節(jié)點(diǎn)C 和 D 刪除而只保留節(jié)點(diǎn) A 和 B。第二步是在第一步的基礎(chǔ)上，由完善以后的折線道路網(wǎng)絡(luò)數(shù)據(jù)生成表示其拓?fù)浣Y(jié)構(gòu)的 ArcNode 數(shù)據(jù)結(jié)構(gòu)，ArcNode 數(shù)據(jù)結(jié)構(gòu)采用鄰接表結(jié)構(gòu)。 路徑規(guī)劃的分析及設(shè)計(jì) 路徑規(guī)劃是現(xiàn)代智能車(chē)輛導(dǎo)航的一項(xiàng)關(guān)鍵技術(shù)，是基于具有拓?fù)浣Y(jié)構(gòu)的道路網(wǎng)絡(luò)，在車(chē)輛行駛前或行駛過(guò)程中尋找出發(fā)點(diǎn)到目標(biāo)點(diǎn)最優(yōu)行車(chē)路線的過(guò)稱(chēng)。本節(jié)充分挖掘?qū)嶋H道路網(wǎng)絡(luò)具有的各種特性，分別利用道路網(wǎng)絡(luò)空間分布特性和道路等級(jí)特性，設(shè)計(jì)了兩種針對(duì)道路網(wǎng)絡(luò)的啟發(fā)式搜索策略，即方向搜索策略和