在线地图的点聚合算法

1) 基于网格的点聚合算法（Grid-based Clustering）

原理：将地图划分成指定尺寸的正方形（每个缩放级别不同尺寸），然后将落在对应格子中的点聚合到该正方形中（正方形的中心），最终一个正方形内只显示一个点，并且点上显示该聚合点所包含的原始点的数量。

优点：运算速度较快，每个原始点只需计算一次，没有复杂的距离计算。

缺点：有时明明很相近的点，却仅仅因为网络的分界线而被逼分开在不同的聚合点中，此外，聚合点的位置采用的是该网格的中心，而非该网格的质心，这样聚合出来的点可能不能较精确反映原始点的信息。

2) 基于距离的点聚合算法（Distance-based Clustering）

原理：根据点与点之间的距离进行聚合，对每个点进行迭代，若被迭代的点在某个已有聚合点的指定阈值的距离范围内，那么这个点就聚合到该点，否则则新建一个聚合点，如此循环，但聚合后的点的坐标依然是该聚合点创建时的第一个点的坐标位置。

优点：聚合点较精确的反映了所包含的原始点要素的位置信息。

缺点：需要计算点与点之间的距离，计算相对复杂。

3) 基于方格和距离结合的点聚合算法（详细）

原理：初始时没有任何已知聚合点，然后对每个点进行迭代，计算一个点的外包正方形，若此点的外包正方形与现有的聚合点的外包正方形不相交，则新建聚合点（区别于前面基于直接距离的算法，这里不是计算点与点间的距离，而是计算一个点的外包正方形，正方形的变长由用户指定或程序设置一个默认值），若相交，则把该点聚合到该聚合点中，若点与多个已知的聚合点的外包正方形相交，则计算该点到到聚合点的距离，聚合到距离最近的聚合点中，如此循环，直到所有点都遍历完毕。每个缩放级别都重新遍历所有原始点要素。

此方法可以算是基于方格与基于距离的算法的一个结合算法。

优点：运算速度相对较快，每个原始点只需计算一次，可能会有点与点距离计算，聚合点较精确的反映了所包含的原始点要素的位置信息。

缺点：速度不如完全基于方格的速度快等。

使用此算法的在线地图：Google Maps。

以下是Google给出的一个基于方格距离的点聚合示意图：

步骤示例：

a) 默认输入的数组的顺序是如图 7 – 基于方格距离的点聚合算法（原始点要素）所示的字母顺序。

b) 初始计算，从A开始迭代，此时并没有任何聚合点，则在A的位置生成一个聚合点（设为A1），A1的位置与A相同。

c) 迭代到B，如图 8所示，由于B的外包正方形与已有聚合点A1的外包正方形相交，所以B应聚合到A1中，新聚合后的聚合点的位置依然保持在A1原来的位置（这主要是因为若采用A与B的质心会花费客户端较大的计算量，这在原始点要素数量较大时影响较大）。

d) 迭代到C，由于C的外包正方形不与现有的聚合点A1相交（目前只有A1一个聚合点），因此C需要新建一个新的聚合点（设为C1）。

e) 迭代到D，类似于B，D与A1聚合，聚合后依然为A1。

f) 迭代到E，新的问题来了，E的外包正方形同时与A1和C1相交，这时需判断E到A1、C1的距离，并将E聚合到距离近的那个聚合点中，这里E到C1更近，于是E聚合到了C1中。

g) 剩下的如此迭代，直至完毕。

4) 基于距离和最少点数量限制的点聚合算法

原理：此算法相当于先执行完基于距离的点聚合算法，然后再进行一次聚合点的分解。每个聚合点成立的条件是所聚合的原始点要素的数量应大于程序默认或用户指定的最少数量限制，否则将解散这个聚合点。

此方法甚至不能算是一个独立的算法，因为此算法的前后相互独立，类比的，其实也可以建议一种“基于网格和最少点数量限制”的点聚合算法。

优点：聚合后的显示相对精确，对显示的控制更灵活。

缺点：运算速度相对较慢，因为本身基于距离的点聚合算法就已经是相对较慢了，再加上后期根据最少数量限制的阈值进行点聚合分解，速度更慢。