地图POI标签遮挡问题解决方案

1. 背景介绍

小区周边配套，是每个购房人在购房时都会关注的关键信息，而地图是展示小区周边配套最有用的方法（没有之一），在房产领域被广泛使用。然而在实际场景下，小区周边有丰富的配套POI，各配套POI之间的距离往往非常小，POI标签之间经常会出现不同程度的遮挡现象，不能呈现POI的全部信息，也大幅降低了地图的观感体验。

本文提出了一种解决地图POI标签遮挡问题的方案，主要内容包括：遮挡问题复现与场景分析、二维碰撞检测算法简介、A-Star寻路算法简介、去遮挡解决方案。

2. 遮挡问题复现与场景分析

1. 问题复现

   如下图所示，5个POI之间的距离很近，并且POI对应的标签之间发生了严重的遮挡现象，甚至有2个POI的信息已经无法查看。在这种情形下，页面已经无法完整提供周边配套信息，较差的视觉体验也降低了吸引力。

2. 场景分析

   针对展现小区方位和周边配套信息的特定场景，经过分析后，总结出该场景的3个特点：

   根据场景特点，POI标签遮挡问题的解决步骤大致可以拆解成两个：一是合理排布POI标签，目的是防止标签之间发生遮挡而影响视觉体验，涉及的算法是二维碰撞检测算法；二是确定POI及其标签之间的引线，目的是避免混淆POI及标签间的对应关系，涉及的算法是A-Star寻路算法。

• 进行POI标签去遮挡时，对时效性和准确性要求较高，属于轻量级应用
• 只需关注小区周围固定距离的区域，且区域内只包含有限个需要关注的POI
• 地图的比例尺不发生变化，无用户操作，也不进行POI聚合与解聚合

结合上述内容可以进一步明确思路：以地图的JavaScript API为基础，请求后端去遮挡服务，依据返回结果在前端展示POI标签及引线。

3. 二维碰撞检测算法

碰撞检测算法可以分为2D碰撞检测和3D碰撞检测，主要应用于游戏中，2D碰撞检测如推箱子，3D碰撞检测如绝地求生。这里主要向读者介绍2D碰撞检测算法，首先是圆形间的碰撞检测，然后是水平矩形间的碰撞检测，以及圆形与水平矩形间的碰撞检测，最后引出任意两个凸多边形间的碰撞检测。

1. 圆形间的碰撞检测

   圆形间的碰撞检测是最简单的情形，下图展示了两个圆形之间的相对位置。

只需判断两个圆心之间的距离与两个半径之和的大小即可，判断条件如下：

math.sqrt(math.pow(circleA.x - circleB.x, 2) + math.pow(circleA.y - circleB.y, 2)) < 
circleA.radius + circleB.radius

2. 水平矩形间的碰撞检测

   排布POI标签位置时用到了水平矩形间的碰撞检测，下图展示了两个水平矩形之间发生碰撞的所有可能情形。

rect1.x < rect2.x + rect2.width and
rect1.x + rect1.width > rect2.x and
rect1.y < rect2.y + rect2.height and
rect1.y + rect1.height > rect2.y

3. 圆形与水平矩形间的碰撞检测

   圆形与水平矩形间的碰撞检测相对复杂，核心思想是找出矩形上离圆心最近的点，然后判断该点与圆心的距离是否小于圆的半径，若小于则为碰撞。

   那么应当如何确定矩形上距离圆心最近的点呢？首先是轴：

• 如果圆心在矩形的左侧（if circle.x < rect.x），那么 closestPoint.x = rect.x

• 如果圆心在矩形的正上或者正下方（else），那么 closestPoint.x = circle.x。

同理，对于轴：

• 如果圆心在矩形的上方（if circle.y < rect.y），那么 closestPoint.y = rect.y。
• 如果圆心在矩形的下方（elif circle.y > rect.y + rect.h），那么 closestPoint.y = rect.y + rect.h。
• 如果圆心在矩形的正左或者正右侧（else），那么 closestPoint.y = circle.y。

通过上述方法即可找出矩形上距离圆心最近的点，接着可以计算两点间距离并比较大小。

4. 任意凸多边形间的碰撞检测

   针对于以上3种情形，如果形状发生旋转或者变为不规则凸多边形，那么应该如何检测两个形状之间是否发生碰撞？

   这里介绍一种更一般的方法来判断任意两个凸多边形之间是否发生碰撞——分离轴定理（SAT）。分离轴定理的基本含义：若两个凸多边形不相交（碰撞），则一定能找到一条投影轴使得两个凸多边形的投影不相交。

   分离轴定理本身的优势和劣势比较明显，优势是快速、准确，劣势是只适用于凸多边形。

   分离轴定理主要涉及二维向量之间的计算，其中一个重要的概念就是投影轴。然而在程序中根本无法找到所有的投影轴，那究竟如何确定投影轴呢？实际上投影轴的数量与凸多边形的边数保持一致即可，具体地，可以选择凸多边形边缘向量的法向量作为投影轴，原因在于凸多边形在这些轴上具有极值。投影轴计算过程如下图所示：

下图展示了分离轴定理的计算过程，外围带有编号的线代表投影轴，该编号与凸多边形边的编号对应。

在每个投影轴上分别计算两个凸多边形对应的投影值，并统计最大值和最小值，进而得到两个凸多边形投影的数值区间。如果在某条轴上，两个凸多边形的投影数值区间未发生重叠，则证明两个图多边形未发生碰撞。

4. A-Star寻路算法

A-Star算法是一种求解最短路径的最有效的启发式直接搜索方法，具有较好的性能和准确度，多用于机器人动态寻路，或者游戏中人物移动的路径规划。这里对A-Star算法的基本原理和运行流程进行简要介绍，并给出例子帮助读者理解。

A-Star算法形式化表示为：，其中：

• 表示从初始状态经由状态n到达目标状态的代价估计
• 表示状态空间中从初始状态到状态n的实际代价
• 表示从状态n到目标状态的最佳路径的估计代价

为了简便，这里选择曼哈顿距离作为算法中的代价估计函数，同时规定水平和竖直方向移动代价为10，对角方向移动代价为14。A-Star算法还涉及到几个名词，分别是：起点、终点、、、节点。

在详细描述A-Star算法的运行步骤之前，先来了解一下算法流程：

“

1. 把起点加入，
2. 重复如下过程：
• 若它是障碍点或者它在中，跳过它，否则做如下操作：
• 若它不在中，把它加入 ，并且把当前节点设置为它的父亲，记录该节点的、和值
• 若它已经在中，检查由当前节点到达它那里是否更好，用值作参考，更小的值表示这是更好的路径。若是这样，把它的父亲设置为当前节点，并重新计算它的和值
• 遍历，查找值最小的节点，把它作为当前要处理的节点，
• 把这个节点移到，
• 对当前节点的8个相邻节点的每一个节点：
3. 程序停止，当满足如下条件：
• 把终点加入到了中，表明路径查找成功
• 为空，表明路径查找失败
4. 路径查找成功后，保存路径：从终点开始，每个节点沿着节点移动至起点

以下图为例，绿色格子代表起点，红色格子代表终点，中间蓝色格子代表障碍点：

1. 从起点开始，将其入到。中会逐渐加入更多的点，这些点可能在最终的路径中，也有可能不在。可以看成由待检查的点组成的列表。

2. 查看与起点相邻的点，忽略障碍点以后，将剩余所有的相邻点加入到中，并将这些点的节点设置为起点。随后将起点放入中。

3. 继续探索，需要从中选择一个值最小的点，从下图中可知起点右侧的点具有最小的值40，将该点加入到中。查看当前点的相邻点，发现起点在中，除了不可达到的点以外，其余均在中。检测经过当前点到达这些点的代价是否更小（用值做参考），若更小则将对应点的节点更换为当前点，否则不进行操作。

以下动画直观地展现了A-Star算法的运行过程，其中蓝色代表起点，红色代表终点，灰色表示不可到达的点，青色代表加入到的点，绿色代表最短路径中的点，橘黄色代表加入到的点。

5.去遮挡解决方案

POI标签去遮挡的目标是：标签之间不遮挡，标签不压盖POI，POI与标签之间要对应。

为了清晰快速地介绍解决方案，这里使用OpenCV和Numpy在Python环境下模拟真实场景并进行相关计算。规定页面尺寸为，页面内包含5个POI，标签的形状为水平矩形。不失一般性，5个POI的图像坐标通过程序随机生成，分别为：、、、、。

实现步骤：

1. 合理排布POI标签

   该步目的是利用策略避免标签之间发生遮挡，并且保证标签不压盖POI，主要用到了矩形碰撞检测算法。该策略的简要描述：获取质心，计算半径，以为圆心为半径画出圆，在上取等分点，等分点个数与POI点个数一致，最后根据等分点的三角函数值并结合碰撞检测确定标签的最终位置。具体描述如下：

• 根据5个POI的图像坐标，下图模拟了POI在地图中的相对位置

    def get_centroid(points):
         """求点序列的质心"""
         xs, ys = [], []
         for p in points:
             xs.append(p[0])
             ys.append(p[1])
         x_ = int(np.mean(xs))
         y_ = int(np.mean(ys))
         return [x_, y_]

    def euclidean_dis(p_start, p_end):
         """计算两点间欧式距离"""
         dis = np.linalg.norm(np.array(p_start) - np.array(p_end))
         return dis

• 以为圆心，为半径，利用OpenCV在图中画圆，效果如下所示：

• 以质心为原点构建直角坐标系，从圆和轴正半轴的交点开始，顺时针依次计算等分点坐标，计算代码如下：

      def get_equal_points(centroid, points, radius):
           """计算等分点"""
           equal_points = []  # 等分点
           trig_values = []  # 三角函数值
           for i in range(len(points)):
               cos = math.cos(2 * math.pi * i / len(points))
               sin = math.sin(2 * math.pi * i / len(points))
               x = int(centroid[0] + radius * cos)
               y = int(centroid[1] + radius * sin)
               equal_points.append([x, y])  # 图像坐标系
               trig_values.append([cos, sin])
           return equal_points, trig_values

• 根据等分点的三角函数值，判断该等分点应该属于矩形标签上的哪个点，并进一步确定矩形标签的初始位置，代码如下：

      def get_rectangles(equal_points, trig_values):
           """
           根据等分点计算矩形框位置
           """
           rectangles = []
           for [x, y], [cos, sin] in zip(equal_points, trig_values):
               if abs(sin - 0.) < 1e-9 and abs(cos - 1.) < 1e-9:
                   # 该点为左侧短边中点
                   delta_x = 0
                   delta_y = - int(DeblockConfig.label_H / 2)
                   tl_p = [x + delta_x, y + delta_y]
                   br_p = [x + delta_x + DeblockConfig.label_W, y + delta_y + DeblockConfig.label_H]
                   rectangles.append(tl_p + br_p)
                   continue
               if abs(sin - 1.) < 1e-9 and abs(cos - 0.) < 1e-9:
                   # 该点为上侧长边中点
                   delta_x = - int(DeblockConfig.label_W / 2)
                   delta_y = 0
                   tl_p = [x + delta_x, y + delta_y]
                   br_p = [x + delta_x + DeblockConfig.label_W, y + delta_y + DeblockConfig.label_H]
                   rectangles.append(tl_p + br_p)
                   continue
               if abs(sin - 0.) < 1e-9 and abs(cos + 1.) < 1e-9:
                   # 该点为右侧短边中点
                   delta_x = - DeblockConfig.label_W
                   delta_y = - int(DeblockConfig.label_H / 2)
                   tl_p = [x + delta_x, y + delta_y]
                   br_p = [x + delta_x + DeblockConfig.label_W, y + delta_y + DeblockConfig.label_H]
                   rectangles.append(tl_p + br_p)
                   continue
               if abs(sin + 1.) < 1e-9 and abs(cos - 0.) < 1e-9:
                   # 该点为下侧长边中点
                   delta_x = - int(DeblockConfig.label_W / 2)
                   delta_y = - DeblockConfig.label_H
                   tl_p = [x + delta_x, y + delta_y]
                   br_p = [x + delta_x + DeblockConfig.label_W, y + delta_y + DeblockConfig.label_H]
                   rectangles.append(tl_p + br_p)
                   continue
               if sin > 0. and cos > 0.:
                   # 该点为左上顶点
                   delta_x = 0
                   delta_y = 0
                   tl_p = [x + delta_x, y + delta_y]
                   br_p = [x + delta_x + DeblockConfig.label_W, y + delta_y + DeblockConfig.label_H]
                   rectangles.append(tl_p + br_p)
                   continue
               if sin > 0. and cos < 0.:
                   # 该点为右上顶点
                   delta_x = -DeblockConfig.label_W
                   delta_y = 0
                   tl_p = [x + delta_x, y + delta_y]
                   br_p = [x + delta_x + DeblockConfig.label_W, y + delta_y + DeblockConfig.label_H]
                   rectangles.append(tl_p + br_p)
                   continue
               if sin < 0. and cos > 0.:
                   # 该点为左下顶点
                   delta_x = 0
                   delta_y = -DeblockConfig.label_H
                   tl_p = [x + delta_x, y + delta_y]
                   br_p = [x + delta_x + DeblockConfig.label_W, y + delta_y + DeblockConfig.label_H]
                   rectangles.append(tl_p + br_p)
                   continue
               if sin < 0. and cos < 0.:
                   # 该点为右下顶点
                   delta_x = -DeblockConfig.label_W
                   delta_y = -DeblockConfig.label_H
                   tl_p = [x + delta_x, y + delta_y]
                   br_p = [x + delta_x + DeblockConfig.label_W, y + delta_y + DeblockConfig.label_H]
                   rectangles.append(tl_p + br_p)
                   continue
       
           for rect in rectangles:
               if min(rect[0::2]) < 0 or max(rect[0::2]) > DeblockConfig.w:
                   return False, None
               if min(rect[1::2]) < 0 or max(rect[1::2]) > DeblockConfig.h:
                   return False, None
       
           return True, rectangles

• 依据等分点的顺序，对首末两个矩形标签进行碰撞检测，确定标签最终的位置。利用OpenCV在图上画出等分点和矩形标签，效果如下：

上述步骤最终给出了矩形标签的位置，在圆上取等分点来确定标签位置的方法避免了标签压盖圆内的POI点，另外等分点与与矩形标签的对应策略也尽可能地减少了碰撞检测算法执行的次数，只需进行一次碰撞检测即可。

2. 确定POI及其标签之间的引线

   该步目的是利用策略画出POI与矩形标签之间的引线，明确POI与矩形标签之间的对应的关系，主要用到了A-Star寻路算法。

   按照策略对矩形标签重新排布，又在POI坐标已知的情况下，应该如何确定POI与矩形标签的对应关系呢？这里选择的策略是：距离质心最远的POI点与距离其本身最近的一个矩形标签组合，接着按照相同的规则组合剩余的POI点和矩形标签。

   确定了POI与矩形标签之间的对应关系后，也就意味着确定了路径的起点和终点，因此可以应用A-Star寻路算法，经过A-Star计算得到的路径即为引线轨迹。

   利用OpenCV在图中画出A-Star算法得到的轨迹后，可以看到POI与矩形标签之间通过引线连接，效果如下：

下图展示了实际场景中的一个badcase，可以结合下图说明该解决方案的优缺点：

• 优点：

  原理简单，运算速度快

  标签位置准确，POI与标签的对应关系明确

• 缺点：

  POI与标签之间的距离可能较远，视觉体验不够

  引线之间距离较近的情况下，不易于区分

6. 结语

以上全部内容即为地图页面中POI标签去遮挡的解决方案，以及所用到算法的详细介绍。经过标签去遮挡操作后，地图画面的视觉体验有了大幅提升，并且能够传递完整的POI信息。但是POI标签的排布策略仍有改进空间，如采用分而治之的思想来对POI和标签进行组合。在以后的工作中，会针对上述想法对地图页面中的标签展示作进一步的改进和完善。

Ref.

1. 知乎问答 - POI标签注记：https://www.zhihu.com/question/21306785

2. POI聚合与解聚合：https://segmentfault.com/a/1190000023059160

3. JavaScritp API - 点聚合：https://lbsyun.baidu.com/index.php?title=jspopular3.0/guide/conflux

4. 常见的2D碰撞检测：https://aotu.io/notes/2017/02/16/2d-collision-detection/index.html

5. A-Star算法详解：https://blog.csdn.net/hitwhylz/article/details/23089415