基于網格的地圖標注避讓算法

呂德奎++崔艷軍

摘 要

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

【關鍵詞】WebGIS 地圖標注 網格化 自動避讓

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

1 基本實現思想

1.1 聚合與解聚思想

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

1.2 碰撞自動避讓思想

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

1.3 比較分析

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

2 基于網格的自動避讓算法設計

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

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

本節采用網格劃分算法的思想來實現碰撞檢測并按照避讓規則庫實現地圖標注的自動避讓，本文設計的地圖標注包括：文本信息和圖標符號兩種組成。

2.1 網格劃分設計

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

數據結構采用二維數組形式，使用與屏幕網格一致的二維數組來標記其對應的網格是否可標注。設二位數組為Grids=[maxRowNum][maxColNum]，其中maxRowNum為屏幕網格最大行數，maxColNum為屏幕網格最大列數，求值為公式1和2。如當行1，列2被占用時，則Grids[1][2]=true。

maxRowNum=[mapScreenHeight/gridHeight]

（1）

maxColNum=[mapScreenWidth/gridWidth]

（2）

2.2 自動避讓設計

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

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

2.3 動態目標避讓

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

3 結束語

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

參考文獻

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

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

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

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

作者單位

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