聚合点算法实现
在地图上查询结果通常以标记点的形式展现，但是如果标记点较多，不仅会大大增加客户端的渲染时间，让客户端变得很卡，而且会让人产生密集恐惧症（图1）。为了解决这一问题，我们需要一种手段能在用户有限的可视区域范围内，利用最小的区域展示出最全面的信息，而又不产生重叠覆盖。
image
算法选择
直接距离法，数据量大的话数据会比较慢，聚合效果也不太真实
这里直接选用网格距离法
1、网格法，聚合出所要的点
2、直接距离法，进一步聚合
JS实现方法
1、经纬度转换为坐标
function _getMercator(poi) {//[114.32894, 30.585748]
var mercator = {};
var earthRad = 6378137.0;
// console.log("mercator-poi",poi);
mercator.x = poi.lng * Math.PI / 180 * earthRad;
var a = poi.lat * Math.PI / 180;
mercator.y = earthRad / 2 * Math.log((1.0 + Math.sin(a)) / (1.0 - Math.sin(a)));
// console.log("mercator",mercator);
return mercator; //[12727039.383734727, 3579066.6894065146]
}
2、获取矩形四个顶点的坐标
let minX = 0
let minY = 0
let maxX = 0
let maxY = 0
let mathData = mockData.map( item => {
let lonlat = _getMercator({lng: item.longitude, lat: item.latitude})
maxX = Math.max(maxX, lonlat.x)
maxY = Math.max(maxY, lonlat.y)
minX = Math.min(minX, lonlat.x)
minY = Math.min(minY, lonlat.y)
return {
point: item,
...lonlat
}
})
3、分割成多个小矩形
var points = {}
sourceData.forEach(item => {
let i = Math.floor( (item.x - minX) / radius )
let j = Math.floor( (item.y - minY) / radius )
let tmpPoint = points[i + '_' + j]
if (!tmpPoint) {
tmpPoint = {
data: []
}
points[i + '_' + j] = tmpPoint
}
tmpPoint.data.push(item)
});
for(let [key, tmpPoint] of Object.entries(points)) {
tmpPoint.x = tmpPoint.data.map(x => x.x).reduce((total,value)=>{
return total + value;
},0) / tmpPoint.data.length;
tmpPoint.i = (tmpPoint.x % radius) > (0.5 * radius)? 1: -1
tmpPoint.y = tmpPoint.data.map(x => x.y).reduce((total,value)=>{
return total + value;
},0) / tmpPoint.data.length;
tmpPoint.j = (tmpPoint.y % radius) > (0.5 * radius)? 1: -1
}
return points
}
4、小矩形之间的聚合
function _mergeSplit(sourceData ,radius) {
for(let [key, tmpPoint] of Object.entries(sourceData)) {
let attrs = key.split('_').map(x => parseInt(x))
_mathMerge(tmpPoint, sourceData[ (attrs[0] + tmpPoint.i)+ '_' + attrs[1] ])
|| _mathMerge(tmpPoint, sourceData[ attrs[0] + '_' + (attrs[1] + tmpPoint.j) ])
|| _mathMerge(tmpPoint, sourceData[ (attrs[0] + tmpPoint.i)+ '_' + (attrs[1] + tmpPoint.j) ])
}
var resultData = []
for(let [key, tmpPoint] of Object.entries(sourceData)) {
if (!tmpPoint.isMath) {
var lngLat = _getLngLat(tmpPoint);
resultData.push({
count: tmpPoint.data.length, coordinates: [lngLat.lng,lngLat.lat]
})
}
}
return resultData
function _mathMerge(point1, point2 ,radius) {
if (point2 && !point2.isMath && Math.abs(point1.x - point2.x) < (0.5 * radius)) {
var tmpData = [...point1.data,...point2.data]
var x = tmpData.map(x => x.x).reduce((total,value)=>{
return total + value;
},0) / tmpData.length;
var y = tmpData.map(x => x.y).reduce((total,value)=>{
return total + value;
},0) / tmpData.length;
var i = (x % radius) > (0.5 * radius)? 1: -1
var j = (y % radius) > (0.5 * radius)? 1: -1
if (i === point1.i && j === point1.j) {
point2.isMath = true;
Object.assign(point1,{data: tmpData, x, y, i, j})
return false;
}else {
Object.assign(point2,{data: tmpData, x, y, i, j})
point1.isMath = true;
return true;
}
}
return false;
}
}
5、墨卡托转经纬度
/**
* 墨卡托转经纬度
* @param poi 墨卡托
* @returns {{}}
* @private
*/
function _getLngLat(poi){
var lnglat = {};
lnglat.lng = poi.x/20037508.34*180;
var mmy = poi.y/20037508.34*180;
lnglat.lat = 180/Math.PI*(2*Math.atan(Math.exp(mmy*Math.PI/180))-Math.PI/2);
return lnglat;
}
总结
最终效果
- 点聚合算法要先将经纬度转换为坐标
- 点聚合的聚合半径要设置合理，比如中国的长宽在5000公里级别，所以聚合半径最好大于1000米，小于100公里
- 点聚合算法，数据量大的时候，可能时间比较长，可以考虑将计算结果放到redis或者文件系统中，用离线计算的方式
