V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐关注
Meteor
JSLint - a JavaScript code quality tool
jsFiddle
D3.js
WebStorm
推荐书目
JavaScript 权威指南第 5 版
Closure: The Definitive Guide
Aresn
V2EX  ›  JavaScript

你不知道的前端算法之文字避让

  •  1
     
  •   Aresn · 2018-01-10 10:08:45 +08:00 · 5559 次点击
    这是一个创建于 2260 天前的主题,其中的信息可能已经有所发展或是发生改变。

    本文作者:TalkingData 可视化工程师李凤禄

    编辑:Aresn

    inMap 是一款基于 canvas 的大数据可视化库,专注于大数据方向点线面的可视化效果展示。目前支持散点、围栏、热力、网格、聚合等方式;致力于让大数据可视化变得简单易用。

    GitHub 地址:https://github.com/TalkingData/inmap

    文档地址:http://inmap.talkingdata.com/

    在地理信息可视化中,我们经常会遇到在地图上标记文字的需求,下面展示的是某流行 chart 图表框架的效果:

    image

    要显示的文字空间不够时,就会造成文字重叠显示混乱,用户体验很不友好。

    怎么解决这个问题呢?我们采用文字避让算法,解决这种坑爹的问题。

    下面展示的是 inMap 文字避让效果:

    image

    文字标注算法是 GIS 中最复杂的问题之一(属于 NP 复杂度问题,所以通常不能找到最优解,只能找到较优解)。

    inMap 避让算法采用的是四分位模型算法,接下来手把手教你写避让算法,老司机带你装逼带你飞。

    准备数据

    inMap 接收的是经纬度数据,需要把它映射到 canvas 的像素坐标,这就用到了墨卡托转换,墨卡托算法很复杂,以后我们会有单独的一篇文章来讲讲他的原理。经过转换,你得到的数据应该是这样的:

    [
      {
        "name": "海门",//要显示的文字
        "lng": 121.15,
        "lat": 31.89,
        "count": 7,
        "pixel": { //像素坐标
          "x": 968,
          "y": 736
        }
      },
      {
        "name": "鄂尔多斯",
        "lng": 109.781327,
        "lat": 39.608266,
        "count": 5,
        "pixel": {
          "x": 659,
          "y": 478
        }
      },
    ...
    ]
    

    好了,我们得到转换后的像素坐标数据(x、y),就可以做下面的事情了。

    求出每段文字矩形的实际大小

    measureText() 是 canvas 内置的方法,返回字体宽度的像素单位:

    let ctx = this.container.getContext('2d'); // canvas 上下文
    let width= ctx.measureText(name).width;
    

    我们通过 measureText 得到每个文字的宽度,canvas 并没有直接获取文字的方法,那文字的高度如何的得到呢?

    我们通过反复测试发现 canvas 的 font 等于 “ 13px Arial ” 字体(别的字体不敢保证)的时候,文字的高度大概是 fontSize 的 1.1 倍。

    所以代码如下:

    let fontSize = parseInt(ctx.font);
    let height = fontSize * 1.1;
    

    文字的宽度和高度得到后,我们就可以创建文字矩形的坐标系了。

    创建四分位模型

    image

    所谓四分位模型,每一个标记点都有上下左右四个放文字的位子,如果左边放不下,那就放右边试试,还不行就放到下面试试,以此类推,原理就这么简单,哈哈。

    创建右侧虚拟矩形坐标描述:

    image

    右侧虚拟矩形坐标的描述把圆点也包含在内了,是为了防止文字和圆点重叠。

    在计算虚拟矩形的高度时有些坑,圆点大小不是固定的,是根据用户动态配置的,圆点的直径可能大于文字的高度,我们就设定虚拟矩形的高度永远都是最大的那个,需要做一些特殊处理。

    代码如下:

    _getLeftAnchor() {
        let x = this.center.x - this.radius - this.textReact.width,
            y = this.center.y - this.textReact.height / 2,
            diam = this.radius * 2,
            maxH = diam > this.textReact.height ? diam : this.textReact.height; //矩形的高度
        return {
            x,
            y,
            minX: x,
            maxX: this.center.x + this.radius,
            minY: this.center.y - maxH / 2,
            maxY: this.center.y + maxH / 2
        };
    }
    

    以此类推,描述下面、左面、上面的虚拟矩形坐标。

    判断碰撞

    判断两个矩形是否覆盖相交,根据矩形的 minX,maxX,minY,maxY 判断相交,原理比较简单,代码如下:

    /**
     * 判断分位是否相交
     * @param {*} target 
     */
     
    isAnchorMeet(target) {
        let react = this.getCurrentRect(),
            targetReact = target.getCurrentRect();
        if ((react.minX < targetReact.maxX) && (targetReact.minX < react.maxX) &&
            (react.minY < targetReact.maxY) && (targetReact.minY < react.maxY)) {
            return true;
        }
        return false;
    }
    

    创建虚拟文字集合对象

    let labels = pixels.map((val) => {
        let radius = val.pixel.radius + this.style.normal.borderWidth; //圆点半径
        return new Label(val.pixel.x, val.pixel.y, radius, fontSize, byteWidth, val.name);
    });
    

    递归遍历虚拟文字集合、判断是否与其他相交,如果有相交就移动当前文字位子,直到不相交为止。当找不到合适位置时,就选择隐藏当前文字。

    代码如下:

    do {
        var meet = false; //本轮是否有相交
        for (let i = 0; i < labels.length; i++) {
            let temp = labels[i];
            for (let j = 0; j < labels.length; j++) {
                if (i != j && temp.show && temp.isAnchorMeet(labels[j])) {
                    temp.next();
                    meet = true;
                    break;
                }
            }
        }
    } while (meet);
    

    绘画文字

    labels.forEach(function (item) {
        if (item.show) { //是否显示
            let pixel = item.getCurrentRect();
            ctx.beginPath();
            ctx.fillText(item.text, pixel.x, pixel.y);
            ctx.fill();
        }
    });
    

    文字避让算法到目前介绍完了,对应的 inMap 文件地址为https://github.com/TalkingData/inmap/blob/master/src/worker/helper/Label.js,接下来还会继续给大家分享干货。

    福利

    分享两位业内大牛的前端课程:

    24 条回复    2018-01-11 09:55:49 +08:00
    flowfire
        1
    flowfire  
       2018-01-10 11:10:36 +08:00   ❤️ 1
    逻辑看起来挺简单的
    不过要是让我实现我肯定懒得。。。
    gzlock
        2
    gzlock  
       2018-01-10 11:30:23 +08:00 via Android   ❤️ 3
    反而重要区域不显示城市名是吗?
    广东那里,韶关能显示,但是广州深圳佛山都没了
    江浙地区地名全没了
    Humorce
        3
    Humorce  
       2018-01-10 11:33:48 +08:00 via iPhone
    @gzlock 放大不就看到了
    xomix
        4
    xomix  
       2018-01-10 11:36:43 +08:00   ❤️ 1
    一般来说这个的解决方案是现成的,做几套不同的显示层的现实与否设置,然后根据具体的地图缩放 zoom 调整显示与否即可。
    gzlock
        5
    gzlock  
       2018-01-10 11:45:23 +08:00 via Android
    @Humorce 原图放大不也能看清?抬杠没意义。
    shevchenhe
        6
    shevchenhe  
       2018-01-10 11:45:56 +08:00
    @xomix 正解,label 显示杂乱本身就说明图的设计是有问题的。
    SuperMild
        7
    SuperMild  
       2018-01-10 12:02:11 +08:00
    @xomix 原图放大后是没问题,但是不放大就很难看,让人一看就觉得什么地方不对。避让后不管放不放大都不会让读者感到不适。
    hxsf
        8
    hxsf  
       2018-01-10 12:21:54 +08:00   ❤️ 2
    > 我们通过反复测试发现 canvas 的 font 等于 “ 13px Arial ” 字体(别的字体不敢保证)的时候,文字的高度大概是 fontSize 的 1.1 倍。
    > 所以代码如下:
    > ```
    > let fontSize = parseInt(ctx.font);
    > let height = fontSize * 1.1;
    > ```

    会不会太草率了。

    事实上,不同平台、不同浏览器、不同字体都会造成字体大小和实际高度的差距。

    我的方案是 init 的时候创建一个不可见的 span, 填充一个 M,
    要计算某个字体的某个大小占用的宽高的时候,对这个 span 应用字体样式,计算这个 span 的宽高。
    AiBoy
        9
    AiBoy  
       2018-01-10 12:31:34 +08:00   ❤️ 1
    这种机械的文字避让很搞笑啊。
    AlwaysBee
        10
    AlwaysBee  
       2018-01-10 12:37:38 +08:00   ❤️ 1
    在用 iview,非常棒
    Humorce
        11
    Humorce  
       2018-01-10 12:50:41 +08:00 via iPhone   ❤️ 1
    @gzlock 避让和显示成一坨 我是在讨论这个效果。
    在这两个图中用户要选中广州市就必然要缩放至广东省内。
    otakustay
        12
    otakustay  
       2018-01-10 13:00:08 +08:00   ❤️ 1
    @Humorce 那为何韶关就不需要缩放呢

    其实这问题很简单啊,文字避让算法里没有加文字的各自权重而已
    Humorce
        13
    Humorce  
       2018-01-10 13:17:56 +08:00 via iPhone   ❤️ 2
    @otakustay
    权重就过了,你把广州设为最高优先级,也是挤成一坨,几个亮点在那你想点哪,韶关它能显示出来,这是地理位置决定的。

    我觉得为了用户体验,你这种权重处理应当像酒店直接展示世界主要时区时间一样处理,而不是让用户去地图上找。
    xu33
        14
    xu33  
       2018-01-10 13:22:01 +08:00   ❤️ 2
    mark
    可能会用到
    gzgz8080
        15
    gzgz8080  
       2018-01-10 14:21:55 +08:00
    感觉这个可以用遗传算法来解决,把显示重叠的一批点进行杂交,经过数论迭代后能近似地选出最优点。
    Aresn
        16
    Aresn  
    OP
       2018-01-10 14:22:19 +08:00
    @hxsf 好主意,已经推荐给了 inMap 作者。
    learnshare
        17
    learnshare  
       2018-01-10 14:36:35 +08:00
    应该参考目前在线地图的方案,将地区名称根据不同的缩放等级来显示或隐藏
    在此基础上再处理文字叠加的问题

    然后几十个点叠到一起本身可读性就很差,这么多文字基本的算法也比较难优化位置了,不如选择更合适的呈现方式(比如热力图)
    QAPTEAWH
        18
    QAPTEAWH  
       2018-01-10 14:57:03 +08:00
    "When in doubt, use brute force." - Ken Thompson

    简单点可以给城市加个权值(大城市权值大),使总权值尽量大。
    imn1
        19
    imn1  
       2018-01-10 15:07:18 +08:00
    还以为肃静……回避……
    Aresn
        20
    Aresn  
    OP
       2018-01-10 16:20:50 +08:00
    @learnshare 恩,目前的 label 也是具有通用性的,框架本身不知道 label 表达的是什么,不过假如权重信息会更好
    lxrmido
        21
    lxrmido  
       2018-01-10 16:30:56 +08:00
    mark ……
    loading
        22
    loading  
       2018-01-10 16:49:06 +08:00 via Android
    居然没有权重?
    lifenglu
        23
    lifenglu  
       2018-01-11 09:55:16 +08:00
    @hxsf 这方法不错,你的思路很棒!
    lifenglu
        24
    lifenglu  
       2018-01-11 09:55:49 +08:00
    @AiBoy 简单 粗暴 有效 哈哈
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3596 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 10:42 · PVG 18:42 · LAX 03:42 · JFK 06:42
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.