（施工中）
在使用各家地图API的时候有时候我们会遇见一种情况：地图上的标志点太密，相互之间离的太近，点击的时候想要的点点不到，或者索性密密麻麻一片icon根本看不到。
在Google等大型厂商那边，解决这个问题可以通过专业的GIS算法进行后台筛选来解决（比如坐标点索引，或者动态分块索引）。但是如果这些地图点是客户或者第三方那边生成的无法后台筛选怎么办？或者如果你就是想实现一种很酷炫的把同一座建筑物里相同的点合并到一起的UI效果怎么办？这里实现了一种基于扫描线算法的相近点合并算法，具体原理如下：
一、基本合并
首先我们得到一系列任意的点，记为array[]：
然后将这些点按纬度或经度坐标增序排序（这里默认按纬度）：
现在我们假想有一条线由上到下扫过整个屏幕：
这种思考方式就称为扫描线算法。属于计算几何领域中的一个小知识。
现在以点1这种情形来思考，如果要将“距离过近”的点进行合并，那么我们就设定一个过近的距离range，即藏青色的范围。根据藏青色圈内的所有点生成一个新点并予以纪录，然后结束这一点的搜索，令扫描线下移到点2。重复这种逻辑就可以把距离过近的点全部合并成一个点。
由于需要遍历每个点，不考虑之前排序过程，这一层循环的时间复杂度为O(n)，n = array.length：
此时进行一些必要的简化操作：
1.由于绝大部分情况下需要在各家地图API上呈现的icon的范围是长矩形，加上简化计算的考虑，故不计算直接的距离，改为分别计算经纬度坐标的差，即圆形区域改为高margin_height，宽margin_width的矩形区域。
2.在扫描线下扫的过程中，第a个点会对所有下标大于a的点进行判断。因此对于点b(b>a)，实际已经计算过a和b之间的关系，无需再向上回扫小于b的部分。
综上所述，此子循环实际需要考虑的点简化为下图中青色部分。若遍历整个点集合，其计算复杂度为O(n)，和上一层循环嵌套复杂度变为O(n^2)，因此需要优化。
此时将这一子循环分为经度和纬度分别计算：
计算纬度时，实质上是要找到青色部分下边际的low_bound_lng，利用二分查找法，易知这一部分的时间复杂度为O(log n)。
计算经度时，利用纬度查得的low_bound在array的（i,low_bound_lng）区间上遍历，时间复杂度最坏为O(n)，若要优化这一部分效率，可建立根据经度递增排序的索引集合，然后利用点i的经度查找经度的low_bound_lat，时间复杂度同样为O(log n)，综上，总的时间复杂度为O(n * log n)。
得到青色区域内的点之后，将所有点放到同一个Set集合中，即图中黑色圈的部分。
重复这一流程直到扫描线扫过所有点。
二、再调度已被合并的点
所有点合并完成后的结果如图所示：
从图中易得知，根据以上逻辑，可能会导致将同一个或者多个点归纳到不同的Set中，从而导致最后返回的set总长度与原长度不一致。容易推导的是，若点7和点8都与点9“过近”（在Android UI上表示为Icon相互遮挡）那么实际上点7，8，9可以合并为同一点。
为了实现这种再合并效果，引入一个Map结构，并在每一次将一个点添加到新的合并点时，以点作为key,以合并后的点作为value，放入map以供之后查找：
（补图）
自此，通过map，在每次尝试将青色区域的点加入到当前合并区时，检查此点是否已经被添加，若已经被添加，则找到其所属的合并区，尝试将整个合并区与当前合并区合并。
（补图）
此时又产生一个新问题，如果认为合并区的连锁合并过多，导致过多的点被合成一个点，应该如何处理呢？例如上图的所有点都被合并成了一个大合并区，这种逻辑可能不符合一些情况下的需求。
此时需要引入一个最大合并区半径的概念。定义如下：
此算法生成的所有合并区，其最左边与最右边的点的距离小于最大合并区半径，其最上边与最下边的点之间的距离小于最大合并区半径。当然，这两个半径可以根据需要设置为不同的值。即下图中绿色框的范围。
接下来我们在算法逻辑中增加一些判断来满足这个最大合并区的条件。注意：接下来的逻辑并不是唯一解，只是最快的，也存在更好或者基于其他UI需求的解决方案。
（补3图）
（补分割和判断合并区的逻辑阐述）
算法逻辑方面的介绍就到这里。此时还有一个小问题可以在体验上优化。
三、关键代码解释和SDK化封装
（补代码）
接下来为了便于用户使用，这里建立了一系列泛型和一个接口用于新手开发人员直接快速调用：
（补代码）
填入算法方法的数组里的对象T需要实现LocationComparable接口，它是Comparable<T>的继承。可在返回的Set<CombinedPoint<T>>中获取所有的CombinedPoint（即合并区），通过调用CombinedPoint的getAll方法获取所有属于此点的T对象。若不会实现compareTo方法，源代码的ExampleCompare中已经写好复制粘贴就好。
CombinedPoint的具体坐标，约定为其包括所有T对象坐标的最大与最小值中点。
代码效率方面一些思考：
1.如果array[]大部分情况比较小（低于 256个）可以将源代码中的hashmap改为arraymap，如果数量特别巨大（超过1000个）可以尝试SparseArray。当然，后者的情况往往你的view方面内存会先崩溃掉。
2.如你所想，可以使用某种条件判断直接令i跳到青色区域中最下面的点（即在某个合适的地方加一行i = low_bound;）以节省查找时间，目前还在思考完善中。（某点接近点i+1却不接近点i+2的场合该如何处理？比较复杂）
3.扶额，由于这里使用JDK为java 7不支持interface内声明default方法，将来更新到java 8后会直接实现compareTo以省略手动实现。另外源代码暂时没有排序经度坐标，采用遍历的方式，因为需要重新设计LocationComparable。
有问题请在github下发Issue咨询。为了让更多的人看懂，请尽量用英语，中文或日语问题只回答比较关键的。
代码地址:https://github.com/areyoucrazytom/maptool
接下来计划实现分段加载地图点时新的点集如何添加到现有合并点的逻辑。
网友评论