共计 3691 个字符，预计需要花费 10 分钟才能阅读完成。
以下内容转载自 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 库，欢送体验。
