基于網(wǎng)格的地圖標(biāo)注避讓算法

呂德奎++崔艷軍

摘 要

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

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

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

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

1.1 聚合與解聚思想

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

1.2 碰撞自動(dòng)避讓思想

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

1.3 比較分析

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

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

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

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

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

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

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

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

maxRowNum=[mapScreenHeight/gridHeight]

（1）

maxColNum=[mapScreenWidth/gridWidth]

（2）

2.2 自動(dòng)避讓設(shè)計(jì)

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

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

2.3 動(dòng)態(tài)目標(biāo)避讓

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

3 結(jié)束語(yǔ)

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

參考文獻(xiàn)

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

[2]游漣，何宏星.地圖點(diǎn)狀符號(hào)及其注記的自動(dòng)配置[J].測(cè)繪學(xué)報(bào)，1993，22（04）：304-308.

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

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

作者單位

中國(guó)電子科技集團(tuán)公司第二十八研究所 江蘇省南京市 210007