以下內容轉載自Crape的文章《web頁面上的旋轉矩形碰撞》

作者：Crape

鏈接：https://juejin.im/post/5eede991e51d45740950c946

來源：掘金

著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

前言

本文主要是總結一下web頁面中的旋轉矩形的碰撞檢測，碰撞算法本身并不難，只是需要注意web坐標系在計算中的影響。碰撞檢測應該是在游戲等場景中很常見且基礎的功能，本文記錄了在JavaScript API GL遇到了這類碰撞問題的調研和實現的過程。

需求場景

用戶在地圖上實現MultiLabel文本標注覆蓋物時，會由于兩個label坐標過近，或者地圖的旋轉、縮放產生的變化而相互重疊。目前label的背景色均為透明且暫時還不支持配置，文字重疊之后識別度下降很多，就計劃先實現label之間的避讓功能。檢測到兩個label碰撞時，根據優先級選擇隱藏其中的一個，保證文字的可讀性。

確定算法

在JSAPI GL中，label并不是在三維空間中的，而是繪制在屏幕上的，只是會根據用戶視角的移動實時計算出label在屏幕坐標中所處的位置，然后在每一幀中進行繪制。label實際上就是一行文字，我們可以把它用一個矩形包圍起來，當做整體計算，因為每個字之間的相對位置并不會變，這樣一來label的碰撞檢測實際上可以轉化為二維空間內的矩形碰撞。

一般的橫平豎直的矩形檢測碰撞很簡單，只要想清楚有哪些情況即可，不在這里贅述。但是用戶可以對label進行旋轉和偏移操作，普通的檢測方法就不適用了，如果強行把label用一個大的水平矩形包裹起來再計算，精度損失會很多，所以調研了一下旋轉矩形的碰撞檢測方法。

比較常見的一種方式是通過分離軸定律(SAT：Separating Axis Theorem)來計算，分離軸定義：兩個凸多邊形物體，如果能找到一個軸，使得兩個物體在該軸上的投影互不重疊，那么這兩個物體就沒有發生碰撞，這條軸可以稱為分離軸。

一般不會遍歷所有角度的軸，而是檢測垂直于多邊形每條邊的軸，因為在這些軸上我們可以取到極值。對于矩形來說可以進一步簡化，因為一個矩形的4條軸內有2個是重復的，所以只需要檢測矩形互相垂直的兩條邊對應的軸就可以了。

進行判斷的具體方式有兩種：一是把每個矩形的4個頂點投影到一個軸上，算出該矩形最長的連線距離，判斷兩個矩形的投影是否重疊；二是將兩個矩形的半徑距離投影到軸上，然后把兩個矩形中心點的連線投影到通一個軸上，判斷兩個矩形的半徑投影之和與中心點連線投影的大小。

本文采用第二種方式計算，首先搞清楚投影的概念，引入向量來進行計算：

我們可以用單位向量來表示垂直于邊線的軸，這樣一個向量在軸線上的投影長度可以用該向量與投影軸上的單位向量的點積來表示。如上圖，A點坐標為(xa, ya)，OB為線段OA在x軸上的投影，x軸的單位向量為(1, 0)，OA · x軸單位向量 = (xa, ya) · (1, 0) = xa * 1 + ya * 0 = xa。

// 如果用數組[x ,y]表示一個向量,則兩個向量的點積結果可以表示為 function dot(vectorA, vectorB) {return Math.abs(vectorA[0] * vectorB[0] + vectorA[1] * vectorB[1]); }

然后就是如何表示矩形兩個軸的單位向量，假設矩形以自身的中心點為原點，逆時針旋轉θ，其兩條相鄰邊的軸的單位向量如下圖所示：

單位圓的半徑為1，所以單位向量OA為 (cosθ, sinθ)，另一條邊的單位向量與OA垂直，為(-sinθ, cosθ)，這兩個單位向量的點積為0。但這里有一個非常重要的注意點：web頁面中的坐標系與我們平時使用的坐標系不同，x軸正方向不變，y軸的正方向向下。我在最開始實現算法的過程中忽略了這個問題，導致碰撞結果不對，調試了半天才發現原因。在實際計算中，我們所使用的坐標都是web屏幕坐標系下的，軸的正方向與常用的不同，所以兩個單位向量應該分別表示為 (cosθ, -sinθ), (sinθ, cosθ)，如下圖所示：

然后就是計算矩形的半徑投影，首先明確下半徑投影的概念，可以理解為矩形中心點到一個頂點的向量，在軸上的投影長度。其實就是，矩形在X軸上最遠處的交點，數學上意義就是2條檢測軸的投影之和。

兩個矩形檢測的過程中，以其中一個矩形的檢測軸為坐標系，投影另外一個矩形的檢測軸。如上圖所示，藍色線段為左邊矩形的半徑投影，黃色線段為右邊矩形檢測軸。我們需要把右邊2條檢測軸投影到藍色線段所在X軸的單位向量（即左邊矩形的檢測軸單位向量），得到投影比例，然后乘以檢測軸長度（即矩形長、寬的一半），可計算出右邊矩形的半徑投影。紅色線段則是兩個矩形中心點的連線，同樣需要計算它在藍色線段所在X軸的投影長度，如果中心點連線的投影長度大于兩個矩形的半徑投影之和，那么在這條軸上兩個矩形沒有碰撞，否則發生碰撞。

檢測最終是否碰撞，需要對四個分離軸都檢測一次，在任何一個軸上沒有碰撞，則兩個矩形就沒有碰撞。

實現

實際實現的過程中進行了簡單的旋轉矩形類，可根據實際業務需求調整，例如添加縮放、偏移等參數

class Rect {constructor(options) {const {center, height, width, angle} = options;this.centerPoint = [center.x, center.y];this.halfHeight = height / 2;this.halfWidth = width / 2;this.setRotation(angle);}getProjectionRadius(axis) { // 計算半徑投影 const projectionAxisX = this.dot(axis, this.axisX);const projectionAxisY = this.dot(axis, this.axisY);return this.halfWidth * projectionAxisX + this.halfHeight * projectionAxisY;}dot(vectorA, vectorB) { // 向量點積return Math.abs(vectorA[0] * vectorB[0] + vectorA[1] * vectorB[1]);}setRotation(angle) { // 計算兩個檢測軸的單位向量const deg = (angle / 180) * Math.PI;this.axisX = [Math.cos(deg), -Math.sin(deg)];this.axisY = [Math.sin(deg), Math.cos(deg)]; return this;}isCollision(check) {const centerDistanceVertor = [this.centerPoint[0] - check.centerPoint[0],this.centerPoint[1] - check.centerPoint[1]];const axes = [ // 兩個矩形一共4條檢測軸this.axisX,this.axisY,check.axisX,check.axisY];for (let i = 0, len = axes.length; i < len; i++) {if (this.getProjectionRadius(axes[i]) + check.getProjectionRadius(axes[i]) <= this.dot(centerDistanceVertor, axes[i])) {return false; // 任意一條軸沒碰上，就是沒碰撞}}return true;} }

使用時每個矩形實例化一個Rect類，然后調用實例上的isCollision方法，參數傳入另一個矩形的實例，最后返回一個boolean類型的碰撞結果。

總結

封裝的這個類比較簡單，沒有涉及到里面參數改變的問題，有需要的話可以再完善。實現過程中注意下web坐標系的問題就可以了。矩形應該是最簡單的一種，其他凸多邊形的檢測會復雜一些，有興趣的話可以自己嘗試一下。

本文參考以下blog：
https://blog.csdn.net/tom_221x/article/details/38457757
https://aotu.io/notes/2017/02/16/2d-collision-detection/index.html

畫圖工具為 GeoGebra sketch

實際效果可以在騰訊位置服務官網的示例中嘗試https://lbs.qq.com/webDemoCenter/glAPI/glMarker/labelCollision

產品推廣

Javascript API GL是基于WebGL技術打造的3D版地圖API，3D化的視野更為自由，交互更加流暢。 提供豐富的功能接口，包括點、線、面繪制，自定義圖層、個性化樣式及繪圖、測距工具等，使開發者更加容易的實現產品構思。 充分發揮GPU的并行計算能力，同時結合WebWorker多線程技術，大幅度提升了大數據量的渲染性能。最高支持百萬級點、線、面繪制，同時可以保持高幀率運行。

同步推出基于Javascript API GL的 位置數據可視化API庫，歡迎體驗。

總結

以上是生活随笔為你收集整理的腾讯地图JavaScript API GL实现文本标记的碰撞避让的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。