你不知道的前端演算法之文字避讓
本文作者：TalkingData 可視化工程師李鳳祿
編輯：Aresn
inMap 是一款基於 canvas 的大數據可視化庫，專註於大數據方向點線面的可視化效果展示。目前支持散點、圍欄、熱力、網格、聚合等方式；致力於讓大數據可視化變得簡單易用。
GitHub 地址：https://github.com/TalkingData/inmap
在地理信息可視化中，我們經常會遇到在地圖上標記文字的需求，下面展示的是某流行 chart 圖表框架的效果：
要顯示的文字空間不夠時，就會造成文字重疊顯示混亂，用戶體驗很不友好。
怎麼解決這個問題呢？我們採用文字避讓演算法，解決這種坑爹的問題。
下面展示的是 inMap 文字避讓效果：
文字標註演算法是 GIS 中最複雜的問題之一（屬於 NP 複雜度問題，所以通常不能找到最優解，只能找到較優解）。
inMap 避讓演算法採用的是四分位模型演算法，接下來手把手教你寫避讓演算法，老司機帶你裝逼帶你飛。
準備數據
inMap 接收的是經緯度數據，需要把它映射到 canvas 的像素坐標，這就用到了墨卡托轉換，墨卡托演算法很複雜，以後我們會有單獨的一篇文章來講講他的原理。經過轉換，你得到的數據應該是這樣的：
好了，我們得到轉換後的像素坐標數據(x、y)，就可以做下面的事情了。
求出每段文字矩形的實際大小
是 canvas 內置的方法，返回字體寬度的像素單位：
我們通過 measureText 得到每個文字的寬度，canvas 並沒有直接獲取文字的方法，那文字的高度如何的得到呢？
我們通過反覆測試發現 canvas 的 font 等於 「13px Arial」 字體（別的字體不敢保證）的時候，文字的高度大概是 fontSize 的 1.1 倍。
所以代碼如下：
文字的寬度和高度得到後，我們就可以創建文字矩形的坐標系了。
創建四分位模型
所謂四分位模型，每一個標記點都有上下左右四個放文字的位子，如果左邊放不下，那就放右邊試試，還不行就放到下面試試，以此類推，原理就這麼簡單，哈哈。
創建右側虛擬矩形坐標描述：
右側虛擬矩形坐標的描述把圓點也包含在內了，是為了防止文字和圓點重疊。
在計算虛擬矩形的高度時有些坑，圓點大小不是固定的，是根據用戶動態配置的，圓點的直徑可能大於文字的高度，我們就設定虛擬矩形的高度永遠都是最大的那個，需要做一些特殊處理。
代碼如下：
以此類推，描述下面、左面、上面的虛擬矩形坐標。
判斷碰撞
判斷兩個矩形是否覆蓋相交，根據矩形的 minX,maxX,minY,maxY 判斷相交，原理比較簡單，代碼如下：
創建虛擬文字集合對象
遞歸遍歷虛擬文字集合、判斷是否與其他相交，如果有相交就移動當前文字位子，直到不相交為止。當找不到合適位置時，就選擇隱藏當前文字。
代碼如下：
繪畫文字
文字避讓演算法到目前介紹完了，對應的 inMap 文件地址為https://github.com/TalkingData/inmap/blob/master/src/worker/helper/Label.js，接下來還會繼續給大家分享乾貨。
福利
）:
TAG:全球大搜羅 |