電子地圖POI標簽位置優化處理

涂巖愷（中國電子科技集團第三十研究所 廈門雅迅網絡股份有限公司，福建 廈門 361008）

電子地圖POI標簽位置優化處理

涂巖愷
（中國電子科技集團第三十研究所 廈門雅迅網絡股份有限公司，福建 廈門 361008）

為減少繪制電子地圖時POI標簽對道路的遮擋，提出一種檢測POI標簽與地圖背景中道路是否產生重疊壓蓋并調整標簽位置的方法。采用劃分網格數據的方法減少檢測計算量，對可能壓蓋路段進行過濾，提取可能與POI產生壓蓋的路段，再采用建立局部坐標系判斷繪制元素斜率關系的方法，檢測該POI標簽是否與道路產生重疊壓蓋，進而做出調整。應用實例表明，該方法能以較高的效率增強地圖顯示效果，提升用戶體驗。

電子地圖；POI標簽；位置優化；壓蓋檢測

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

0　引 言

電子地圖P O I標簽繪制是一個重要問題，良好的POI標簽繪制應盡量減少壓蓋地圖背景中的關鍵區域［1］。車載導航與定位應用［2］中道路是最關鍵信息，當道路邊緣的PO I標簽過多、壓蓋現象嚴重時，會影響道路顯示甚至覆蓋復雜路口細節等關鍵信息，從而影響用戶體驗。

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

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

圖1　電子地圖POI標簽壓蓋檢測流程

1.1網格劃分

計算地圖等級為0時的基準比例尺S0。地圖等級為0時將世界地圖劃分為2×2個網格，每個網格對應一張256×256分辨率地圖瓦片，則基準比例尺S0=360度/ （256×2）像素=0.703 125。

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

1.2路段過濾

進一步減少壓蓋檢測計算量，取路段的縱向/橫向坐標區間與POI標簽的縱向/橫向坐標區間，計算兩個區間的交集，交集不為空的路段為可能覆蓋路段，交集為空的路段不會與PO I相交覆蓋，對它們進行過濾。

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

（2）從全局緩存中取出網格內某一路段rm，m∈［1，M］。其中，M為路段數量，rm=［rm1（xm1，ym1），rm2（xm2，ym2）］，rm1和rm2為路段的兩個端點，（xm1，ym1），（xm2，ym2）為端點對應坐標。

（3）取路段的Y坐標區間Am=［ym1，ym2］（ym2≥ym1），取POI標簽的Y坐標區間B=［Ttop，Tbottom］，計算A與B的交集C=A∩B。

（4）如果C=ф，則該段道路肯定不會與POI標簽產生橫向重疊，將其過濾掉不進行檢測；如果C≠ф，則該路段可能與P OI標簽產生橫向重疊，將該路段rm取出，放入待檢測集Rh中。重復（2）直到該網格內所有路段均被過濾一遍。得到最終的待檢測道路集Rh，供斜率檢測步驟調用。

縱向壓蓋路段過濾原理及步驟與橫向壓蓋路段過濾原理及步驟相同。路段過濾流程所涉及運算為單坐標軸上的交集運算，每次過濾只需要進行兩次邏輯判斷。

1.3基于局部坐標系斜率關系的壓蓋檢測

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

圖2　局部坐標系斜率關系

計算rn2與rn1的斜率k1，TL與rn1的斜率k2，TR與rn1的斜率k3。檢測壓蓋現象的判斷流程如下：

If（k2，k3符號不同）

縱向斜率檢測的原理及步驟與橫向檢測的原理及步驟相同。通過斜率關系檢測，不僅能提供有效的壓蓋檢測，而且能通過速度較快的邏輯判斷代替兩條線段相交的求解方程組運算。從判斷流程看，只需要進行三次除法運算和兩次加法運算，其余均為計算機處理速度最快的邏輯判斷指令，這對于海量電子地圖處理來說能節省大量的時間。

1.4標簽調整

地圖中默認POI標簽位置T（Tleft，Ttop，Tright，Tbottom）位于POI坐標P（Px，Py）右方。當檢測到POI標簽位置T與道路產生壓蓋后進入標簽調整步驟，將標簽位置T 按PO I左方、上方、右方、下方的優先級調整。每一次調整位置后重新返回路段過濾步驟，如此迭代檢測是否與道路壓蓋，直至調整到不會產生壓蓋的位置繪出PO I標簽。如果所有位置調整后仍會產生壓蓋，則視該POI點的重要程度［8］選擇仍舊在地圖壓蓋道路顯示或不顯示該POI點。

2　應用實例

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

3　結 論

本文提出的電子地圖POI標簽位置優化處理方法，先進行網格化減少道路數據的檢測量，再利用區間交集過濾模塊濾去大部分不可能產生壓

圖3　電子地圖POI標簽位置優化前后效果對比

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

［1］於新國，蘇博文.城市公眾地圖服務系統興趣點數據采集與處理［J］.測繪與空間地理信息，2013（3）：73-74.

［2］周演匯，何立富.基于GIS交通事故管理系統的數據平臺設計與實現［J］.溫州職業技術學院學報，2013（3）：54-57.

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

［4］葉常春，周興銘.一種支持多比例尺表示的地圖數據組織方法［J］.計算機學報，2004（7）：964-970.

［5］張鵬程，郗艷梅，任紅霞.矩形布局空間的處理及優化研究［J］.溫州職業技術學院學報，2011（1）：54-58.

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

［7］李永紅，華一新.一種快速判斷線段相交的方法［J］.測繪通報，2003（7）：30-31.

［8］楊必勝，孫麗.導航電子地圖的自適應多尺度表達［J］.武漢大學學報：信息科學版，2008（4）：363-366.

［責任編輯：吳志榮］

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

廈門市科技計劃項目（3502Z20130008）

涂巖愷（1983—），男，福建永安人，中國電子科技集團第三十研究所廈門雅迅網絡股份有限公司工程師，博士.