涂巖愷（中國(guó)電子科技集團(tuán)第三十研究所 廈門(mén)雅迅網(wǎng)絡(luò)股份有限公司，福建 廈門(mén) 361008）

電子地圖POI標(biāo)簽位置優(yōu)化處理

涂巖愷
（中國(guó)電子科技集團(tuán)第三十研究所 廈門(mén)雅迅網(wǎng)絡(luò)股份有限公司，福建 廈門(mén) 361008）

為減少繪制電子地圖時(shí)POI標(biāo)簽對(duì)道路的遮擋，提出一種檢測(cè)POI標(biāo)簽與地圖背景中道路是否產(chǎn)生重疊壓蓋并調(diào)整標(biāo)簽位置的方法。采用劃分網(wǎng)格數(shù)據(jù)的方法減少檢測(cè)計(jì)算量，對(duì)可能壓蓋路段進(jìn)行過(guò)濾，提取可能與POI產(chǎn)生壓蓋的路段，再采用建立局部坐標(biāo)系判斷繪制元素斜率關(guān)系的方法，檢測(cè)該P(yáng)OI標(biāo)簽是否與道路產(chǎn)生重疊壓蓋，進(jìn)而做出調(diào)整。應(yīng)用實(shí)例表明，該方法能以較高的效率增強(qiáng)地圖顯示效果，提升用戶(hù)體驗(yàn)。

電子地圖；POI標(biāo)簽；位置優(yōu)化；壓蓋檢測(cè)

DOI：10.13669/j.cnki.33-1276/z.2015.037

0　引 言

電子地圖P O I標(biāo)簽繪制是一個(gè)重要問(wèn)題，良好的POI標(biāo)簽繪制應(yīng)盡量減少壓蓋地圖背景中的關(guān)鍵區(qū)域［1］。車(chē)載導(dǎo)航與定位應(yīng)用［2］中道路是最關(guān)鍵信息，當(dāng)?shù)缆愤吘壍腜O I標(biāo)簽過(guò)多、壓蓋現(xiàn)象嚴(yán)重時(shí)，會(huì)影響道路顯示甚至覆蓋復(fù)雜路口細(xì)節(jié)等關(guān)鍵信息，從而影響用戶(hù)體驗(yàn)。

由于電子地圖瓦片數(shù)量龐大，達(dá)十億量級(jí)［3］，因而道路壓蓋處理效率是關(guān)鍵。葉常春等［4］采用外接矩形重疊法比對(duì)地圖元素，但由于涉及復(fù)雜的排列組合比對(duì)，張鵬程等［5］提出應(yīng)盡量避免這類(lèi)NP完全問(wèn)題求解。趙靜等［6］采用像素占用的方法判斷是否壓蓋，但該方法要先將地圖矢量數(shù)據(jù)標(biāo)量化，沒(méi)有利用矢量數(shù)據(jù)量小、處理快的優(yōu)點(diǎn)。李永紅等［7］提出一種快速判斷線(xiàn)段相交的方法，該方法處理步驟較少，但涉及向量的內(nèi)積與外積運(yùn)算，所消耗計(jì)算量較大。本文提出一種直接利用矢量數(shù)據(jù)快速進(jìn)行POI標(biāo)簽與道路重疊檢測(cè)的方法。該方法盡可能采用時(shí)間消耗最小的邏輯判斷取代其它運(yùn)算指令，不僅能有效減少P O I標(biāo)簽對(duì)背景道路區(qū)域的覆蓋，防止關(guān)鍵信息丟失，而且具有較高的處理效率。1優(yōu)化處理流程

優(yōu)化后的壓蓋檢測(cè)方法包括網(wǎng)格劃分模塊、路段過(guò)濾模塊、基于局部坐標(biāo)系斜率關(guān)系的壓蓋檢測(cè)模塊、標(biāo)簽調(diào)整模塊。每一模塊都有其功能和作用。一是網(wǎng)格劃分模塊。由于地圖數(shù)據(jù)量巨大，因而需要對(duì)地圖數(shù)據(jù)按地圖級(jí)別劃分為不同的網(wǎng)格區(qū)域，逐個(gè)網(wǎng)格進(jìn)行處理，以達(dá)到減少計(jì)算量的目的，提高檢測(cè)速率。二是路段過(guò)濾模塊。將P OI標(biāo)簽與道路的交叉覆蓋分為縱向覆蓋與橫向覆蓋兩類(lèi)，按坐標(biāo)區(qū)間交集原則初步過(guò)濾出可能產(chǎn)生壓蓋的路段，進(jìn)一步減少壓蓋判斷的路段數(shù)量，同時(shí)能在下一個(gè)模塊斜率檢測(cè)中將各點(diǎn)斜率控制在兩個(gè)象限以?xún)?nèi)，降低檢測(cè)復(fù)雜度。三是基于局部坐標(biāo)系斜率關(guān)系的壓蓋檢測(cè)模塊。以每個(gè)可能路段任一端點(diǎn)為原點(diǎn)建立檢測(cè)坐標(biāo)系，在坐標(biāo)系內(nèi)計(jì)算道路另一端點(diǎn)、P O I標(biāo)簽各端點(diǎn)與原點(diǎn)斜率，制定斜率間的相互極性與絕對(duì)值大小關(guān)系判斷標(biāo)準(zhǔn)，依據(jù)本標(biāo)準(zhǔn)能快速確定該P(yáng)O I標(biāo)簽是否與道路產(chǎn)生壓蓋。四是標(biāo)簽調(diào)整模塊。根據(jù)斜率檢測(cè)模塊的結(jié)果，將P O I標(biāo)簽調(diào)整至新的位置并迭代判斷，最終將P OI標(biāo)簽在無(wú)壓蓋區(qū)域上顯示。電子地圖P OI標(biāo)簽壓蓋檢測(cè)流程如圖1所示。

圖1　電子地圖POI標(biāo)簽壓蓋檢測(cè)流程

1.1網(wǎng)格劃分

計(jì)算地圖等級(jí)為0時(shí)的基準(zhǔn)比例尺S0。地圖等級(jí)為0時(shí)將世界地圖劃分為2×2個(gè)網(wǎng)格，每個(gè)網(wǎng)格對(duì)應(yīng)一張256×256分辨率地圖瓦片，則基準(zhǔn)比例尺S0=360度/ （256×2）像素=0.703 125。

假設(shè)需要檢測(cè)道路壓蓋的地圖等級(jí)為n，計(jì)算該等級(jí)下比例尺Sn=Sn/2n。該等級(jí)下世界地圖劃分為2n+1× 2n+1個(gè)網(wǎng)格，依據(jù)對(duì)應(yīng)比例尺Sn得到每個(gè)網(wǎng)格對(duì)應(yīng)的經(jīng)緯度邊界。依據(jù)經(jīng)緯度邊界，取出經(jīng)緯度邊界內(nèi)的道路矢量數(shù)據(jù)（一般取國(guó)道、省道作為待檢測(cè)道路，也可根據(jù)需求增加要檢測(cè)的道路等級(jí)或種類(lèi)）與PO I數(shù)據(jù)存入全局緩存中，供后續(xù)步驟檢測(cè)調(diào)用。該步驟通過(guò)地圖等級(jí)與比例尺關(guān)系進(jìn)行網(wǎng)格劃分，將一個(gè)網(wǎng)格內(nèi)待檢測(cè)路段數(shù)據(jù)與P OI數(shù)量都限定在一個(gè)比較合理的范圍內(nèi)，避免將地圖中所有道路與一個(gè)P OI進(jìn)行比較，也避免針對(duì)每個(gè)P OI劃分出一個(gè)局部檢測(cè)區(qū)域的復(fù)雜計(jì)算。

1.2路段過(guò)濾

進(jìn)一步減少壓蓋檢測(cè)計(jì)算量，取路段的縱向/橫向坐標(biāo)區(qū)間與POI標(biāo)簽的縱向/橫向坐標(biāo)區(qū)間，計(jì)算兩個(gè)區(qū)間的交集，交集不為空的路段為可能覆蓋路段，交集為空的路段不會(huì)與PO I相交覆蓋，對(duì)它們進(jìn)行過(guò)濾。

（1）從全局緩存中取出一個(gè)POI坐標(biāo)P（Px，Py）和它的標(biāo)簽位置T（Tleft，Ttop，Tright，Tbottom）。其中，Px，Py代表POI位置在地圖上的橫向和縱向坐標(biāo)值，Tleft，Ttop，Tright，Tbottom分別代表POI標(biāo)簽的左、上、右、下四個(gè)坐標(biāo)值。

（2）從全局緩存中取出網(wǎng)格內(nèi)某一路段rm，m∈［1，M］。其中，M為路段數(shù)量，rm=［rm1（xm1，ym1），rm2（xm2，ym2）］，rm1和rm2為路段的兩個(gè)端點(diǎn)，（xm1，ym1），（xm2，ym2）為端點(diǎn)對(duì)應(yīng)坐標(biāo)。

（3）取路段的Y坐標(biāo)區(qū)間Am=［ym1，ym2］（ym2≥ym1），取POI標(biāo)簽的Y坐標(biāo)區(qū)間B=［Ttop，Tbottom］，計(jì)算A與B的交集C=A∩B。

（4）如果C=ф，則該段道路肯定不會(huì)與POI標(biāo)簽產(chǎn)生橫向重疊，將其過(guò)濾掉不進(jìn)行檢測(cè)；如果C≠ф，則該路段可能與P OI標(biāo)簽產(chǎn)生橫向重疊，將該路段rm取出，放入待檢測(cè)集Rh中。重復(fù)（2）直到該網(wǎng)格內(nèi)所有路段均被過(guò)濾一遍。得到最終的待檢測(cè)道路集Rh，供斜率檢測(cè)步驟調(diào)用。

縱向壓蓋路段過(guò)濾原理及步驟與橫向壓蓋路段過(guò)濾原理及步驟相同。路段過(guò)濾流程所涉及運(yùn)算為單坐標(biāo)軸上的交集運(yùn)算，每次過(guò)濾只需要進(jìn)行兩次邏輯判斷。

1.3基于局部坐標(biāo)系斜率關(guān)系的壓蓋檢測(cè)

橫向斜率檢測(cè)的目的是判斷POI標(biāo)簽的上下邊緣是否與道路產(chǎn)生壓蓋現(xiàn)象，其檢測(cè)步驟如下：先從待檢測(cè)道路集Rh中取出某一路段rn=［rn1（xn1，yn1），rn 2（xn2，yn2）］，n∈［1，N］，其中N為待檢測(cè)道路集中路段數(shù)量（N≤M）。接著取任意一道路端點(diǎn)為原點(diǎn)（假設(shè)取rn1），x軸為緯度線(xiàn)方向，y軸為經(jīng)度線(xiàn)方向，建立檢測(cè)坐標(biāo)系。取POI標(biāo)簽上下兩條橫線(xiàn)為檢測(cè)線(xiàn)段，以POI標(biāo)簽上邊緣線(xiàn)TLTR為例，其對(duì)應(yīng)端點(diǎn)坐標(biāo)TL=（Tleft，Ttop），TR=（Tright，Ttop）。經(jīng)過(guò)路段過(guò)濾處理，檢測(cè)線(xiàn)段TLTR，路段rn在檢測(cè)坐標(biāo)系內(nèi)的相對(duì)位置關(guān)系，被約束成兩個(gè)象限內(nèi)六類(lèi)可能的幾何關(guān)系，如圖2所示。

圖2　局部坐標(biāo)系斜率關(guān)系

計(jì)算rn2與rn1的斜率k1，TL與rn1的斜率k2，TR與rn1的斜率k3。檢測(cè)壓蓋現(xiàn)象的判斷流程如下：

If（k2，k3符號(hào)不同）

縱向斜率檢測(cè)的原理及步驟與橫向檢測(cè)的原理及步驟相同。通過(guò)斜率關(guān)系檢測(cè)，不僅能提供有效的壓蓋檢測(cè)，而且能通過(guò)速度較快的邏輯判斷代替兩條線(xiàn)段相交的求解方程組運(yùn)算。從判斷流程看，只需要進(jìn)行三次除法運(yùn)算和兩次加法運(yùn)算，其余均為計(jì)算機(jī)處理速度最快的邏輯判斷指令，這對(duì)于海量電子地圖處理來(lái)說(shuō)能節(jié)省大量的時(shí)間。

1.4標(biāo)簽調(diào)整

地圖中默認(rèn)POI標(biāo)簽位置T（Tleft，Ttop，Tright，Tbottom）位于POI坐標(biāo)P（Px，Py）右方。當(dāng)檢測(cè)到POI標(biāo)簽位置T與道路產(chǎn)生壓蓋后進(jìn)入標(biāo)簽調(diào)整步驟，將標(biāo)簽位置T 按PO I左方、上方、右方、下方的優(yōu)先級(jí)調(diào)整。每一次調(diào)整位置后重新返回路段過(guò)濾步驟，如此迭代檢測(cè)是否與道路壓蓋，直至調(diào)整到不會(huì)產(chǎn)生壓蓋的位置繪出PO I標(biāo)簽。如果所有位置調(diào)整后仍會(huì)產(chǎn)生壓蓋，則視該P(yáng)OI點(diǎn)的重要程度［8］選擇仍舊在地圖壓蓋道路顯示或不顯示該P(yáng)OI點(diǎn)。

2　應(yīng)用實(shí)例

中國(guó)電子科技集團(tuán)第三十研究所廈門(mén)雅迅網(wǎng)絡(luò)股份有限公司自主導(dǎo)航電子地圖運(yùn)用P OI標(biāo)簽位置優(yōu)化處理方法，有效檢測(cè)出POI標(biāo)簽與道路的壓蓋現(xiàn)象，并做出有效調(diào)整，避免了覆蓋道路信息與復(fù)雜路口細(xì)節(jié)等關(guān)鍵信息，如廈門(mén)火車(chē)北站電子地圖和三榕公園電子地圖優(yōu)化前后效果對(duì)比，如圖3所示。廈門(mén)火車(chē)北站POI標(biāo)簽優(yōu)化前，默認(rèn)放置于POI的右側(cè)，由于該P(yáng)OI離主干道路十分接近，因而POI標(biāo)簽明顯壓蓋了主干道路，影響了用戶(hù)視覺(jué)體驗(yàn)（見(jiàn)圖3a）；優(yōu)化后，將POI標(biāo)簽調(diào)整到POI位置左側(cè)，由于左側(cè)是大片空白地圖背景，因而充分利用了地圖背景空間，優(yōu)化了顯示效果（見(jiàn)圖3 b）。三榕公園電子地圖元素較為復(fù)雜，其PO I標(biāo)簽在優(yōu)化前，三榕公園和杏林火車(chē)站均與主干道路壓蓋（見(jiàn)圖3c）；優(yōu)化后，將POI標(biāo)簽調(diào)整到背景區(qū)域，杏林火車(chē)站P OI標(biāo)簽無(wú)法避免與周邊道路產(chǎn)生壓蓋，但由于該P(yáng)OI屬于重要交通設(shè)施，在導(dǎo)航地圖中應(yīng)該保留，因而將其調(diào)整到P OI左側(cè)，讓其壓蓋低等級(jí)的道路，以保證高等級(jí)道路的顯示（見(jiàn)圖3d）。由于三榕公園電子地圖調(diào)整后，在其右側(cè)騰出了布局空間，因而可加入一個(gè)主干道“G319”的道路標(biāo)注，從而在整體上優(yōu)化了布局。優(yōu)化后的電子地圖在相關(guān)車(chē)載電子產(chǎn)品上得到廣泛應(yīng)用，取得了良好用戶(hù)口碑。

3　結(jié) 論

本文提出的電子地圖POI標(biāo)簽位置優(yōu)化處理方法，先進(jìn)行網(wǎng)格化減少道路數(shù)據(jù)的檢測(cè)量，再利用區(qū)間交集過(guò)濾模塊濾去大部分不可能產(chǎn)生壓

圖3　電子地圖POI標(biāo)簽位置優(yōu)化前后效果對(duì)比

蓋的道路，并把P OI標(biāo)簽與路段幾何關(guān)系限定在局部坐標(biāo)系的六種斜率關(guān)系范圍內(nèi)；利用相關(guān)點(diǎn)在坐標(biāo)系內(nèi)的斜率正負(fù)極性與絕對(duì)值關(guān)系有效檢測(cè)是否與道路壓蓋，每次檢測(cè)除了采用三次除法兩次減法運(yùn)算外，其余步驟均由計(jì)算速度最快的邏輯判斷指令完成，能有效提升電子地圖處理效率。但該方法存在一定局限性，即沒(méi)有對(duì)并行計(jì)算進(jìn)行優(yōu)化。隨著圖像處理平臺(tái)的高速發(fā)展，開(kāi)始出現(xiàn)CUDA等GPU高速處理平臺(tái)，需要進(jìn)一步研究在這些平臺(tái)上實(shí)施電子地圖繪制的快速優(yōu)化方法，并融合并行處理方法進(jìn)一步提高電子地圖的生產(chǎn)效率。

［1］於新國(guó)，蘇博文.城市公眾地圖服務(wù)系統(tǒng)興趣點(diǎn)數(shù)據(jù)采集與處理［J］.測(cè)繪與空間地理信息，2013（3）：73-74.

［2］周演匯，何立富.基于GIS交通事故管理系統(tǒng)的數(shù)據(jù)平臺(tái)設(shè)計(jì)與實(shí)現(xiàn)［J］.溫州職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2013（3）：54-57.

［3］邱儒瓊，鄭麗娜，李兵.基于MongoDB的電子地圖瓦片數(shù)據(jù)存儲(chǔ)和服務(wù)研究［J］.地理空間信息，2014（6）：155-157.

［4］葉常春，周興銘.一種支持多比例尺表示的地圖數(shù)據(jù)組織方法［J］.計(jì)算機(jī)學(xué)報(bào)，2004（7）：964-970.

［5］張鵬程，郗艷梅，任紅霞.矩形布局空間的處理及優(yōu)化研究［J］.溫州職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2011（1）：54-58.

［6］趙靜，羅興國(guó)，張汝云.一種新的電子地圖注記算法—格網(wǎng)法［J］.計(jì)算機(jī)工程，2008（7）：278-279.

［7］李永紅，華一新.一種快速判斷線(xiàn)段相交的方法［J］.測(cè)繪通報(bào)，2003（7）：30-31.

［8］楊必勝，孫麗.導(dǎo)航電子地圖的自適應(yīng)多尺度表達(dá)［J］.武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2008（4）：363-366.

［責(zé)任編輯：吳志榮］

Optimization of POI Tag Position of Digital Map

TU Yankai
（Xiamen Yaxon Network Co.， Ltd.， The 30th Research Institute of China Electronics Technology Group Corporation， Xiamen， 361008， China）

In order to reduce the coverage of POI tag on the road in drawing a digital map， a method is proposed to detect if the road will overlap the gland in POI tag map and adjust the tag position. The method of dividing the network data is implemented to reduce the detecting calculation cost， and the likely covering road unit is filtered to refine the road that is likely to create coverage with POI. A local coordinate system to determine the gradient relationship of the drawing elements is applied to detect if the POI tag covers the road and then adjustment is made accordingly. It is shown that the method efficiently increased the displaying effort of the digital map and improved user experience.

Digital map； POI tag； Position optimization； Coverage detect

P283

A

1671-4326（2015）02-0056-03

2015-01-29

廈門(mén)市科技計(jì)劃項(xiàng)目（3502Z20130008）

涂巖愷（1983—），男，福建永安人，中國(guó)電子科技集團(tuán)第三十研究所廈門(mén)雅迅網(wǎng)絡(luò)股份有限公司工程師，博士.