地图开发科普篇:地图展示中的聚合问题浅析

2017-09-13 10:43:42来源:oschina作者:小秀儿人点击

分享

一什么是聚合?


聚合是指将一定区域内分散对象聚集在一起,我们都知道,地图展示如果元素数量过多,可能会导致界面出现压积,重叠,卡顿等性能差的效果。使用聚合能够有效的解决该类问题。


二如何实现聚合?


我秀地图sdk提供聚合相关的接口,开发者可根据这些接口来实现所需的需求。大致步骤分为如下三部:


1、获得一组数据集合设置给聚合对应的接口。


2、调用buildCluste接口构建聚合搜索四叉树。


3、调用showCluster显示聚合到视图上。


三聚合内部实现原理


1、为了便于管理搜索空间数据,聚合内部实现四叉树。四叉树将区域分为四个相等的象限区域,象限区域带有一定容量的数据,容量可定义。每个象限节点再次四等分,如下递归下去直到将数据分配完成。具体图示如下:

2、数据插入比较简单,由根节点开始,判断点属于哪个象限后插入,直到象限中容器的数量达到容量。如果象限容器数量达到最大值,再次将该象限四等分。如此重复步骤到数据全部插入完成为止,核心代码如下:


public boolean addQuadTreeNode(QuadTreeNode node, QuadTreeNodeData data) throws LeadorException {


if(data == null){


throw new LeadorException("QuadTreeNodeData is null"); }


//判断节点是否在象限内 if (!ClusterUtils.boundingBoxContainsData(node.boundingBox, data)) {


return false; }


//象限内的容量是否填满,满则不插入 int size = node.quadTreeNodeDataList.size(); if (size < capacity) {


node.quadTreeNodeDataList.add(data); ClusterBuild.this.nodeDataList.put(data,node); return true; }


/* 若节点容量已满,且该节点为叶子节点,则向下扩展. */


if (node.northWest == null) {


quadTreeNodeSubdivide(node);


}


if (addQuadTreeNode(node.northWest, data)) return true;


if (addQuadTreeNode(node.northEast, data)) return true;


if (addQuadTreeNode(node.southWest, data)) return true;


if (addQuadTreeNode(node.southEast, data)) return true;


return false;


}


3、四叉树搜索树可以通过以上1、2步骤生成,接着我们看看如何进行聚合计算。


在android移动手机上用户能够直接看到的视图区域为可视区域,为了优化性能我们只选择计算可视区域内点的分布情况。


在地图sdk中我们可以通过VisibleRegion类拿到可视区域latLngBounds属性。然后再将该可视区域映射到地图上的二维坐标(内部有提供经纬度转换二维坐标的方法),到这里就能够获得一个区域的矩形坐标。


4、在步骤3完成的基础上,我们对这个区域进行划分成单个cell,具体划分密度跟地图的缩放比例zoom和cellSize大小相关,总体来说zoom越大,cellSize越小,cell密度越大,具体代码如下:


//计算地图对应可是区域的比例


double zoomScale = mapWidth * 1.0D / rectWidth;


//获得 cellSize


double cellSize = cellSizeForZoomLevel(zoomLevel);


//计算zoom和cellSize的比例


double scaleFactor = zoomScale / cellSize;


5、在步骤4的基础上,我们可以得到类似cell网格区域,网格密度和zoom以及cellSize相关,接着计算每个cell的聚合程度。


由左上角第一个cell的范围开始搜索对应四叉树内点的数量,如果二个以上就确定为聚合点,一个就是单独的marker。如此计算完整个可是区域的cell。具体的代码如下:


// 要转化成地理坐标


LatLng pNortheastL = visibleRect.northeast;


LatLng pSouthwestL = visibleRect.southwest ;


IPoint pNortheastI = new IPoint();


IPoint pSouthwestI = new IPoint();


MapProjection.lonlat2Geo(pNortheastL.longitude, pNortheastL.latitude, pNortheastI);


MapProjection.lonlat2Geo(pSouthwestL.longitude, pSouthwestL.latitude, pSouthwestI);


int pMinX = (int)(pSouthwestI.x * scaleFactor);


int pMaxX = (int)(pNortheastI.x * scaleFactor);


int pMinY = (int)(pNortheastI.y * scaleFactor);


int pMaxY = (int)(pSouthwestI.y * scaleFactor);


//按原先划分的网格查找数据


for(int x = pMinX;x

for(int y=pMinY;y

searchQuad(x,y,zoomLevel,scaleFactor); }


}


6、在完成步骤5后,我们能够得到一组聚合,聚合的内部结构由经纬度(根据每个cell的经纬度重新计算),数量等属性构成。然后进行地图绘制,部分代码展示如下:


/**


*


* 将marker加入到地图中


*/


public void addMarkerToMap(){


if(lng == null) return;


//正常状态不管


if(status == 0) return;


//删除状态移除


if(status == 3 ){


clearMarker();


return;


}


try {


//单个marker


if(quadTreeNodeDataList.size() == 1){


QuadTreeNodeData iquad = quadTreeNodeDataList.get(0);


MarkerOptions options = iquad.getMarkerOptions();


addMark(options,false);


}else{


MarkerOptions options = new MarkerOptions();


addMark(options,true);


}


} catch (RemoteException e) {


e.printStackTrace(); }


}


7、需要注意的是每次可视区域发生变化时,重新计算cell个数和搜索cell的聚合程度。为了提升性能,需要实现聚合的去重。规定屏幕内单个cell聚合数量变化时候绘制,否则不需要。


/**


* 将聚合后的点加入到平面中


* @throws RemoteException


*/


private void addClusterToMap() throws RemoteException {


for (String key : removeMap.keySet()) {


QuadTreeNodeModel iq = removeMap.get(key);


iq.status = 3;


iq.addMarkerToMap();


currentMap.remove(iq.getSeqId());


}


for (String key : addMap.keySet()) {


QuadTreeNodeModel iq = addMap.get(key);


iq.status = 1;


iq.addMarkerToMap();


currentMap.put(iq.getSeqId(),iq);


}


通过以上的步骤完成聚合,实现效果示意图如下:

我秀地图开放平台向企业用户和普通用户提供部署版和在线版的定位、地图、搜索、导航等能力,以API、SDK等形式开放,帮助用户完成地图开发。

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台