本篇文章已授权微信公众号 guolin_blog (郭霖) 独家发布
老规矩先上图， 高仿 ios 相册， 地图算法分析。
下载.gif
百度地图 SDK 新增点聚合功能。通过该功能，可通过缩小地图层级，将定义范围内的多个标注点，聚合显示成一个标注点，解决加载大量点要素到地图上产生覆盖现象的问题，并提高性能。
基于百度地图优化算法流程：（其实百度也是抄袭 google map 的算法）
- 加入异步添加屏幕上图片，
- 只加载屏幕范围内的图片
- 优化渲染逻辑
大大减少运算的时间
（经过测试 2W 张不同经纬度的图片 300-500ms 可以计算完毕，绝对比 ios 相册还快。）
讲解点聚合功能，整个分析过程分为三部分：
1、如何添加点聚合功能到项目中；
2、整体结构分析；
3、核心算法分析。
一、添加点聚合功能
如官网所示，添加点聚合的方法分为三步：
1、声明点聚合管理类为全局变量，并初始化。核心代码如下图：
MarkerOptions opts = new MarkerOptions().position(cluster.getPosition())
.icon(BitmapDescriptorFactory.fromBitmap(XX));
Marker marker = (Marker) mMap.addOverlay(opts);
二、整体结构分析
先上一个思维导图：
2.png
如上图，点聚合有四个类
1、Cluster 数据：主要是聚合数据类型，图示很明确，这里不罗嗦；
2、四叉树：记录初始范围内的所有图片并以四叉树的数据结构组织。核心算法需要用到的数据结构，后面再讲；
3、点聚合算法：基于四叉树的核心算法。后面讲；
4、Cluster 管理：对外接口，通过调用核心算法实现点聚合功能、
整个功能的主要流程有两条：
1、添加 item：Cluster 管理类添加 item 接口 算法类添加 item 接口：记录所有的图片信息 四叉树类添加 item 接口：已四叉树的结构记录所有图片信息
2、获取聚合后的集合：Cluster 管理类获取聚合接口 算法类核心算法接口：通过核心算法获取聚合后的集合
三、核心算法
首先要说一个概念：世界宽度。
百度地图是把整个地球是按照一个平面来展开，并且通过墨卡托投影投射到xy坐标轴上面。上图：
世界地图
墨卡托投影后的坐标轴
很明显墨卡托投影把整张世界地图投影成
X∈ [0,1] ; Y∈ [0,1]。的一个正方型区域，世界宽度为 1 。
X 表示的是经度，Y表示的是纬度。
（其实准确来说是投影一个上下无限延伸的长方体，只是Y属于 [0,1] 这个范围已经足够我们使用）上图说明：
3.png
从上面看出 -85° 的纬度对应Y坐标是1，那么 -90° 呢，你们自己可以去算一下，是 +∞ （正无穷），90 ° 是 -∞ （负无穷） 。
至于为什么讲这个，因为计算搜索范围的时候，所有的经纬度都需要换算成Point 来计算，是不是很方便性，而且不易出错。
真是感叹伟人的强大！
附注
转换的公式在下面这个类里面：
SphericalMercatorProjection.java
接下来说说如何通过四叉树组织数据
四叉树的基本思想是把空间递归划分为不同层次的树结构。它把已知的空间等分成四个相等的子空间，如此递归下去，直到满足当层数目量超过 50，或者层级数大于 40 则停止分割。示意图如下：
四叉树
OK，接下来说说具体流程
- 遍历 QuadItem，只加载屏幕内的点，生成四叉树，方便搜索。
- 如果图片已被 visitedCandidate 记录，则 continue 下面步骤，直到需要处理的图片没有被 visitedCandidates 记录；
- 对上一次屏幕上的点
QuadItem先进行处理； - 根据 MAX_DISTANCE_IN_DP 及图片位置计算出 searchBounds；
- 通过四叉树得到 searchBounds 内所有的图片；
- 如果图片数量为1，记录并跳到步骤2；
- 遍历得到的图片；
- 依次对得到的图片进行处理，
- 如果图片到中心点的距离比 distanceToCluster （此图片与包含此图片的前cluster的距离）小，把图片加入结果集，并移除前 Cluster 拥有该图片的引用，并记录此次更小的距离，跳步骤 8 继续遍历剩余项。
重点源码分析：
- 聚合触发口
@Override
public void onMapStatusChangeFinish(MapStatus mapStatus) {
if (mRenderer instanceof BaiduMap.OnMapStatusChangeListener) {
((BaiduMap.OnMapStatusChangeListener) mRenderer).onMapStatusChange(mapStatus);
}
// 屏幕缩放范围太小，不进行触发聚合功能
if (mPreviousCameraPosition != null
&& Math.abs((int) mPreviousCameraPosition.zoom - (int) mapStatus.zoom) < 1
&& mPreviousCameraPosition.target.latitude == mapStatus.target.latitude
&& mPreviousCameraPosition.target.longitude == mapStatus.target.longitude) {
return;
}
//记录
mPreviousCameraPosition = mapStatus;
//算法运算，计算出聚合后结果集，并且addMarker 到屏幕上
cluster(mapStatus.zoom,mapStatus.bound);
}
对地图进行手势操作，都会进行触发这个函数，并进行聚合操作
2.算法运算
NonHierarchicalDistanceBasedAlgorithm.java
@Override
public Set<Cluster<T>> getClusters(double zoom, LatLngBounds visibleBounds) {
...
}
这个函数有点多，不过在 github 上面的 demo 已经注释满满，请移步 github 查看。
3.渲染UI(addMarker)
class DefaultClusterRenderer {
class CreateMarkerTask {
...
}
}
private void perform(MarkerModifier markerModifier) {
// Don't show small clusters. Render the markers inside, instead.
markRemoveAndAddLock.lock();
//真正添加Marker 的地方
Marker marker = mClusterToMarker.get(cluster);
if (marker == null || (marker != null
&& mMarkerToCluster.get(marker).getSize() != cluster.getSize())) {
//异步添加Marker，查看同个位置是否已经有打入Marker
//没有的话，进行添加，如果有，并且图片右上角的size数不一样
//也要执行添加
Integer size = onReadyAddCluster.get(cluster);
if (size == null || size != cluster.getSize()) {
onReadyAddCluster.put(cluster,cluster.getSize());
//添加Marker的执行函数
onBeforeClusterRendered(cluster, new MarkerOptions()
.position(cluster.getPosition()));
}
}
markRemoveAndAddLock.unlock();
newClusters.add(cluster);
}
主要添加图片的是onBeforeClusterRendered这一个函数， 我们看一下实现：
public class PersonRenderer extends DefaultClusterRenderer<LocalPictrue> {
//取消上一次的添加操作，只显示最后添加的cluster
DataSource<CloseableReference<CloseableImage>> target = cancleMap1.get(cluster);
if(target != null) {
target.close();
cancleMap1.remove(target);
}
final LocalPictrue person = cluster.getItems().iterator().next();
ImageRequest imageRequest = ImageRequestBuilder
.newBuilderWithSource(Uri.fromFile(new File(person.path)))
.setProgressiveRenderingEnabled(false)
.setResizeOptions(new ResizeOptions(50, 50))
.setPostprocessor(new BadgViewPostprocessor(mContext,cluster))
.build();
ImagePipeline imagePipeline = Fresco.getImagePipeline();
DataSource<CloseableReference<CloseableImage>> dataSource =
imagePipeline.fetchDecodedImage(imageRequest,mContext);
dataSource.subscribe(new BaseBitmapDataSubscriber() {
@Override
public void onNewResultImpl(@Nullable Bitmap bitmap) {
// You can use the bitmap in only limited ways
// No need to do any cleanup.
if(bitmap != null && !bitmap.isRecycled()) {
//把bitmap做为icon 打入marker
setIconByCluster(person.path,cluster,
markerOptions.icon(BitmapDescriptorFactory.fromBitmap(bitmap)));
}
cancleMap1.remove(cluster);
}
@Override
public void onFailureImpl(DataSource dataSource) {
// No cleanup required here.
System.out.println("shibai");
}
}, UiThreadImmediateExecutorService.getInstance());
cancleMap1.put(cluster, dataSource);
}
很明显我这边解决了 baiduMap 在UI线程上添加图片阻塞问题， 添加强大的 fresco 第三方加载库，进行异步加载图片，接下来看图片下载完成后 执行setIconByCluster 函数：
//异步回调回来的icon ，需要
public void setIconByCluster(String path, Cluster<T> cluster, MarkerOptions markerOptions) {
markRemoveAndAddLock.lock();
Integer size = onReadyAddCluster.get(cluster);
//此处主要解决多线程问题，多个addMarker只操作最尾的一次
if (size != null && cluster.getSize() == size) {
Marker marker = mClusterToMarker.get(cluster);
if (marker != null) {
//如果该图在屏幕上已经打了marker，那么替换icon即可，主要解决图片重新加载闪烁问题
marker.setIcon(markerOptions.getIcon());
} else {
//打入新的Marker
marker = mClusterManager.getClusterMarkerCollection().addMarker(markerOptions);
}
mMarkerToCluster.put(marker, cluster);
mClusterToMarker.put(cluster, marker);
}
markRemoveAndAddLock.unlock();
}
总结：
重点源码分析，基本上到这里结束。我们来撸一撸流程：
- 通过
onMapStatusChangeFinish回调，去执行点聚合运算； - 通过
getClusters把聚合后的结果集算出来； - 通过
CreateMarkerTask.perform()把 marker 打到屏幕上。
备注：
更多细节请看源代码
喜欢去帮忙start一下，谢谢！
github：
https://github.com/zhangchaojiong/BaiduMapClusterSample/tree/master
网友评论