电子地图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—），男，福建永安人，中国电子科技集团第三十研究所厦门雅迅网络股份有限公司工程师，博士.