郭慶勝，劉 洋，李 萌，程曉茜，何 捷，王慧慧，魏智威

1. 武漢大學(xué)資源與環(huán)境科學(xué)學(xué)院，湖北 武漢 430079； 2. 北京四維圖新科技股份有限公司，北京 100094； 3. 武漢大學(xué)測繪遙感信息工程國家重點(diǎn)實(shí)驗室，湖北 武漢430079

隨著高精度導(dǎo)航地圖的推廣應(yīng)用，直接從該數(shù)據(jù)集中自動生產(chǎn)出較低精度的導(dǎo)航地圖是當(dāng)前亟待解決的問題，其中就涉及導(dǎo)航道路圖形化簡。已有的線圖形簡化算法很多，國內(nèi)外學(xué)者在這方面已取得豐碩的研究成果，主要分為全域性算法和局域性算法。全域性算法以經(jīng)典的Douglas-Peucker算法為代表[1]，隨后有些學(xué)者對此方法進(jìn)行了改進(jìn)[2-3]。為了使線的簡化達(dá)到最優(yōu)化效果，文獻(xiàn)[4—7]提出了線簡化的最優(yōu)化算法和智能化方法。局域性算法將線圖形劃分為一定數(shù)量的基本組成單元，然后分別對每個組成單元進(jìn)行化簡[7-10]，如文獻(xiàn)[10]提出了用斜拉式彎曲劃分的曲線化簡方法。在線的簡化過程中可能會引起空間關(guān)系的破壞，因此有些學(xué)者就研究了解決這些空間關(guān)系沖突的方法[11-12]，如文獻(xiàn)[11]研究了采用彎曲進(jìn)行道路化簡沖突避免的方法。線在不同尺度下需要保留必要的特征點(diǎn)，線的這些特征點(diǎn)識別方法很多[13-16]，如文獻(xiàn)[14]提出了曲線形態(tài)的結(jié)構(gòu)化表達(dá)方法，文獻(xiàn)[15]提出了基于拐點(diǎn)和極值點(diǎn)等局部特征點(diǎn)的線彎曲識別方法，文獻(xiàn)[16]研究了基于曲率法的曲線特征點(diǎn)選取方法。

對于導(dǎo)航道路數(shù)據(jù)而言，其圖形簡化需要考慮導(dǎo)航需求和地圖制圖規(guī)則的約束。當(dāng)前，在導(dǎo)航空間定位數(shù)據(jù)中，高精度導(dǎo)航地圖的數(shù)據(jù)要求必須保留到小數(shù)點(diǎn)7位數(shù)。為了從7位數(shù)的導(dǎo)航道路數(shù)據(jù)中自動提取5位數(shù)的導(dǎo)航道路數(shù)據(jù)，本文采用網(wǎng)格模型表達(dá)導(dǎo)航地圖數(shù)據(jù)，試圖提出一種漸進(jìn)式的道路圖形化簡方法，并協(xié)同處理導(dǎo)航道路網(wǎng)上的導(dǎo)航方向信息和可視化效果。

1 導(dǎo)航道路數(shù)據(jù)表達(dá)與需求

導(dǎo)航道路網(wǎng)是一個圖結(jié)構(gòu)，圖由節(jié)點(diǎn)和邊組成，其中道路為邊，道路交叉口為節(jié)點(diǎn)。一條道路可以用一串坐標(biāo)進(jìn)行描述，例如P={(x1,y1),…,(xi,yi),…,(xn,yn)}，其中，(x1,y1)和(xn,yn)為首末點(diǎn)，(xi,yi)(i≠1,i≠n)表示頂點(diǎn)，因此，設(shè)道路的內(nèi)域為P°，道路的首末點(diǎn)為?P。本文采用網(wǎng)格模型[17]表示化簡前后的導(dǎo)航數(shù)據(jù)。如圖1所示，實(shí)線為7位精度的道路，而同一條道路在5位精度下是圖中的虛線。

基于網(wǎng)格模型的導(dǎo)航道路圖形化簡的約束條件如下：

(1) 位置精度約束:道路立體交叉點(diǎn)和首末點(diǎn)在導(dǎo)航道路圖形化簡中不能刪除,只能移動，而頂點(diǎn)則可以刪除或移動，點(diǎn)移動距離應(yīng)該小于導(dǎo)航數(shù)據(jù)精度。

圖1 不同層次網(wǎng)格模型上的道路Fig.1 Roads mesh models with different levels

(3) 空間方向關(guān)系約束：導(dǎo)航道路圖形化簡前后要保持道路走向的相似性。如圖2(a)所示，化簡前的道路上的3個頂點(diǎn)A、B、C，在化簡后每個頂點(diǎn)的可選擇位置為其所在的網(wǎng)格單元的4個角點(diǎn)之一，無論選擇哪一個點(diǎn)，化簡后的道路圖形走向都可能發(fā)生變化，但是，化簡前后道路(圖2(a)中虛線為化簡后的道路)走向應(yīng)當(dāng)盡量相似。因此，當(dāng)A∈P°時，A點(diǎn)處轉(zhuǎn)角變化最小；當(dāng)A∈?P時，與A點(diǎn)關(guān)聯(lián)的所有道路的方位角變化之和最小。

圖2 約束條件示意圖Fig.2 Sketch map of constraint conditions

(4) 空間拓?fù)潢P(guān)系約束：導(dǎo)航道路化簡前后的空間拓?fù)潢P(guān)系不能被破壞。如圖2(b)所示，若線L1上刪除i點(diǎn)，則會導(dǎo)致L1與L2相交，破壞了這兩條線間的空間拓?fù)潢P(guān)系。因此，道路網(wǎng)中任意兩直線段之間的拓?fù)潢P(guān)系在綜合前后應(yīng)該保持一致。

(5) 視覺光滑程度約束：導(dǎo)航中要考慮化簡后道路的可視化效果。如圖2(c)所示，虛線轉(zhuǎn)為5位精度的道路實(shí)線后，可能會產(chǎn)生一些急拐彎和抖動現(xiàn)象，針對這種情況就需要進(jìn)行光滑處理。

2 道路頂點(diǎn)漸進(jìn)式刪除的算法

2.1 基本思想

在導(dǎo)航道路化簡過程中，需要維護(hù)道路空間方向關(guān)系和空間拓?fù)潢P(guān)系，同時還要顧及導(dǎo)航時的可視化效果，因此，本文采用漸進(jìn)式圖形綜合的思想[18-19]對道路圖形進(jìn)行簡化。這種漸進(jìn)式思想主要體現(xiàn)在：對道路上的每一個頂點(diǎn)依據(jù)約束按順序決策能否被刪除，如果遇到不滿足約束的頂點(diǎn)，則不立即處理該點(diǎn)，而是先將該點(diǎn)標(biāo)記為問題點(diǎn)，然后順序處理剩下的頂點(diǎn)，直到所有頂點(diǎn)都處理完畢，并同時更新所有被影響的頂點(diǎn)形狀特征。然后逐個處理問題點(diǎn)，此時，可能這些頂點(diǎn)的形狀特征發(fā)生改變，而不必再處理，需要按此過程對單條道路和整個道路網(wǎng)進(jìn)行迭代處理。若一次迭代處理過程中仍然存在問題點(diǎn)，則需要繼續(xù)迭代處理這些問題點(diǎn)，直到所有問題點(diǎn)全部處理完畢。

2.2 道路頂點(diǎn)的刪除方法

為了能夠保持化簡前后道路的局部形狀特征，需要對道路的局部形狀特征進(jìn)行描述，本文采用道路上相鄰頂點(diǎn)之間的距離和頂點(diǎn)處的轉(zhuǎn)向角來描述該點(diǎn)的幾何形狀特征。如圖3(a)所示，Vi為當(dāng)前的頂點(diǎn)，Vi-1和Vi+1分別為前后頂點(diǎn)，θi為頂點(diǎn)Vi處的轉(zhuǎn)向角，D[i-1,i]和D[i,i+1]分別表示Vi與Vi-1和Vi+1之間的距離。在道路圖形化簡過程中也需要顧及道路的語義特征，以便在頂點(diǎn)刪除過程中根據(jù)不同的語義特征進(jìn)行處理。線的語義特征識別方法有很多[13-15]，如文獻(xiàn)[13]采用彎曲作為線的基本單元構(gòu)建二叉樹表達(dá)線結(jié)構(gòu)的語義特征。對導(dǎo)航道路而言，直線型道路是一個比較重要的特征，因此，本文在計算局部幾何特征的基礎(chǔ)上將道路線結(jié)構(gòu)的語義特征分為直線段和彎曲段兩大類。若轉(zhuǎn)向角小于一個很小的角度，且頂點(diǎn)偏移量小于一個很小的距離值，則提取道路中較長的直線段，將直線段外的部分都看作曲線型道路段。如圖3(b)所示，其中從1號點(diǎn)到3號點(diǎn)之間為直線型道路段；4號點(diǎn)處為右拐，6號點(diǎn)處為左拐，依據(jù)這些特征也可以劃分出彎曲[15]。另外，在頂點(diǎn)刪除過程中不能破壞線之間的空間關(guān)系，如同3(c)所示，可以通過柵格索引計算當(dāng)前頂點(diǎn)與前后兩頂點(diǎn)構(gòu)成的三角形內(nèi)是否包含其他頂點(diǎn)來判斷頂點(diǎn)的刪除是否會破壞空間關(guān)系。

圖3 頂點(diǎn)刪除的約束Fig.3 Constraints on vertex deletion

在提取了道路幾何特征和語義信息基礎(chǔ)后，可對道路頂點(diǎn)進(jìn)行刪除。設(shè)β為距離閾值。對于直線型道路段，如圖4(a)所示，其兩端的頂點(diǎn)(A和B)不能刪除。對于位于直線型道路段內(nèi)部的點(diǎn)，若D[i-1,i]>β且D[i,i+1]>β，則按照導(dǎo)航要求保留該頂點(diǎn)，如圖4(b)中的C點(diǎn)，否則就刪除，如圖4(a)中的D點(diǎn)和E點(diǎn)。對于曲線型道路段部分上的頂點(diǎn)，在頂點(diǎn)刪除過程中需要考慮其周圍的空間環(huán)境，處理方法如下:

(1) 當(dāng)D[i,i-1]<β時，如圖5(a)所示，可以直接刪除Vi點(diǎn)；若在刪除Vi點(diǎn)后會破壞線之間的空間關(guān)系，如圖5(b)所示，則不能刪除Vi點(diǎn)，此時應(yīng)將Vi點(diǎn)標(biāo)記為“問題點(diǎn)”，正常處理完所有道路之后進(jìn)行迭代處理。

(2) 當(dāng)D[i,i-1]>β且D[i,i+1]<β時，需要在Vi和Vi+1兩個點(diǎn)內(nèi)刪除一個點(diǎn)。計算Vi+1點(diǎn)后段直線段的長度D[i+1,i+2]，若D[i+1,i+2]>β，則比較Vi點(diǎn)和Vi+1點(diǎn)處的轉(zhuǎn)向角的大小，如圖5(c)所示。當(dāng)在Vi點(diǎn)處的轉(zhuǎn)向角θi小于Vi+1點(diǎn)處的轉(zhuǎn)向角θi+1時，刪除Vi點(diǎn)，否則如圖5(d)所示，暫不刪除Vi點(diǎn)，將Vi點(diǎn)標(biāo)記為問題點(diǎn)，待迭代時再進(jìn)行判斷。若D[i+1,i+2]<β時，在兩種情況下可以刪除Vi點(diǎn)，如圖5(e)所示。當(dāng)Vi點(diǎn)處的轉(zhuǎn)向角θi小于導(dǎo)航規(guī)定的閾值，即Vi點(diǎn)與前后兩個頂點(diǎn)近似在一條直線上時，可以刪除Vi點(diǎn)；當(dāng)Vi+1點(diǎn)處的轉(zhuǎn)向角θi+1大于定義的閾值時，如圖5(f)所示，可以刪除Vi點(diǎn)。其他情況下均不能刪除Vi點(diǎn)，需將Vi點(diǎn)標(biāo)記為問題點(diǎn)，待迭代時再進(jìn)行判別。

圖4 直線型道路頂點(diǎn)壓縮Fig.4 Compression of vertices on linear roads

圖5 彎曲型道路頂點(diǎn)刪除Fig.5 Deletion of vertices on curved roads

對于已標(biāo)記的所有問題點(diǎn)，需要迭代處理，重新對上一輪處理時不滿足約束條件，且暫時沒有處理的頂點(diǎn)進(jìn)行判斷。根據(jù)約束條件，迭代處理所有問題點(diǎn)，直至滿足約束條件。在迭代時需要重新對問題點(diǎn)Vi計算其特征信息，根據(jù)問題點(diǎn)不同的空間環(huán)境進(jìn)行處理，處理方法如下：

(1) 若問題點(diǎn)滿足條件：D[i,i-1]>β且D[i,i+1]>β，就不再刪除該點(diǎn)，取消Vi的問題標(biāo)記。否則，仍按照彎曲部分的處理方式進(jìn)行處理。

(2) 對于Vi點(diǎn)，如圖6(a)所示，D[i,i-1]>β且D[i,i+1]<β，并且刪除Vi點(diǎn)后不再破壞道路之間的空間拓?fù)潢P(guān)系，刪除Vi點(diǎn)。

(3) 若刪除Vi點(diǎn)后會破壞道路之間的空間拓?fù)潢P(guān)系，如圖6(b)所示，則刪除Vi點(diǎn)兩側(cè)的點(diǎn)；但是，若Vi點(diǎn)兩側(cè)的點(diǎn)中也不滿足刪除條件，如圖6(c)所示，則不刪除Vi點(diǎn)兩側(cè)的點(diǎn)，并將Vi點(diǎn)標(biāo)記為問題點(diǎn),留待移位或人工編輯處理。

圖6 迭代處理Fig.6 Iterative processing

2.3 道路局部空間方向關(guān)系維護(hù)

在5位精度下，原始7位精度的一個點(diǎn)的可選位置有4個。道路內(nèi)部空間方向關(guān)系的維護(hù)就是在這4個位置中選擇最優(yōu)的位置，使維護(hù)后的線同原始精度下的線在空間方向關(guān)系上最相似。本文采用導(dǎo)航數(shù)據(jù)精度降低前后的頂點(diǎn)轉(zhuǎn)向角偏差或節(jié)點(diǎn)(道路交叉點(diǎn))關(guān)聯(lián)的直線段方位角偏差和點(diǎn)的位置偏差作為局部空間方向關(guān)系相似程度的評價指標(biāo)。

對于一般頂點(diǎn)Vi，如圖7(b)所示，按照頂點(diǎn)編號順序進(jìn)行處理。設(shè)Vi-1點(diǎn)的5位精度位置已經(jīng)確定，則當(dāng)前頂點(diǎn)Vi的空間方向關(guān)系受Vi-1和Vi+1的5位精度位置影響。首先，對Vi點(diǎn)的4個可能的5位精度位置，計算對應(yīng)的Vi-1點(diǎn)處的轉(zhuǎn)向角偏差Δθi-1，選取其中滿足約束條件的位置作為可選的一個或多個位置。然后，對于每個可選的位置，再與Vi+1點(diǎn)的4個可能5位精度位置相連接，計算每個連接在Vi點(diǎn)處轉(zhuǎn)向角的7位精度與5位精度之間的轉(zhuǎn)向角偏差Δθi，選擇其中偏差最小的位置作為調(diào)整后的位置。同理，若有多個轉(zhuǎn)向角偏差都與最小偏差相當(dāng)，則選擇在5位精度下點(diǎn)位置偏差最小的點(diǎn)作為調(diào)整后的優(yōu)選位置。

圖7 道路局部空間方向關(guān)系維護(hù)Fig.7 Maintenance of local spatial directional relations of roads

另外，在道路局部空間方向關(guān)系調(diào)整的過程中，可能會出現(xiàn)與原始點(diǎn)處的道路轉(zhuǎn)向相反，這不符合約束條件。但是，若原始點(diǎn)在近似一條直線上，調(diào)整前后的轉(zhuǎn)向角偏差Δθi很小，即使道路轉(zhuǎn)向相反，也認(rèn)為符合約束條件，其中，轉(zhuǎn)向角偏差Δθi的閾值為一個大于0的很小的值。若Δθi大于閾值，就按照前文所提到的方法處理。道路局部空間方向關(guān)系維護(hù)的目標(biāo)函數(shù)和約束條件見式(1)

(1)

2.4 道路局部的視覺光滑

當(dāng)導(dǎo)航道路數(shù)據(jù)的精度降低時，在道路局部可能存在尖角點(diǎn)和抖動點(diǎn)，在導(dǎo)航道路數(shù)據(jù)可視化時就需要進(jìn)行光滑處理。已有許多曲線光滑算法，其中比較常見的方法是用擬合的曲線逼近原始曲線[25-26]，但是在網(wǎng)格模型中由于受到網(wǎng)格精度的限制，新生成的5位精度曲線無法實(shí)現(xiàn)數(shù)學(xué)意義上的光滑。本文從道路視覺光滑的角度，提出了一種顧及道路局部視覺認(rèn)知規(guī)律的光滑算法。

首先，需要提取5位精度下道路的尖角點(diǎn)和抖動點(diǎn)，在Vi點(diǎn)處為尖角點(diǎn)的判定條件為：|θi|>β，其中，β為轉(zhuǎn)向角閾值。當(dāng)與Vi點(diǎn)相鄰的頂點(diǎn)的轉(zhuǎn)向角方向同時變化時，則認(rèn)為在該點(diǎn)處發(fā)生了抖動，Vi點(diǎn)為抖動點(diǎn)。但是，從道路可視化上看，若Vi點(diǎn)兩側(cè)直線段的長度都比較長，則該點(diǎn)就不是抖動點(diǎn)。抖動點(diǎn)的條件見式(2)

其次，閱讀作為作文素材的來源，需要學(xué)生在平時課外閱讀或是看到課文中的好的詞語和句子時，摘抄到一個本子上，收集起來，便于使用時查找，例如“問渠那得清如許？為有源頭活水來”的名詩。又如朱自清在《春》中是這么描寫南方春雨的，“看，像牛毛，像花針，像細(xì)絲，密密地斜織著，人家屋頂上全籠著一層薄煙”。胸中有墨水，下筆之時才能夠信手拈來、旁征博引。

(2)

式中，θi為i點(diǎn)處的轉(zhuǎn)向角；D[i,i-1]和D[i,i+1]為當(dāng)前點(diǎn)Vi前后兩條直線段的長度；d為長度閾值。

尖角點(diǎn)處的光滑插值方法如圖8(a)所示。設(shè)∠COD為需要光滑的尖角，O點(diǎn)處的道路轉(zhuǎn)向角為θi，A和B為待插入的點(diǎn)，|OA|和|OB|為插入線段的長度，β2和β3分別為插入線段OA和OB與直線L2的夾角，L1為∠COD的角平分線，L2垂直于L1,并相交于O點(diǎn)。下面以A點(diǎn)的位置計算為例，說明插入A點(diǎn)的過程：

(1) 計算OA與OC向量的夾角，β5=90°-β1/2-β2。

(2) 將O設(shè)為坐標(biāo)原點(diǎn)，以O(shè)C為X軸的正方向構(gòu)建臨時坐標(biāo)系，則可用式(3)計算點(diǎn)A在該臨時坐標(biāo)系中的坐標(biāo)

(3)

(3) 將臨時坐標(biāo)系下的坐標(biāo)轉(zhuǎn)換為原始坐標(biāo)系下的坐標(biāo)，見式(4)

(4)

式中，X、Y為原始坐標(biāo)系下點(diǎn)的坐標(biāo)；θ為臨時坐標(biāo)系下向量OC與原始X軸正方向的夾角；a、b為臨時坐標(biāo)系原點(diǎn)O平移到原坐標(biāo)系原點(diǎn)在X、Y軸方向上的平移距離。

(4) 計算所得的點(diǎn)為7位精度，需要轉(zhuǎn)換為5位精度，并從4個可能位置中選擇最優(yōu)的位置，條件是：①OA的長度大于導(dǎo)航需求中的距離閾值；②OA與OC之間夾角最小；③插入點(diǎn)A后,β6應(yīng)反映局部形狀特征，即β6×θi>0;對于B點(diǎn)而言，則是β7×θi>0。

抖動點(diǎn)的處理如圖8(b)所示。設(shè)長度閾值為dis；Vi點(diǎn)前后兩條直線段的長度分別為D[i,i-1]和D[i,i+1]。抖動點(diǎn)處理方法是：若D[i,i-1]>dis，且D[i,i+1]>dis，則不處理，如圖8(b)的第4號點(diǎn)；否則，用短直線段的中點(diǎn)代替原始的頂點(diǎn)，如圖8(b)中帶圓圈的第1、2、3、5、6號點(diǎn)分別代替原始的第1、2、3、5、6號點(diǎn)。

圖8 道路視覺光滑的計算方法Fig.8 Calculation method on visual smoothing of roads

3 節(jié)點(diǎn)處空間方向關(guān)系維護(hù)

導(dǎo)航中道路網(wǎng)節(jié)點(diǎn)處的道路走向十分重要。如圖9所示，道路節(jié)點(diǎn)A與3條道路線相關(guān)聯(lián)，當(dāng)導(dǎo)航道路數(shù)據(jù)從7位精度降為5位精度時，需要保持節(jié)點(diǎn)A處3條道路之間的空間方向關(guān)系。這種空間方向關(guān)系，本文用各條道路繞節(jié)點(diǎn)A的空間方位間接表達(dá)，并只考慮與節(jié)點(diǎn)A直接關(guān)聯(lián)的直線段(AA1、AA2、AA3)的空間方位。從圖9可以看出，這里之所以用AA3，而不是AA4，是因為需要考慮到道路段AD是一條直線，這是一個非常重要的導(dǎo)航信息。

如圖10所示，道路網(wǎng)節(jié)點(diǎn)A與點(diǎn)B關(guān)聯(lián)，A點(diǎn)和B點(diǎn)在5位精度下的可能位置均為4個，因此A點(diǎn)和B點(diǎn)的可能連接方式共有4×4=16個。計算所有連接方式的方位角，將所得的16個方位角同原始的7位精度下AB的方位角進(jìn)行比較，優(yōu)選偏差最小的連接。當(dāng)有多個可能的連接都與原始直線段AB的空間方向關(guān)系非常相似時，則比較這些連接與原始直線段AB之間的位置偏差。這里的位置偏差定義為節(jié)點(diǎn)A的可能位置同原始精度位置之間的距離。同理，對于B點(diǎn)的5位精度位置也是按照這種條件判斷，從而間接控制線段AB的長度偏差盡量小。如圖10所示，藍(lán)色的A2B2連接和紅色的A1B1連接都與原始直線段AB的空間方向關(guān)系非常相似，但是，A1離A更近，因此選擇A1B1連接方式。

圖9 道路網(wǎng)節(jié)點(diǎn)處的空間場景Fig.9 Spatial scene at the junction of a road network

當(dāng)?shù)缆肪W(wǎng)節(jié)點(diǎn)關(guān)聯(lián)多個點(diǎn)時，就需要考慮與道路網(wǎng)節(jié)點(diǎn)A關(guān)聯(lián)的所有直線段與原始直線段之間空間方向關(guān)系的整體相似程度。設(shè)節(jié)點(diǎn)A與M條直線段相關(guān)聯(lián)，這些原始直線段的方位角為AZ(i)，其中，i=1,2,…,M；5位精度下可能形成的直線段方位角為AZP(i，k,j)，其中，i=1,2,…,M；k為節(jié)點(diǎn)A的可能位置，k=0,1,2,3;j為與節(jié)點(diǎn)A相鄰的點(diǎn)(i=1,2,…,M)的可能位置，j=0,1,2,3。當(dāng)數(shù)據(jù)精度降低時，在節(jié)點(diǎn)A處空間場景中具有空間方向關(guān)系最相似程度的優(yōu)選點(diǎn)位置的計算方法見式(5)

(5)

式中，f1(k)為點(diǎn)A在k位置下與M條直線段方位角偏差之和；f2(i，k)為點(diǎn)A在k位置下與第i條直線段的方位角偏差；f3(k)為點(diǎn)A在k位置下7位精度與5位精度的距離偏差，V5(i,k)為點(diǎn)A在k位置下5位精度的坐標(biāo)，V7(i)為點(diǎn)A在7位精度下的坐標(biāo)；β為角度閾值，當(dāng)f1(k)≤β時，即當(dāng)方位角偏差之和變化都比較小時，優(yōu)選點(diǎn)A位置偏差最小的位置。

為了使得整個道路網(wǎng)所有節(jié)點(diǎn)處的空間方向關(guān)系整體上盡量保證與原始精度時的空間方向關(guān)系最相似，本文先對節(jié)點(diǎn)的連接度進(jìn)行排序，然后優(yōu)先處理連接度較大的節(jié)點(diǎn)。另外，在數(shù)據(jù)處理的過程中，由于當(dāng)前處理的節(jié)點(diǎn)可能關(guān)聯(lián)了已經(jīng)處理的節(jié)點(diǎn)或被動處理的交叉點(diǎn)，因此對于已經(jīng)處理過的節(jié)點(diǎn)位置就不再調(diào)整。算法流程如下：

(1) 掃描所有道路節(jié)點(diǎn)，獲取與每個節(jié)點(diǎn)相連接的所有道路直線段。

(2) 根據(jù)節(jié)點(diǎn)所關(guān)聯(lián)的道路直線段的數(shù)量(節(jié)點(diǎn)連接度)，對節(jié)點(diǎn)進(jìn)行排序。

(3) 按順序選取要處理的節(jié)點(diǎn)。

(4) 計算當(dāng)前節(jié)點(diǎn)與關(guān)聯(lián)點(diǎn)在精度降低時的所有可能連接方式，對每種連接方式計算方位角偏差，利用式(5)判斷當(dāng)前節(jié)點(diǎn)的最優(yōu)位置。

4 生產(chǎn)試驗與分析

筆者采用C#開發(fā)了用于導(dǎo)航道路數(shù)據(jù)綜合(從7位精度轉(zhuǎn)為5位精度)的算法試驗軟件，已用于多個城市的5位精度導(dǎo)航數(shù)據(jù)試生產(chǎn)。本文選取重慶市主城區(qū)7位精度的導(dǎo)航道路網(wǎng)數(shù)據(jù)用于算法分析。該數(shù)據(jù)集共包含道路53 525條和233 584個點(diǎn)，其中，道路網(wǎng)節(jié)點(diǎn)有8514個。圖11為生產(chǎn)試驗中的部分?jǐn)?shù)據(jù)，整個數(shù)據(jù)處理流程見圖12。

為了滿足導(dǎo)航道路數(shù)據(jù)從7位精度降為5位精度的需要，在生產(chǎn)試驗中設(shè)置了相應(yīng)的參數(shù)和閾值，設(shè)判定直線的轉(zhuǎn)向角閾值為2°；點(diǎn)之間的最小距離閾值為2 m；最大距離閾值設(shè)為5 m；轉(zhuǎn)向角偏差閾值為6°；判定“尖角”的角度閾值為30°；7位精度下插入線段的長度為2.5 m。圖13是圖11中方框區(qū)域的試驗結(jié)果，黑色表示7位精度的目標(biāo)，綠色表示5位精度的目標(biāo)。

圖14為圖13中紅色方框區(qū)域的放大圖。圖14(a)為道路頂點(diǎn)漸進(jìn)式刪除的結(jié)果，紅色表示綜合后的目標(biāo)；圖14(b)為道路空間方向維護(hù)的結(jié)果，藍(lán)色表示空間方向關(guān)系維護(hù)后的目標(biāo)；圖14(c)為道路視覺光滑后的結(jié)果，黃色表示光滑后的目標(biāo)。

圖11 高精度的道路網(wǎng)數(shù)據(jù)Fig.11 Road network data with high precision

圖12 導(dǎo)航道路圖形化簡的流程Fig.12 Flow chart of graphic simplification for navigation roads

圖13 導(dǎo)航道路圖形化簡的結(jié)果Fig.13 The result of graphic simplification for navigation roads

圖14 綜合過程中各階段的指定局部放大圖Fig.14 Enlarged maps of the given local region in each stage of generalization

在道路圖形簡化過程中，空間方向關(guān)系維護(hù)是非常重要的一個環(huán)節(jié)，在點(diǎn)之間的最小距離閾值為2 m的情況下，本文分別統(tǒng)計了試驗結(jié)果中道路網(wǎng)節(jié)點(diǎn)和道路頂點(diǎn)處的空間方向關(guān)系維護(hù)效果。圖15是道路網(wǎng)節(jié)點(diǎn)處空間方向關(guān)系維護(hù)結(jié)果的統(tǒng)計圖，橫軸表示與節(jié)點(diǎn)連接的道路直線段方位角在空間方向關(guān)系維護(hù)前后的角度變化區(qū)間；縱軸表示在角度變化區(qū)間內(nèi)的直線段統(tǒng)計數(shù)量；藍(lán)色表示調(diào)整前；橘黃色表示調(diào)整后。圖16是道路頂點(diǎn)處空間方向關(guān)系維護(hù)結(jié)果的統(tǒng)計圖，橫軸表示道路頂點(diǎn)處轉(zhuǎn)向角在空間方向關(guān)系維護(hù)前后的角度變化區(qū)間；縱軸表示在角度變化區(qū)間內(nèi)的頂點(diǎn)統(tǒng)計數(shù)量；藍(lán)色表示調(diào)整前；橘黃色表示調(diào)整后。從統(tǒng)計圖表中可以看出，本文的空間方向關(guān)系維護(hù)算法使得道路網(wǎng)節(jié)點(diǎn)處和道路頂點(diǎn)處的空間方向變化比直接使用四舍五入轉(zhuǎn)換方法的空間方向變化明顯減少。

圖15 節(jié)點(diǎn)處空間方向關(guān)系維護(hù)結(jié)果的統(tǒng)計Fig.15 Statistics of results at nodes after maintaining spatial directional relations

圖16 道路頂點(diǎn)處空間方向關(guān)系維護(hù)結(jié)果的統(tǒng)計Fig.16 Statistics of results at vertices after maintaining spatial directional relations

當(dāng)最小距離閾值為2 m時，本試驗結(jié)果中沒有出現(xiàn)拓?fù)潢P(guān)系方面的問題點(diǎn)。當(dāng)設(shè)置最小距離閾值為5 m時，就出現(xiàn)了拓?fù)潢P(guān)系方面的問題點(diǎn)。如圖17所示(7位精度的線為綠色；5位精度的線為棕色)，問題點(diǎn)A不滿足最小距離閾值條件，但是若刪除該點(diǎn)，在點(diǎn)C2處就會出現(xiàn)拓?fù)潢P(guān)系錯誤。圖17中藍(lán)色線表示刪除A點(diǎn)后出現(xiàn)的拓?fù)潢P(guān)系破壞情況，從B1到B14是不可以刪除的道路立體交叉點(diǎn)，C1和C2是導(dǎo)航地圖模型中定義的不可刪除點(diǎn)。在5位精度的導(dǎo)航地圖數(shù)據(jù)生產(chǎn)中，點(diǎn)之間的距離有嚴(yán)格規(guī)定，若道路簡化后存在點(diǎn)之間的距離小于設(shè)置的距離閾值，就標(biāo)識這些點(diǎn)為問題點(diǎn)，以便有針對性地進(jìn)行人工數(shù)據(jù)編輯。當(dāng)導(dǎo)航地圖數(shù)據(jù)可視化時，若道路頂點(diǎn)處轉(zhuǎn)彎很急，符號化后的道路圖形就顯得不光滑，本文所提出的視覺光滑算法能很好地解決這個問題。將本文方法與ArcGIS中常用的PAEK光滑算法進(jìn)行對比，結(jié)果如圖18所示。

圖17 存在拓?fù)潢P(guān)系錯誤的問題點(diǎn)Fig.17 Points with questions about topological errors

圖18 兩種光滑結(jié)果的對比Fig.18 Comparison between two kinds of smoothing results

5位精度的導(dǎo)航地圖數(shù)據(jù)生產(chǎn)有嚴(yán)格的要求，相關(guān)的導(dǎo)航需求是：點(diǎn)之間的距離大于2 m；道路網(wǎng)節(jié)點(diǎn)處關(guān)聯(lián)的道路之間的空間方向關(guān)系變形最?。坏缆讽旤c(diǎn)處的轉(zhuǎn)向角變化最??；所有點(diǎn)的位置誤差小于1.42 m；空間目標(biāo)之間的拓?fù)潢P(guān)系應(yīng)該與7位精度的導(dǎo)航地圖原始數(shù)據(jù)一致；簡化后的道路不能出現(xiàn)抖動和急轉(zhuǎn)彎情況；點(diǎn)之間的距離也需要小于5 m(用戶定義的最大距離閾值)。這些要求在整個道路網(wǎng)圖形簡化過程中都需要進(jìn)行判斷，若存在不滿足要求的點(diǎn)，筆者所開發(fā)的軟件就自動進(jìn)行標(biāo)記，說明是問題點(diǎn)。

在試驗中也使用ArcGIS10.2的兩種線化簡方法(點(diǎn)刪除方法和彎曲化簡方法)對同樣的數(shù)據(jù)集進(jìn)行了處理。以四維圖新導(dǎo)航地圖的需求為標(biāo)準(zhǔn)，對比分析了ArcGIS的處理結(jié)果和本文算法軟件試生產(chǎn)的結(jié)果。

試驗用的計算機(jī)配置條件是：Intel(R) Core(TM)i7-4790 CPU@3.60 GHz,RAM: 8 GB,windows10,64位。ArcGIS的彎曲化簡方法在無選項，閾值為5 m的條件下，耗時60 s；ArcGIS的點(diǎn)刪除方法在無選項、閾值為2 m的條件下，耗時54 s；本文的化簡算法耗時172.39 s，空間方向關(guān)系維護(hù)耗時238.13 s，空間拓?fù)潢P(guān)系維護(hù)耗時25.97 s，視覺光滑耗時17.07 s。由此可以看出，本文算法耗時比較多。主要原因是本文算法在化簡階段需要判斷和維護(hù)空間拓?fù)潢P(guān)系，為了滿足導(dǎo)航需求，還需要維護(hù)空間方向關(guān)系和視覺光滑效果。而ArcGIS的這兩種方法都沒有考慮這些空間關(guān)系的維護(hù)。

在原始試驗數(shù)據(jù)(重慶市主城區(qū))中道路有233 584個點(diǎn)，用本文算法簡化后，保留了119 938個點(diǎn)，光滑后有129 884個點(diǎn)。按照本文描述的5位精度下的導(dǎo)航要求，檢查了這3個試驗結(jié)果，產(chǎn)生差異的原因是：點(diǎn)刪除方法只考慮了點(diǎn)的偏移量，彎曲化簡方法只考慮了彎曲的大小，它們都沒有考慮保留點(diǎn)之間的距離應(yīng)該在導(dǎo)航規(guī)定的距離閾值范圍內(nèi)。圖19是這3種方法所得結(jié)果的局部放大圖，可以直觀地了解它們之間的差異。在圖形化簡算法的對比試驗中，ArcGIS的兩個線圖形化簡工具無法直接表達(dá)導(dǎo)航道路數(shù)據(jù)生產(chǎn)的要求，本文依據(jù)5位數(shù)據(jù)精度導(dǎo)航道路數(shù)據(jù)生產(chǎn)對點(diǎn)之間距離的要求，設(shè)置了近似的閾值。

在生產(chǎn)試驗中，道路圖形化簡算法和空間拓?fù)潢P(guān)系維護(hù)算法的參數(shù)是按照四維圖新5位數(shù)據(jù)精度導(dǎo)航地圖生產(chǎn)的具體要求設(shè)置；空間方向關(guān)系維護(hù)算法和視覺光滑算法的有關(guān)角度的閾值是按照生產(chǎn)單位對導(dǎo)航道路數(shù)據(jù)的要求在進(jìn)行了多次試驗和調(diào)整后確定，是經(jīng)驗值。

圖19 3種方法所得結(jié)果的局部放大圖Fig.19 Enlarged maps of partial results of three kinds of methods

在試驗中所使用的漸進(jìn)式道路圖形簡化方法充分利用了道路頂點(diǎn)漸進(jìn)式刪除、空間方向關(guān)系維護(hù)和視覺光滑等操作。這里的“漸進(jìn)式”主要體現(xiàn)在：當(dāng)?shù)缆讽旤c(diǎn)刪除時，必須保證滿足道路圖形簡化的約束條件；若無法滿足這些約束條件，就需要臨時標(biāo)記該頂點(diǎn)為問題點(diǎn)，并記錄其位置，然后在空間上下文關(guān)系發(fā)生變化后再回頭來處理這些問題點(diǎn)，該過程是一個迭代過程。當(dāng)需要從7位精度的道路數(shù)據(jù)綜合為5位精度的道路數(shù)據(jù)時，在試驗中并不是先綜合為6位精度的道路數(shù)據(jù)，再綜合為5位精度的道路數(shù)據(jù)。

5 總 結(jié)

本文基于網(wǎng)格模型有效表達(dá)了高精度導(dǎo)航數(shù)據(jù)向低精度導(dǎo)航數(shù)據(jù)的轉(zhuǎn)換過程，詳細(xì)說明了5位數(shù)據(jù)精度導(dǎo)航道路數(shù)據(jù)生產(chǎn)的特殊要求，將道路圖形化簡、導(dǎo)航地圖要素之間空間拓?fù)潢P(guān)系維護(hù)、道路本身和道路網(wǎng)交叉點(diǎn)處空間方向關(guān)系維護(hù)以及道路數(shù)據(jù)可視化的視覺光滑等算法協(xié)同在一起，提出了一種基于網(wǎng)格模型的導(dǎo)航道路圖形漸進(jìn)式協(xié)同化簡方法。在該方法中，網(wǎng)格模型體現(xiàn)了導(dǎo)航數(shù)據(jù)的表達(dá)需求；在道路圖形化簡過程中強(qiáng)調(diào)了漸進(jìn)式質(zhì)量控制；協(xié)同了空間關(guān)系維護(hù)和視覺光滑；在點(diǎn)刪除過程中綜合考慮了點(diǎn)之間的距離、點(diǎn)的語義特征和點(diǎn)附近的空間關(guān)系；依據(jù)導(dǎo)航數(shù)據(jù)網(wǎng)格模型表達(dá)的特征和視覺認(rèn)知規(guī)律，設(shè)計了道路的視覺光滑方法。從試驗結(jié)果看，本文所提出的方法顧及了導(dǎo)航需求，能夠維護(hù)好道路網(wǎng)在數(shù)據(jù)精度降低時的空間方向關(guān)系，圖形的可視化效果好。但是，本文所提出的方法在導(dǎo)航道路網(wǎng)向更低精度轉(zhuǎn)換時如何與道路選取相結(jié)合還有待進(jìn)一步的研究。該方法是針對5位精度的導(dǎo)航道路數(shù)據(jù)生產(chǎn)特點(diǎn)所提出的，制圖綜合的約束主要是點(diǎn)之間的最小距離、原始點(diǎn)的最大偏移距離、道路轉(zhuǎn)彎方向和大小、道路連接關(guān)系、視覺光滑程度等，道路圖形簡化的主要任務(wù)是在保留道路(網(wǎng))的導(dǎo)航所需要信息條件下刪除多余的道路頂點(diǎn)。因此本文所提出的方法并不直接適用于制圖約束條件性質(zhì)不同的線圖形簡化任務(wù)。