地图 POI 聚合功能实践

介绍

在实现地图相关的业务功能时，我们常常会面临在不同的数量级别下展示地图兴趣点POI数据不同形态的需求，在大的地理范围上关注区域的统计值，在小范围的地理范围上关注POI的明细和操作，因此不可避免地会使用到地图POI的聚合功能。接下来来讨论二维平面地图的POI如何做聚合处理。

实现方案

本文实现的聚合功能，使用了网格质心算法作为点聚合的策略，四叉树用于快速查找。 实现步骤是这样的： 1.将地图当前的视图区域划分为若干网格，每个网格为大小相同的矩形；

2.遍历所有网格，对每个网格做以下操作：查找到每个网格内的所有POI，计算POI点的质心(x,y)，其中x为所有POI的x轴平均值，y为所有POI的y轴平均值，用质心点作为聚合点，替代原有的POI；

3.将这些聚合点渲染出来，根据其聚合的POI数量调整外观；

4.如地图视图有所改变（缩放、移动、改变尺寸），则重复步骤1 。

这个方案的难点在于如何快速找到每个网格范围内的所有POI。我们当然可以采用最机械的方法，即遍历每一个点，判断其是否在已经划定好的某个网格范围内，然而这种方法的执行时间会随着网格和POI数量的增加指数上升，并不适合处理海量POI。因此需要构造一棵四叉树提供快速查找的能力 。

构造四叉树

我们常用二叉树来查找和存储一维数据。对于地图POI（带xy坐标）来说是二维数组，可以采用四叉树对其进行存储和查找。

四叉树节点的特性：

1. 每个树节点需要包含的属性如下：

constructor(data, conf) {
    // 每个节点所指定的地址范围 xmin ymin xmax ymax
    this.extent =  new Extent(conf.extent)
    // 节点数据容量,超过该容量则会分裂成4个子节点
    this.bucketLimit = conf.bucketLimit || 10
    // 当前节点的深度，根节点深度为0
    this.deep = conf.deep || 0
    //存储的POI
    this.points = data
  }

2. 每个节点可以分裂为4个子节点，这四个子节点的范围extent分别为父节点的4个地理象限，即northWest（西北）northEast（东北）southWest（西南）southEast（东南）

3. 当前节点范围包含的POI点数量如果超过容量bucketLimit，并且节点深度deep没有超过最大深度，则分裂子节点

4.所有的POI点最终都会放在叶子节点中

图为基于现有数据构造出来的四叉树，从图中可以看到节点分裂越频繁的地方，POI越密集

查找网格内的POI

构造好了四叉树，就可以用它来查找单个网格Grid内的POI点，这是一个对四叉树递归遍历的过程，操作如下：

1. 从根节点开始，判断当前节点extent是否与网格Grid几何相交，如果相交，则进入步骤2

2. 当前节点有POI点（只有叶子节点有POI点），则遍历这些POI点，将处于Grid范围内的POI点存入数组Arr；否则进入步骤3

3. 如果当前节点有子节点（如果有的话必定是4个子节点），则按步骤1处理这些子节点

最终我们会得到一个Grid范围内所有POI点的数组Arr。每个网格范围内的POI点到手了，直接求取它们xy轴的平均值，就能得到这个网格质心聚合点的坐标，接下来就是在地图上的渲染工作。

代码层实现四叉树

我依据代码复用情况建了两个类

1.四叉树QuadTreeNode，提供树的构建和查找功能 findPoints(extent)
2.矩形范围Extent，这里的范围即有四叉树的地理范围，也有网格的地理范围，用于计算点和面，面和面之间的几何关系

QuadTreeNode

  /**
   * 查找指定范围内的坐标点
   * @param extent 指定范围
   * @returns {Array}
   */
  findPoints(extent) {

    if (!(extent instanceof Extent)) {
      extent = new Extent(extent)
    }

    let arr = []

    function travel(node) {

      if (node.isIntersects(extent)) {

        //如果当前四叉树节点有points，则将在extent范围内的points入栈
        if (node.points.length > 0) {
          node.points.forEach(point => {
            if (extent.within(point)) {
              arr.push(point)
            }
          })

        } else {
          const {northWest, northEast, southWest, southEast} = node

          if (northWest && northWest.isIntersects(extent)) {
            travel(northWest)
          }
          if (northEast && northEast.isIntersects(extent)) {
            travel(northEast)
          }
          if (southWest && southWest.isIntersects(extent)) {
            travel(southWest)
          }
          if (southEast && southEast.isIntersects(extent)) {
            travel(southEast)
          }
        }
      }
    }

    travel(this)

    return arr
  }
  
}

Extent

class  Extent{
  constructor(conf = {xmin: 0, ymin: 0, xmax: 100, ymax: 100}){

    this.xmin = conf.xmin
    this.ymin = conf.ymin
    this.xmax = conf.xmax
    this.ymax = conf.ymax
  }
  /**
   * 判断当前范围是否与指定范围相交
   * 如果两个矩形相交，则两个矩形中心点间的距离肯定小于两个矩形边长和的1/2
   * @param extent 指定范围
   * @returns {boolean}
   */
  intersects(extent) {

    const {xmin, ymin, xmax, ymax} = extent

    //x轴 两个矩形中心点距离 * 2
    let lx = Math.abs(this.xmax + this.xmin - xmin - xmax)
    //x轴 两个矩形边长和
    let bx = Math.abs(this.xmax - this.xmin + xmax - xmin)
    //y轴 两个矩形中心点距离 * 2
    let ly = Math.abs(this.ymax + this.ymin - ymin - ymax)
    //y轴 两个矩形x轴边长和
    let by = Math.abs(this.ymax - this.ymin + ymax - ymin)

    if (lx <= bx && ly <= by) {
      return true
    } else {
      return false
    }
  }
}

聚合功能的应用

1.解决重叠坐标点的选择问题 这是我非常想解决的问题，在实际项目中遇到的真实数据其实没有那么理想，很多情况下有部分POI数据因为地址不够详细或者定位api出错会导致坐标点一模一样，从而导致一堆点叠加在某个位置，鼠标操作只能取到最上方点的属性。既然实现了点聚合功能，那么可以配置缩小聚合的阈值，提取到所有叠加点的属性。

2.为热力图层的渲染提供基础数据 热力图其实可以看做点聚合的另一种展示方式，它所需要的源数据与点聚合非常类似（x坐标，y坐标，点的权值）。有了源数据，只要将做表单做一次地理坐标和平面坐标的转换，权值归一化，再渲染出热力图也是很简单的事。

3.海量数据的统计展示 还是文章开头提到的需求，大比例尺我要看POI的聚合数量，小比例尺我要看单个POI的属性明细。

优点和缺陷

1. 四叉树其实是个空间换时间的做法，和质心合并算法（求平均值）结合带来的有点就是计算速度快
2. 网格算法存在一定的误差，如果有一撮点切好处于两个网格的边界线上，算法会将这一撮点切成两个聚合点，不过这也不算什么大事

文章示例

地图POI聚合演示页面

GitHub源代码

参考文章

《地图兴趣点聚合算法的探索与实践》 这篇文章里面提到的算法解决方案更为详细生动，适合做更深入的研究