基于网格的地图标注避让算法

吕德奎++崔艳军

摘 要

本文在充分研究和比较了几种用于解决地图标注重叠的算法基础上，提出一种基于网格划分算法的思想方法来实现地图标注信息的自动避让，解决了地图点状目标因位置接近而出现的标注重叠的问题。

【关键词】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