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

[Aresn]

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

编辑：Aresn

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

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

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

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

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

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

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

文字标注算法是 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;

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

创建四分位模型

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

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

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

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

代码如下：

_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，接下来还会继续给大家分享干货。

福利

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

• Aresn 大神，开源了很优秀的前端 UI 组件库 iView，出版了《 Vue.js 实战》一书。向大家推荐他的课程，Vue.js 实战系列教程，从本链接过去的打八折优惠，先到先得。

• Chaos WebGL 专家，擅长 web 3D 开发。 主要有被《玩坏的地球系列课程》，很适合初学者。

[flowfire]

逻辑看起来挺简单的
不过要是让我实现我肯定懒得。。。

[gzlock]

反而重要区域不显示城市名是吗？
广东那里，韶关能显示，但是广州深圳佛山都没了
江浙地区地名全没了

[Humorce]

@gzlock 放大不就看到了

[xomix]

一般来说这个的解决方案是现成的，做几套不同的显示层的现实与否设置，然后根据具体的地图缩放 zoom 调整显示与否即可。

[gzlock]

@Humorce 原图放大不也能看清？抬杠没意义。

[shevchenhe]

@xomix 正解，label 显示杂乱本身就说明图的设计是有问题的。

[SuperMild]

@xomix 原图放大后是没问题，但是不放大就很难看，让人一看就觉得什么地方不对。避让后不管放不放大都不会让读者感到不适。

[hxsf]

> 我们通过反复测试发现 canvas 的 font 等于 “ 13px Arial ” 字体（别的字体不敢保证）的时候，文字的高度大概是 fontSize 的 1.1 倍。
> 所以代码如下：
> ```
> let fontSize = parseInt(ctx.font);
> let height = fontSize * 1.1;
> ```

会不会太草率了。

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

我的方案是 init 的时候创建一个不可见的 span， 填充一个 M，
要计算某个字体的某个大小占用的宽高的时候，对这个 span 应用字体样式，计算这个 span 的宽高。

[AiBoy]

这种机械的文字避让很搞笑啊。

[AlwaysBee]

在用 iview，非常棒

[Humorce]

@gzlock 避让和显示成一坨 我是在讨论这个效果。
在这两个图中用户要选中广州市就必然要缩放至广东省内。

[otakustay]

@Humorce 那为何韶关就不需要缩放呢

其实这问题很简单啊，文字避让算法里没有加文字的各自权重而已

[Humorce]

@otakustay
权重就过了，你把广州设为最高优先级，也是挤成一坨，几个亮点在那你想点哪，韶关它能显示出来，这是地理位置决定的。

我觉得为了用户体验，你这种权重处理应当像酒店直接展示世界主要时区时间一样处理，而不是让用户去地图上找。

[xu33]

mark
可能会用到

[gzgz8080]

感觉这个可以用遗传算法来解决，把显示重叠的一批点进行杂交，经过数论迭代后能近似地选出最优点。

[Aresn]

@hxsf 好主意，已经推荐给了 inMap 作者。

[learnshare]

应该参考目前在线地图的方案，将地区名称根据不同的缩放等级来显示或隐藏
在此基础上再处理文字叠加的问题

然后几十个点叠到一起本身可读性就很差，这么多文字基本的算法也比较难优化位置了，不如选择更合适的呈现方式（比如热力图）

[QAPTEAWH]

"When in doubt, use brute force." - Ken Thompson

简单点可以给城市加个权值(大城市权值大)，使总权值尽量大。

[imn1]

还以为肃静……回避……

[Aresn]

@learnshare 恩，目前的 label 也是具有通用性的，框架本身不知道 label 表达的是什么，不过假如权重信息会更好

[lxrmido]

mark ……

[loading]

居然没有权重？

[lifenglu]

@hxsf 这方法不错，你的思路很棒！

[lifenglu]

@AiBoy 简单 粗暴 有效 哈哈