呂德奎++崔艷軍

摘 要

本文在充分研究和比較了幾種用于解決地圖標注重疊的算法基礎(chǔ)上，提出一種基于網(wǎng)格劃分算法的思想方法來實現(xiàn)地圖標注信息的自動避讓，解決了地圖點狀目標因位置接近而出現(xiàn)的標注重疊的問題。

【關(guān)鍵詞】WebGIS 地圖標注 網(wǎng)格化 自動避讓

公安、民航等領(lǐng)域基于地圖的動態(tài)點目標不但眾多，而且每個目標的標注攜帶著非常重要的信息，實時性高。如何控制地圖點目標的注記的位置和布局，以及解決注記之間的沖突和壓蓋問題，是解決注記自動配置問題的重點和關(guān)鍵。本文在充分研究和比較了幾種用于解決地圖標注重疊的算法基礎(chǔ)上，提出一種基于網(wǎng)格劃分算法的思想方法來實現(xiàn)地圖標注信息的自動避讓，解決了地圖點狀目標因位置接近而出現(xiàn)的標注重疊的問題，并通過實驗驗證可以很好的解決這類問題。

1 基本實現(xiàn)思想

1.1 聚合與解聚思想

聚合是在一定的地圖比例尺下，當(dāng)兩個目標在地圖上的屏幕像素小于某個閥值時，就把兩個目標合并成一個，并通過更改圖標等形態(tài)用于標記說明，依次類推兩兩目標的屏幕間距直至所有的目標均符合閥值要求。解聚剛好相反，當(dāng)因為比例尺發(fā)生變化或動態(tài)目標因地理位置發(fā)生移動時，需要重新按照預(yù)設(shè)閥值進行聚合計算，并把大于某個閥值的所有目標進行還原。聚合與解聚，是地圖綜合的其中一種方法，主要解決地圖中點要素很多時候的表示困難的問題。

1.2 碰撞自動避讓思想

碰撞檢測與自動避讓的中心思想是“放”，把重要的實時信息或臨近的目標明確的在地圖上區(qū)分開來，用于最清晰、直觀的形式展現(xiàn)給指揮人員或管理人員。比較著名的算法有物理松弛法、整型規(guī)劃及連續(xù)梯度下降法等。

1.3 比較分析

聚合和避讓是地圖客戶端點要素展現(xiàn)的兩種常見形式，聚合主要用途是解決地圖客戶端大量點標注渲染時遇到的性能瓶頸，避讓主要的用途為解決客戶端重要目標信息顯示混亂的問題。

2 基于網(wǎng)格的自動避讓算法設(shè)計

點標注的位置可以在點的右邊、左邊或者上面，首先判斷右邊的位置是否可以標注（標注需要占用網(wǎng)格是否可用），如不可標注則判斷左邊的網(wǎng)格，同理判斷上面的網(wǎng)格。

我們采用網(wǎng)格索引類似的方式，根據(jù)文字大小計算出一個網(wǎng)格尺寸（保證一個文字占用的網(wǎng)格數(shù)目是定值），建立一個屏幕網(wǎng)格索引（采用的是屏幕坐標）。將所有的地圖要素的坐標轉(zhuǎn)換從實際坐標轉(zhuǎn)換為屏幕坐標。因為標注不能壓蓋點狀要素，所以計算出所有點狀要素所占據(jù)的網(wǎng)格，并將這些網(wǎng)格標記為不可標注。

本節(jié)采用網(wǎng)格劃分算法的思想來實現(xiàn)碰撞檢測并按照避讓規(guī)則庫實現(xiàn)地圖標注的自動避讓，本文設(shè)計的地圖標注包括：文本信息和圖標符號兩種組成。

2.1 網(wǎng)格劃分設(shè)計

把整個地圖顯示客戶端屏幕分成大小相等的網(wǎng)格，根據(jù)標注信息多少計算出一個網(wǎng)格占多少像素，并建立屏幕網(wǎng)格索引。本文采用的網(wǎng)格是50像素*50像素（gridHeight，gridWidth），當(dāng)?shù)貓D點標注在地圖上顯示時，標記所在網(wǎng)格為已被標注占用。

數(shù)據(jù)結(jié)構(gòu)采用二維數(shù)組形式，使用與屏幕網(wǎng)格一致的二維數(shù)組來標記其對應(yīng)的網(wǎng)格是否可標注。設(shè)二位數(shù)組為Grids=[maxRowNum][maxColNum]，其中maxRowNum為屏幕網(wǎng)格最大行數(shù)，maxColNum為屏幕網(wǎng)格最大列數(shù)，求值為公式1和2。如當(dāng)行1，列2被占用時，則Grids[1][2]=true。

maxRowNum=[mapScreenHeight/gridHeight]

（1）

maxColNum=[mapScreenWidth/gridWidth]

（2）

2.2 自動避讓設(shè)計

自動避讓是以當(dāng)前坐標為中心如（1，1），如果該網(wǎng)格已被其他標注占用，則在下一個外圈進行所搜，直至遍歷到未被占用的網(wǎng)格為止，并進行標記以及標注偏移設(shè)置（offset）。

首先需要把點符號的經(jīng)緯度坐標（lng，lat）轉(zhuǎn)換為屏幕坐標（sx，sy），轉(zhuǎn)換函數(shù)設(shè)f（x）；然后得到當(dāng)前點所在的網(wǎng)格行列號（curRowNum，curColNum），判斷當(dāng)前網(wǎng)格是否被占用，如果被占用則在下一個外圈進行遍歷查詢每個網(wǎng)格是否被占用，依次類推，直至沒有查找到不被占用的為止。

2.3 動態(tài)目標避讓

對于動態(tài)變化的GPS、北斗等來源的目標，地圖標注的自動避讓相對頻繁，如果采用每次全部刷新的機制，實現(xiàn)起來簡單，但是會導(dǎo)致屏幕閃爍以及耗費內(nèi)存。本文對動態(tài)目標采用局部刷新的算法，采用先把動態(tài)目標上一個占用的網(wǎng)格進行清零，然后以新的網(wǎng)格為原點進行遍歷，并設(shè)置偏移量。

3 結(jié)束語

地圖點注記是WebGIS地圖的主要內(nèi)容之一，是上層業(yè)務(wù)應(yīng)用的最多的功能，注記位置的選擇是否恰當(dāng)，排列是否美觀，將直接影響到電子地圖的清晰易讀性和業(yè)務(wù)應(yīng)用價值。當(dāng)航空管制人員、公安指揮人員等在指揮調(diào)度時，面對動態(tài)多變的環(huán)境，簡易直觀地在地圖上看到相關(guān)信息尤為重要。本文提出的基于網(wǎng)格的算法思想來解決地圖點標注沖突與重疊的問題，具有一定的應(yīng)用前景。

參考文獻

[1]樊紅等.地圖線狀要素自動注記的算法設(shè)計與實現(xiàn)[J].測繪學(xué)報，1999（01）：86-89.

[2]游漣，何宏星.地圖點狀符號及其注記的自動配置[J].測繪學(xué)報，1993，22（04）：304-308.

[3]馬超等.優(yōu)化的標牌自動避讓算法[J].計算機工程與設(shè)計，2012，33（09）.

[4]趙火軍.基于格網(wǎng)法的標牌避讓算法在雷達模擬機的應(yīng)用[J].中國民航飛行學(xué)院學(xué)報，2007（03）：20-24.

作者單位

中國電子科技集團公司第二十八研究所 江蘇省南京市 210007