以下内容转载自Crape的文章《web页面上的旋转矩形碰撞》

作者：Crape

链接：https://juejin.im/post/5eede9...

起源：掘金

著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。

前言

本文次要是总结一下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_221...
https://aotu.io/notes/2017/02...

画图工具为 GeoGebra sketch

实际效果能够在腾讯位置服务官网的示例中尝试https://lbs.qq.com/webDemoCenter/glAPI/glMarker/labelCollision

产品推广

Javascript API GL是基于WebGL技术打造的3D版地图API，3D化的视线更为自在，交互更加晦涩。 提供丰盛的性能接口，包含点、线、面绘制，自定义图层、个性化款式及绘图、测距工具等，使开发者更加容易的实现产品构思。 充分发挥GPU的并行计算能力，同时联合WebWorker多线程技术，大幅度晋升了大数据量的渲染性能。最高反对百万级点、线、面绘制，同时能够放弃高帧率运行。

同步推出基于Javascript API GL的 地位数据可视化API库，欢送体验。