T O P

[资源分享]     地图区域大数据量 marker 坐标点高效抽稀算法

  • By - 楼主

  • 2021-09-10 16:00:24
  • 按网上的思路一般要写双层循环,第一层循环遍历点集合,时间复杂度为O(N),第二层循环遍历结果集,逐一计算距离,距离小于阈值的不加入结果集,距离大于阈值的加入结果集,时间复杂度为O(log2N),双层循环总时间复杂度为O(N * log2N)。

    新的算法思路:坐标点的经纬度经过计算得到的结果作为HashMap的Key,坐标相近的点的Key相同,利用HashMap降低时间复杂度,不需要第二层循环遍历,把时间复杂度由O(N * log2N)降为O(N)。

    该算法的优点:1、抽稀后坐标点位置均匀,2、计算效率高(时间复杂度:O(N)),3、算法逻辑简单,4、计算结果幂等(结果集确定,多次重复计算结果集相同)。

     

    代码:

    //抽稀
    if (mapZoom >= 15 && mapZoom <= 16) {
        currentMarkerMap = new HashMap();
    
        var getKey = function (lng, lat, len, ratio) { //如果计算结果数量较少,就调大ratio
            var a = (10000 + lng * ratio).toString().substr(0, len);
            var b = (10000 + lat * ratio).toString().substr(0, len)
            return a + "," + b;
        };
    
        for (var i = 0; i < forAdd.length; i++) {
            var marker = forAdd[i];
    
            var key;
            if (mapZoom == 15) key = getKey(marker.geometry.x, marker.geometry.y, 9, 1);
            if (mapZoom == 16) key = getKey(marker.geometry.x, marker.geometry.y, 10, 1);
    
            if (!currentMarkerMap.containsKey(key)) {
                currentMarkerMap.put(key, marker);
            }
        }
    }
    View Code

    说明:代码中 forAdd 变量是抽稀前的坐标点集合,currentMarkerMap 变量是HashMap集合(HashMap是自己实现的JS类),定义代码如下:

    var forClear = [];
    var currentMarkerMap = new HashMap();
    View Code

    效果图:

     

    本帖子中包含资源

    您需要 登录 才可以下载,没有帐号?立即注册