碰撞检测
引子
碰撞检测（Collision Detection）这个东西，之前找 canvas 相关资料的时候碰到过，有些好奇，就去尝试了解一下。
简介
与碰撞检测有些类似的一个概念：命中检测（Hit-testing），也被广泛运用。
在计算机图形编程中，命中检测是确定用户控制的光标（或触摸屏上的触摸点）是否与屏幕上绘制的给定图形对象（如形状）产生相交的过程。根据这个定义，web 开发中碰到鼠标点击下拉菜单等这些交互都属于这个范畴。
碰撞检测用于检测多个不同图形对象的交叉点，不是光标与一个或多个图像对象的交叉点。在 web 游戏中也涉及到这些，2D 游戏中的碰撞检测算法，依赖于碰撞物体的形状（例如矩形与矩形、矩形与圆形、圆形与圆形）。基于 canvas，下面看看几种简单的情景。
光标碰撞检测
使用 canvas 创建交互时，在画布内点击，如果需要判断点击所在的图形，就需要做碰撞检测。思路比较简单，就是要检测光标点击的坐标是否在某个形状里面。在测试中发现几点需要注意：
- 遍历形状的顺序，因为绘制的图形可能重叠，后绘制的一般在上层，这个时候倒序遍历才合理。
- 获取点击坐标时，注意移动端和 PC 端对应属性，移动端 touch 属性中可能有多个坐标。
- 图形的形状，规则图形和非规则图形判断的方式有差异。
这是简单的示例，移动端访问如下：
基于像素颜色碰撞检测
上面数学计算的方式，如果在一些图案信息较多的情况下，需要存储大量的数据，会非常的不方便。另外的一种方式就是取得像素块，检测它们的颜色。例如这个示例，移动端访问如下：
示例中矩形区域是图片，其中线条颜色都是黑色，实现的思路是在小球移动之前，先取包含了小球且比小球稍大的空间像素，遍历像素数据，判断是否有黑色且不透明，如果有就说明在下一次重绘时就会发生碰撞。在迷宫类的游戏实现中，这种方式就会很方便，见小游戏 Maze 。
在测试中发现几点需要注意：
- 选择图片时，需要注意图片中颜色的使用，因为要用来作为判断依据，色值不要随意混用。
- 使用
getImageData方法时，获取数据的位置是根据 canvas 实际的像素数据，而不是渲染显示的大小。
矩形与矩形碰撞检测
这里是指轴对齐（意味着没有旋转）的两个矩形碰撞检测。下面的一个算法可以用来进行判断：
var rect1 = {x: 5, y: 5, width: 50, height: 50}
var rect2 = {x: 20, y: 10, width: 10, height: 10}
if (rect1.x <= rect2.x + rect2.width &&
rect1.x + rect1.width >= rect2.x &&
rect1.y <= rect2.y + rect2.height &&
rect1.height + rect1.y >= rect2.y) {
// collision detected!
}
上面的条件，以刚好碰撞的状态做对照，思考起来会比较方便理解。这是简单的示例，移动端访问如下：
圆形与圆形碰撞检测
这种形式的碰撞检测，通过两个圆心之间的直线距离，与两个圆的半径之和作比较。
var circle1 = {radius: 20, x: 5, y: 5};
var circle2 = {radius: 12, x: 10, y: 5};
var dx = circle1.x - circle2.x;
var dy = circle1.y - circle2.y;
var distance = Math.sqrt(dx * dx + dy * dy);
if (distance <= circle1.radius + circle2.radius) {
// collision detected!
}
这是简单示例，移动端访问如下：
从上面的示例中，发现如果使用在动态的场景下，效果并不一定如预期。
参考资料
上一篇： 100亿个数中找出最大的前K个数（海量TopK问题）
下一篇： 在两个升序数组中找到第k小的数据