樊 浩，徐明偉

(1安徽廣播電視大學(xué)，合肥 230022； 2合肥濱湖職業(yè)技術(shù)學(xué)院，合肥 230601)

0 引言

隨著IT技術(shù)的飛速發(fā)展，高校校園作為產(chǎn)學(xué)研的前沿基地，校園管理的信息化和數(shù)字化將成為校園建設(shè)發(fā)展的必然趨勢(shì)。目前國(guó)內(nèi)上千所高職院校的校園規(guī)模越來(lái)越大，但校園軟體建設(shè)發(fā)展相對(duì)緩慢，校園信息平臺(tái)仍采用傳統(tǒng)的C/S模式，校園信息管理仍多以人工為主[1]，這使得構(gòu)建一個(gè)智能的電子校園導(dǎo)航平臺(tái)顯得非常必要和迫切。

智能校園導(dǎo)航平臺(tái)能輔助獲取到最新的校園環(huán)境信息、實(shí)體建筑信息、地上線路圖、地下電網(wǎng)圖等。通過(guò)智能選擇目的地和源地址，可以輔助快速選擇最佳的導(dǎo)航路徑，并且以三維圖的形式展示給用戶[2]。同時(shí)可以便捷地采集校園信息，尤其是環(huán)境信息，便于校園信息管理和相關(guān)校園建設(shè)的輔助決策[3]。

本文基于導(dǎo)航技術(shù)及WebGIS(萬(wàn)維網(wǎng)地理信息系統(tǒng))技術(shù)構(gòu)建校園導(dǎo)航平臺(tái)，以實(shí)現(xiàn)校園建設(shè)的信息化、數(shù)字化、智能化。該平臺(tái)以WebGIS和SuperMap iObjects組件為技術(shù)架構(gòu)，將SuperMap iObjects技術(shù)與OLE(對(duì)象連接嵌入)和SDE(空間數(shù)據(jù)引擎)結(jié)合，通過(guò)組件的方式提供服務(wù)，實(shí)現(xiàn)B/S技術(shù)架構(gòu)，不需要下載客戶端，支持終端用戶在瀏覽器上使用該導(dǎo)航平臺(tái)。此外，對(duì)SuperMap iObjects組件技術(shù)進(jìn)行優(yōu)化封裝，以提升平臺(tái)空間的數(shù)據(jù)處理能力。同時(shí)對(duì)Dijkstra算法從搜索方式和地理信息存儲(chǔ)方式兩個(gè)方面進(jìn)行優(yōu)化。

通過(guò)該平臺(tái)可以實(shí)現(xiàn)：1)終端用戶可以在平臺(tái)上對(duì)地圖物體進(jìn)行任意縮放及漫游控制，對(duì)于選取的區(qū)域進(jìn)行三維全仿真展示；2)進(jìn)行信息的采集、查詢、檢索，并與校園其他系統(tǒng)集成，同時(shí)能夠在同一維度查閱相關(guān)信息；3)納入高校人員信息，輔助管理者進(jìn)行人員信息管理等。

1 技術(shù)架構(gòu)

1.1 技術(shù)框架

傳統(tǒng)技術(shù)中被采用的地理數(shù)據(jù)系統(tǒng)采用的為地理信息元數(shù)據(jù)，主要描述地理數(shù)據(jù)的內(nèi)容、質(zhì)量、狀態(tài)及相關(guān)特征，一般適用于專業(yè)領(lǐng)域[4]。本系統(tǒng)基于WebGIS技術(shù)，通過(guò)GIS系統(tǒng)采集多源的空間地理數(shù)據(jù)，由專業(yè)系統(tǒng)對(duì)封裝數(shù)據(jù)進(jìn)行預(yù)處理、分析、轉(zhuǎn)化等，向終端用戶提供地理數(shù)據(jù)服務(wù)。

傳統(tǒng)的互聯(lián)網(wǎng)系統(tǒng)中一般采用C/S模式，由于C/C++/.NET/DEPHI等開發(fā)語(yǔ)言同時(shí)適應(yīng)于客戶端和服務(wù)端，且之前的應(yīng)用體量小，所以C/S優(yōu)勢(shì)明顯[5]。但隨著IT技術(shù)的發(fā)展及用戶體量的迅猛增加，使C/S維護(hù)成本高、開發(fā)成本高、不靈活等弊端逐步顯現(xiàn)。隨著Web 2.0的廣泛使用以及前后端開發(fā)語(yǔ)言的發(fā)展，B/S成為中小型平臺(tái)的常用解決方案[6]。本文所述平臺(tái)采用B/S開發(fā)模式，利用WebGIS技術(shù)和組件技術(shù)構(gòu)成服務(wù)端框架，通過(guò)互聯(lián)網(wǎng)提供地理信息服務(wù)。

本平臺(tái)在服務(wù)端結(jié)合SuperMap iObjects組件，將WebGIS核心技術(shù)封裝在自定義iObjects組件中，對(duì)外提供地理數(shù)據(jù)采集、預(yù)處理、處理、數(shù)據(jù)轉(zhuǎn)換、分析及統(tǒng)計(jì)服務(wù)等。

1.2 技術(shù)分析及優(yōu)化

本文涉及的主要技術(shù)包括B/S模式、WebGIS技術(shù)、導(dǎo)航技術(shù)、SuperMap iObjects組件技術(shù)。

B/S模式以Web服務(wù)器為核心，用戶通過(guò)萬(wàn)維網(wǎng)服務(wù)工具，一般采用瀏覽器訪問(wèn)Web服務(wù)器，服務(wù)請(qǐng)求和響應(yīng)都在網(wǎng)頁(yè)上完成。

WebGIS技術(shù)是GIS在Web框架下的應(yīng)用，GIS地理信息系統(tǒng)專門負(fù)責(zé)對(duì)多源多方式的地理空間數(shù)據(jù)進(jìn)行采集，并利用專門組件模塊完成數(shù)據(jù)清洗，包括數(shù)據(jù)類型轉(zhuǎn)換、數(shù)據(jù)結(jié)構(gòu)映射、數(shù)據(jù)存儲(chǔ)等[7]。然后，利用GIS核心模塊，對(duì)數(shù)據(jù)進(jìn)行處理，并且展示到Web客戶端。此外，還可結(jié)合海量的地理數(shù)據(jù)信息，對(duì)相關(guān)數(shù)據(jù)的應(yīng)用部門提供數(shù)據(jù)分析和統(tǒng)計(jì)服務(wù)。

在網(wǎng)絡(luò)應(yīng)用開發(fā)技術(shù)中傳統(tǒng)的是采用CGI通用網(wǎng)關(guān)接口，隨著用戶體量變大且應(yīng)用越來(lái)越復(fù)雜，CGI腳本編寫也越來(lái)越復(fù)雜，嚴(yán)重制約著應(yīng)用的發(fā)展，且CGI每次升級(jí)都需要重啟，對(duì)應(yīng)用直接產(chǎn)生影響[8]。插件Plug-in技術(shù)成為CGI技術(shù)的擴(kuò)充，通過(guò)動(dòng)態(tài)鏈接庫(kù)加載，節(jié)省內(nèi)存，提升訪問(wèn)效率。本文采用SuperMap iObjects組件構(gòu)建GIS系統(tǒng)，每個(gè)GIS模塊通過(guò)組件對(duì)外提供服務(wù)，組件的方式靈活、易擴(kuò)展，組件技術(shù)完美契合B/S模式架構(gòu)[9]。

SuperMap iObjects技術(shù)是基于三維一體化、高性能、跨平臺(tái)的大型組件式GIS開發(fā)平臺(tái)，功能完備、開發(fā)便捷，易于構(gòu)建通用GIS平臺(tái)以及基于地理空間信息的行業(yè)應(yīng)用系統(tǒng)[10]。SuperMap iObjects技術(shù)采用面向?qū)ο蟮募軜?gòu)，提供應(yīng)用程序之間的對(duì)象訪問(wèn)，其功能不受限于平臺(tái)和操作系統(tǒng)，可大大提高軟件開發(fā)效率和利用效率[11]。

iObjects組件按照?qǐng)D層的方式組織整個(gè)物理空間，不同圖層代表不同的物理屬性，譬如建筑物為一個(gè)圖層，道路為一個(gè)圖層等等。這里圖層為矢量圖層，基于坐標(biāo)數(shù)據(jù)，用于展示物理特性，如圖1所示。

圖1 Web結(jié)構(gòu)示意圖

本文重點(diǎn)研究iObjects組件功能實(shí)現(xiàn)和導(dǎo)航技術(shù)最短路徑的問(wèn)題。其中iObjects組件通過(guò)對(duì)外提供服務(wù)實(shí)現(xiàn)WebGIS系統(tǒng)的圖像處理功能。采用SupperMap iOBjects組件來(lái)實(shí)現(xiàn)WebGIS技術(shù)，通過(guò)封裝已有的接口及方法實(shí)現(xiàn)圖像處理、二維路徑計(jì)算、數(shù)據(jù)搜索、數(shù)據(jù)緩存、路徑對(duì)比、數(shù)據(jù)緩存等功能。通過(guò)SuperMap iObjects Java實(shí)現(xiàn)地圖預(yù)處理及地圖匹配。

關(guān)鍵控件/接口包括Workspace類和MapControl類、MapMatchParameter類、PathAnalyst類、SSCDataEnvironment類和GPSData類。

核心算法包括MapMatchParameter.setTime()方法、SSCDataEnvironment.connectData()方法，以及用于路徑分析和計(jì)算的PathAnalyst.setSSCEnvironment()方法、PathAnalyst.mapMatch()方法。

地形邊緣平滑處理功能主要解決不同分辨率地形疊加邊緣處斷崖問(wèn)題。關(guān)鍵控件和接口主要包括：Workspace類、Datasource類、DatasetGrid類和ConversionAnalystParameter類、Recordset類、DissolveParameter類和Generalization類；方法包括Generalization.dissolve()方法、Recordset.getGeometry()方法、RasterClip.clip()方法、BufferAnalyst.createBuffer()方法、VectorClip.clipDatasetVector()方法和ConversionAnalyst.rasterToVector()方法。

2 Dijkstra算法

導(dǎo)航技術(shù)基于數(shù)學(xué)圖論理論獲取最短路徑，將地圖中的道路和建筑等抽象為點(diǎn)與點(diǎn)的關(guān)系，即網(wǎng)格關(guān)系，通過(guò)研究點(diǎn)與點(diǎn)之間的關(guān)系，計(jì)算出最優(yōu)解，進(jìn)而得到最優(yōu)的路徑。

在研究導(dǎo)航Dijkstra算法的優(yōu)化之前，有必要先介紹一下涉及到的概率圖、圖論、網(wǎng)格及最小路徑問(wèn)題。

圖論中的圖是指所參照的事物之間的相互關(guān)系，如果以點(diǎn)表示具體事物，事物與事物之間的關(guān)系以線表示，則地圖上所有點(diǎn)及點(diǎn)之間聯(lián)系的集合，即為將研究的圖。以G表示圖，通常為一個(gè)有序二元組{V，E}，即G=(V，E)，其中V={v_1，v_2，…，v_n}為有序非空集合，V中元素稱之為頂點(diǎn)，而V稱之為G的頂點(diǎn)集合。E為V中不同元素之間的非有序?qū)ε?即為(v_i，v_j)其中v_i≠v_j，這些非有序?qū)ε挤Q之為邊，而E稱之為G的邊集。網(wǎng)格為在圖的基礎(chǔ)上在每條邊上加上權(quán)值，即為w_i，權(quán)重可以表示價(jià)格、流量或者時(shí)間等，網(wǎng)格不僅僅可以體現(xiàn)幾何中的事物，也可將實(shí)體事物抽象為網(wǎng)格，網(wǎng)格被表示為N=(V，A，W)，由G圖及其權(quán)重構(gòu)成，其中G=(V，A)，W={w(v_i，v_j)}，(v_i，v_j)∈A。網(wǎng)格中節(jié)點(diǎn)和邊在不同事物中可以表示不同的含義。在WebGIS系統(tǒng)中由于GIS都是以實(shí)際物體作為基礎(chǔ)，所以這里表示圖中事物的坐標(biāo)，而邊值權(quán)重要具體問(wèn)題具體分析，可表示長(zhǎng)度、時(shí)間、費(fèi)用等元素，在本系統(tǒng)中最小路徑算法計(jì)算權(quán)重值時(shí)計(jì)算的是實(shí)際點(diǎn)距的長(zhǎng)度。

所謂最小路徑問(wèn)題，是指在一個(gè)網(wǎng)格中，其中一個(gè)頂點(diǎn)作為源點(diǎn)，一個(gè)頂點(diǎn)作為終點(diǎn)，網(wǎng)絡(luò)權(quán)值取相鄰兩點(diǎn)的長(zhǎng)度值，尋求任意兩點(diǎn)v_i，v_j之間的最小路徑長(zhǎng)度。

Dijkstra算法提出了在有向的圖中按照路徑遞增的順序計(jì)算最短路徑的方法。Dijkstra算法的基本思想是利用源點(diǎn)v，找到與之相鄰的最小路徑的點(diǎn)v_i，然后再以v_i為源點(diǎn)找到與其相鄰的最小路徑的點(diǎn)v_j，依次類推直到找到終點(diǎn)v_k，從而形成集合w={v，v_i，v_j，…，v_k}，則為最小路徑點(diǎn)集合。具體算法：

1)假設(shè)抽象帶權(quán)重的有向圖為鄰接矩陣Square，其中Square[I，j]表示(v_i，v_j)兩頂點(diǎn)邊上的權(quán)值。若(v_i，v_j)不存在，則Square[I，j]表示為∞。其中S表示從v點(diǎn)出發(fā)最短路徑的頂點(diǎn)集合。集合S最初始的狀態(tài)為空集，從v點(diǎn)出發(fā)到達(dá)各個(gè)頂點(diǎn)v_的i最短路徑權(quán)值長(zhǎng)度表示為dist[i]=Square[v_0，i]，(v_i∈v)，其中v_0為起點(diǎn)序號(hào)。

2)選擇頂點(diǎn)v_j，并得到dist[j]=Min{dist[i]|v_i=V-S}，其中v_j表示從v_0出發(fā)尋求最短路徑的路線的終點(diǎn)，其中S=S∪j。

3)尋求從V出發(fā)到集合V-S的最短路徑中的頂點(diǎn)v_k，若存在dist[j]+Square[j，k]

4)重復(fù)2)、3)步驟n-1次，得到從v到其他頂點(diǎn)長(zhǎng)度為遞增的順序。

5)Dijkstra算法中按照前述步驟，每次以當(dāng)前頂點(diǎn)為源點(diǎn)，依次找出到各點(diǎn)的最小路徑長(zhǎng)度，經(jīng)過(guò)復(fù)雜度O(n^2)計(jì)算，得出從v點(diǎn)出發(fā)到達(dá)有序圖所有終點(diǎn)的最小路徑集合S。

本文的研究方向是在導(dǎo)航技術(shù)中尋找最短路徑，抽象的圖集為有向帶權(quán)圖，所以可利用不規(guī)則圖形限制搜索范圍，范圍內(nèi)的頂點(diǎn)在目標(biāo)有向路徑上，進(jìn)行Dijkstra計(jì)算時(shí)只需考慮搜索范圍內(nèi)的頂點(diǎn)。本文采用橢圓不規(guī)則圖形限定搜索范圍。

通過(guò)給定起始和終止節(jié)點(diǎn)M、N，以此兩點(diǎn)構(gòu)造橢圓區(qū)域，在此橢圓區(qū)域內(nèi)的頂點(diǎn)納入計(jì)算節(jié)點(diǎn)，否則不予不考慮。假定D=|MN|，其中D表示M、N兩點(diǎn)的歐氏距離，用于限制其他節(jié)點(diǎn)是否納入計(jì)算。

構(gòu)建橢圓時(shí)，以M、N為橢圓的兩個(gè)焦點(diǎn)，D=|MN|為橢圓的焦距，R為橢圓的長(zhǎng)軸，并設(shè)定R=τD，其中τ取正實(shí)數(shù)，一般取值為1.25。由于橢圓內(nèi)的點(diǎn)滿足：|SM|+|SN|<|MN|，所有此部分的頂點(diǎn)集S均納入計(jì)算范圍，而|XM|+|XN|≥|MN|為橢圓外的頂點(diǎn)，不納入計(jì)算范圍。

按照前述方式對(duì)Dijkstra算法進(jìn)行過(guò)濾，選擇頂點(diǎn)，若此次橢圓范圍內(nèi)未找到最佳路徑，按照一定比例擴(kuò)大橢圓范圍，直至選擇到最佳的路徑為止。

應(yīng)用Dijkstra算法進(jìn)行導(dǎo)航路徑規(guī)劃的效果圖如圖2所示，優(yōu)化后得到的結(jié)果如圖3所示。執(zhí)行效率對(duì)比見(jiàn)表1，對(duì)比原始算法，本文的改進(jìn)算法在導(dǎo)航路徑規(guī)劃中具有收斂速度快，準(zhǔn)確率高，并且能以大的概率收斂獲得全局最優(yōu)解，尤其適合復(fù)雜環(huán)境。

圖2 基于Dijkstra算法路徑規(guī)劃圖

圖3 基于優(yōu)化Dijkstra算法的規(guī)劃路徑

表1 改進(jìn)Dijkstra算法與原始算法導(dǎo)航時(shí)間對(duì)比表

3 結(jié)論

本文所設(shè)計(jì)的導(dǎo)航平臺(tái)對(duì)于高校構(gòu)建智能管理導(dǎo)航平臺(tái)有參考意義。首先利用WebGIS技術(shù)及SuperMap iObjects Java組件技術(shù)，構(gòu)建了智能導(dǎo)航平臺(tái)框架。其次研究了導(dǎo)航最小路徑Dijkstra算法的優(yōu)化路徑，并結(jié)合校園導(dǎo)航平臺(tái)的特點(diǎn)，從搜索范圍及數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)方面進(jìn)行了優(yōu)化，提升了導(dǎo)航功能的選址效率。