你可能不知道的前端算法之文字避让(inMap)

前言

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

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对我们的支持。

时间: 2018-01-09

总结一些你可能不知道的ip地址

前言 IP地址是指互联网协议地址(英语:Internet Protocol Address,又译为网际协议地址),是IP Address的缩写.提起IP地址,大家肯定都知道,但本文主要给大家总结了一些大家可能不知道的ip地址,分享出来供大家参考学习,下面话不多说,来一起看看详细的介绍: 一.短ip 作为it从业人员,我们都知道以127开头的ip,都是指向本机的,比如127.9.9.9 但是,你知道127.1是指向哪里么,没错就是127.1,没有少什么 如果你不清楚的话,可以ping 一下看看,也

你可能不知道的Shell(有趣的知识)

Shell也叫做命令行界面,它是*nix操作系统下用户和计算机的交互界面.Shell这个词是指操作系统中提供访问内核服务的程序. 这篇文章向大家介绍Shell一些非广为人知.但却实用有趣的知识,权当品尝shell主食后的甜点吧. 科普 先科普几个你可能不知道的事实: Shell几乎是和Unix操作系统一起诞生,第一个Unix Shell是肯·汤普逊(Ken Thompson)以Multics上的Shell为模范在1971年改写而成,并命名Thompson sh.即便是后来流行的bash(shel

Android中你可能不知道的Fragment妙用

本文主要给大家介绍了关于Android中你可能不知道的Fragment妙用的相关内容,分享出来供大家参考学习,下面来一起看看吧. 先来看看效果图 在软件开发中登陆功能是十分常见重要的,就以此为例说明fragment的一种用法,让开发变得更自如 1.这个用法的原因和意义 在未登录情况下,点击很多地方都可能要跳到登陆界面,登陆成功后,当前页面需要刷新 我们的一般做法是StartActivityForResult,在登陆成功后,SetResultOK,finsh登陆页面. 在当前Activity或者f

vue技术分享之你可能不知道的7个秘密

前言 本文是vue源码贡献值Chris Fritz在公共场合的一场分享,觉得分享里面有不少东西值得借鉴,虽然有些内容我在工作中也是这么做的,还是把大神的ppt在这里翻译一下,希望给朋友带来一些帮助. 一.善用watch的immediate属性 这一点我在项目中也是这么写的.例如有请求需要再也没初始化的时候就执行一次,然后监听他的变化,很多人这么写: created(){ this.fetchPostList() }, watch: { searchInputValue(){ this.fetch

关于bash函数你可能不知道的一些事情(译)

关于bash函数,这里有一些您不知道的东西.通常当你写一个函数时,你会这样做: function name () { ... } 不是吗?我知道你会这么做,因为这是所有人写函数的方式.这就是我要说的.在bash中 {-} 并不像在JavaScript或c中那样意味着"函数的主体"或"函数的范围",它实际上是一个复合命令.你可以做各种稀奇古怪的事情,比如: function fileExists () [[ -f $1 ]] 不需要那些花括号!者你可以这样做: fun

你可能不知道的Vim使用小技巧

一.用拷贝的内容替换 当发生拼写错误或者想要重命名标识符时,就需要用拷贝的内容来替换当前的名字.比如调用函数时写错了: void letus_fuckit_with_vim(){ cout<<"great!"; } let_fuckat_with_vom(); 只需要先复制上面的函数名,再把光标切换到拼错的词首.然后按下viwp,就替换过来了: void letus_fuckit_with_vim(){ cout<<"great!"; } l

你或许不知道的一些npm实用技巧

前言 绝大多数前端和 Node.js 开发者每天的日常工作都离不开 npm,不知道你对 npm 的观感如何?如果你觉得 npm 很棒,那么不妨看下这篇文章,说不定其中有你之前没留意过的小窍门,可以让你 npm 用得更顺手.如果你觉得 npm 很糟糕,那也可以看下这篇文章,也许会发现用上一些小技巧,npm 会变得稍微不那么糟糕. npm ci 别被它的名字骗了.npm ci 并不仅仅适用于持续集成系统,在日常开发中,npm ci 非常实用.和 npm install 不同,npm ci 根据 pa

不能不知道的10个angularjs英文学习网站

AngularJS 是非常棒的JS框架,能够创建功能强大,动态功能的Web app.AngularJS自2009发布以来,已经广泛应用于Web 开发中.但是对想要学习Angular JS 的人而言,只有官方文档,那是万万不够的.大多数人更愿意看一些入门视频,或者是更易于理解学习的Demo程序.因此本文推荐了10个AngularJS 学习指南,助你一臂之力. 1. Year of Moo 超级赞的AngularJS学习指南,是由Year of Moo 创建的,包含AngularJS基本知识以及An

你可能不知道的JSON.stringify()详解

前言 JSON已经逐渐替代XML被全世界的开发者广泛使用.本文深入讲解JavaScript中使用JSON.stringify的一些细节问题.首先简单回顾一下JSON和JavaScript: 不是所有的合法的JSON都是有效的JavaScript: JSON只是一个文本格式: JSON中的数字是十进制. 1. JSON.stringify let foo = { a: 2, b: function() {} }; JSON.stringify(foo); // "{ "a":