腾讯地图JavaScript API GL实现文本标记的碰撞避让

以下内容转载自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库，欢迎体验。