基于百度地图的标记点聚合算法研究

2013-10-08戴凤娇,肖林华,杨琭等

中国科技信息 2013年23期

引言

近年来，新技术的不断涌现，使得网页功能更加丰富。数字地图创造性地将传统地图与网页相结合，极大丰富和方便了人们的生活。从最初的“无缝”图片发展到现在的二维、三维，数字地图，以其特有的优势，得到了人们越来越多的青睐。

在用户体验上，数字地图为用户提供了一种新的信息查询方式，信息显示更精准全面，而查询结果通常都是以标记形式展现，用户的可视区域有限，如何在当前缩放级别下，利用最小的区域展示出最全面的信息，而又不产生重叠覆盖，就要利用到标记聚合技术，这也正是文章讨论的中心。

1. 百度Map API

一个开发地图应用的快捷方法是利用第三方的API。运用美国卫星航拍技术的Google地图，以及与交通部门合作的百度地图这两个地图服务商都为应用程序开发者提供了API。Google与百度的API文档相对其他服务商提供的文档来说，更完备、详尽、简洁，并且给出了很多学习示例，非常适合初学者学习开发。Google更精准，精确度达小数点后14位，而百度地图则是小数点后6位。但由于Google的ICP牌照已失效，因此理论上谷歌不能再向中国用户提供Google Map和Google Earth服务了，所以文章最终采用百度Map API实现。

为了减小计算量，以下讨论的三种算法只计算在视图区域内标记点，在视图区域外的不计算。

2. 基于视图矩形的标记点聚合

2.1 原理

将视图区域划分成若干矩形，矩形的大小视地图的缩放级别而定。将同一矩形内的标记点聚合成一个聚合标记，该聚合标记需记录被聚合的标记点个数或其他重要的统计信息。

2.2 实现

利用百度地图API中Map类的getBounds方法，获取视图区域的西南点及东北点的经纬度数据，并根据当前的缩放级别确定出矩形大小，综合这三个数据计算得出各个矩形的边界。

现矩形划分已定，需要解决标记点的经纬度到所在矩形区域的对应问题。有个直接的方法是将每一个标记点依次与视图中的矩形区域边界比较，直到有一个匹配的为止。这种方法简单，但费时，实验中采用一种时间复杂度比较低的算法。

首先将视图视为2维数组，按从上到下从左到右的顺序依次对矩形编号，以lngDiff代表一个矩形所跨域的经度，以latDiff代表一个矩形所跨域的纬度，以swp代表视图区域的西南点，利用Math库提供的下取整函数Math.floor，则点point所在的矩形行标为：Math.floor((nep.lat-point.lat)/latDiff)，列标为：Math.floor((point.lngswp.lng)/lngDiff)，这样就找到了标记点到矩形的对应关系。对应关系找到，标记点的分类与聚合就可以顺利完成。下一步就需要确定聚合点的显示位置。

聚合点在矩形的显示位置需要考虑当前的缩放级别，若缩放级数低，为避免聚合点重叠，可以将聚合点显示在矩形正中；若缩放级别高，则可选取矩形内某个标记点的位置为聚合点的显示位置，这个标记点可以简单的选取遇到的第一个标记点，也可以选取最靠近矩形中心的标记点，或者可以根据标记点内容，选取最重要的点。

实验中选取矩形中心为聚合点的目标位置。图1、图2分别为使用聚合算法前后标记点的显示情况，可以看出，聚合后的信息呈现更加简洁丰富。选取矩形中心为聚合点的显示位置，可以避免出现图3所示的情况，图3中由于[3]

[2]矩形及[3][3]矩形的聚合点位置随机选取为矩形内的某个标记点位置，而恰巧这两个标记点相邻，这就使得聚合点发生覆盖，信息无法读出。

3. 基于距离的标记点聚合

3.1 原理

基于矩形的标记点聚合实现简单，但不够灵活。现实应用中，标记点多与国家地区相联系，因此聚合时，常需要考虑标记点间的距离。

首先需要解决地球表面上两点间距离的计算问题。通常在不要求特别精确的情况下，将地球视为正球体，而实际上地球是个两头略扁的椭球体，因此实验中得出的距离是个近似距离。在球面几何中，定义正球体表面两点间的距离为经过这两点的大圆所在的劣弧长，如图4中弧AB即为A、B两点间的距离。以表示∠AOB的弧度，以R表示地球半径，则根据弧长公式得到：A、B两点间的距离为R。这样，选取某个标记点为基点，则其他点到基点的距离都可以得到。

以绝对距离划分标记点存在一个问题，在不同缩放级数下，同一距离对应不同的像素点数目，而视图区域的像素点数目是一定的，用户是以两点间的像素点数目来衡量点与点之间的距离，因此以间隔的像素点数目为标准设计聚合算法更合理（图4）。

图1 点聚合前

图2 点聚合后

图3 聚合点发生覆盖

3.2 实现

百度地图API默认使用墨卡托投影。选取经纬线原点为平面原点，即原点位置为赤道与0度经线相交的位置。在百度地图API中，以18级为平面坐标基准级数。已知某点的经纬度，利用BMap.MercatorProjection类可获取该点在18级下的平面像素坐标，在其他级别下的像素坐标可通过Math. floor (平面坐标×2zoom-18)换算得到，其中zoom代表当前缩放级别。至此，点的经纬度坐标到像素坐标转换完成，点的像素坐标已知，则点间的像素距离不难得到。