# 你被追尾了

### 分析

#### 外接图形判别法（Axis-Aligned Bounding Box）

<html>
<style type="text/css">
* {
margin:0;
}
canvas {
border:1px solid orange;
margin:10px auto 0;
display:block;
}
</style>

<body>
<!-- html5 画布对象 -->
<canvas id="canvas" width="300" height="200"></canvas>
</body>
<script>
// 构造小球的函数
var Ball = function(context) {
// 球的外切正方形的左上角顶点坐标
this.left = 0;
this.top = 0;
// 小球的半径
// 小球的水平速度
this.velocityX = 3;
// 小球的垂直速度
this.velocityY = 2;
// 传入 H5 画布
this.context = context;
}

// 定义球拥有的方法
Ball.prototype = {
// 画球本身
paint: function() {
this.context.beginPath();
this.context.arc(this.left + this.radius, this.top + this.radius, this.radius, 0, Math.PI * 2, false);
this.context.fill();
},

// 球如何移动
move: function() {
this.left += this.velocityX;
this.top += this.velocityY;
}
}

// 处理边界碰撞逻辑
function handleEdgeCollisions(ball) {
// 球的外切正方形右下角
var ballRight = ball.left + ball.radius * 2;
var ballBottom = ball.top + ball.radius * 2;

// 球碰撞到了画布的左边框
if (ball.left < 0) {
ball.left = 0;
// 速度等值反向实现弹性碰撞
ball.velocityX = -ball.velocityX;
// 球碰到了画布的右边框
} else if (ballRight > canvas.width) {
ball.left = canvas.width - ball.radius * 2;
ball.velocityX = -ball.velocityX;
}

// 球碰到了画布的上边框
if (ball.top < 0) {
ball.top = 0;
ball.velocityY = -ball.velocityY;
// 球碰到了画布的下边框
} else if (ballBottom > canvas.height) {
ball.top = canvas.height - ball.radius * 2;
ball.velocityY = -ball.velocityY;
}
}

// 重新绘制图帧
function animate(time) {
context.clearRect(0, 0, canvas.width, canvas.height);
ball.move();
handleEdgeCollisions(ball);
ball.paint();
requestAnimationFrame(animate);
}

var canvas = document.getElementById('canvas');
context = canvas.getContext('2d');
ball = new Ball(context);

ball.paint();
requestAnimationFrame(animate);
</script>

</html>


rect1.x < rect2.x + rect2.width && rect2.x < rect1.x + rect1.width
&&
rect1.y < rect2.y + rect2.height && rect2.y < rect1.y + rect1.height


// 矩形碰撞检测的逻辑,返回true 表示发生了碰撞, 返回false 表示未发生碰撞, 下同
function handleEgdeCollisions(rect1, rect2) {
return rect1.left < rect2.left + rect2.width && rect2.left < rect1.left + rect1.width && rect1.top < rect2.top + rect2.height && rect2.top < rect1.height + rect1.top;
}


• 相对局限：两物体必须是矩形，且均不允许旋转，即上面的矩形的边必须平行于坐标轴.
• 对于包含着图案（非填满整个矩形）的矩形进行碰撞检测，可能存在精度不足的问题。例如你写一个坦克大战游戏

• （类）矩形物体间的碰撞。

#### 圆形碰撞（Circle Collision）

function handleEgdeCollisions(circle1, circle2) {
var circle1X = circle1.left + circle1.radius;
var circle1Y = circle1.top + circle1.radius;
var circle2X = circle2.left + circle2.radius;
var circle2Y = circle2.top + circle2.radius;
var distance = Math.sqrt(Math.pow(circle1X - circle2X, 2) + Math.pow(circle1Y - circle2Y, 2));
}


#### 圆形与无旋转矩形

1. 判断圆心是不是在矩形内部，如果都在内部的话，没什么好说的，肯定发生碰撞了.
2. 然后直接暴力计算圆心到矩形的四条边的最短距离.

• 如果圆心在矩形的左侧（if(circle.x < rect.x)），那么closestPoint.x = rect.x

function detectCollision(rect, circle) {
var cx, cy;
if (circle.x < rect.x) {
cx = rect.x;
} else if (circle.x > rect.x + rect.w) {
cx = rect.x + rect.w;
} else {
cx = circle.x;
}
if (circle.y < rect.y) {
cy = rect.y;
} else if (circle.y > rect.y + rect.h) {
cy = rect.y + rect.h;
} else {
cy = circle.y;
}
return distance(circle.x, circle.y, cx, cy) < circle.r;
}


#### 圆形与旋转矩形（以矩形中心为旋转轴）

function detectCollision(rect, circle) {
var cx, cy;
// 矩形中心
var rectCenterX = rect.x + rect.w / 2;
var rectCenterY = rect.y + rect.h / 2;
// 顺时针旋转 angleOfRad 后的圆心坐标
var rotateCircleX = Math.cos(angleOfRad) * (circle.x - rectCenterX) - Math.sin(angleOfRad) * (circle.y - rectCenterY) + rectCenterX;
var rotateCircleY = Math.sin(angleOfRad) * (circle.x - rectCenterX) + Math.cos(angleOfRad) * (circle.y - rectCenterY) + rectCenterY;
if (rotateCircleX < rect.x) {
cx = rect.x;
} else if (rotateCircleX > rect.x + rect.w) {
cx = rect.x + rect.w;
} else {
cx = rotateCircleX;
}
// 和圆形与无旋转矩形一样的步骤获取矩形上距离圆心最近的点
if (rotateCircleY < rect.y) {
cy = rect.y;
} else if (rotateCircleY > rect.y + rect.h) {
cy = rect.y + rect.h;
} else {
cy = rotateCircleY;
}
return distance(rotateCircleX, rotateCircleY, cx, cy) < circle.r;
}


#### 地图格子划分

map = [[0, 0, 1, 1, 1, 0, 0, 0, 0],
[0, 1, 1, 0, 0, 1, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 1, 0, 0],
[0, 1, 0, 0, 0, 0, 1, 0, 0],
[0, 1, 1, 1, 1, 1, 1, 0, 0]];
function handleEgdeCollisions(player, map) {
return map[player.top][player.left];
}


#### 像素检测（Pixel checking）

// rect 是交集矩形 P
function handleEgdeCollisions(rect) {
// 取出熊猫在 P 中的像素字节数组
var imgData1 = offscreenContextPanda.getImageData(rect.left, rect.top, rect.width, rect.height);
// 取出竹子在 P 中的像素字节数组
var imgData2 = offscreenContextBamboo.getImageData(rect.left, rect.top, rect.width, rect.height);
var imgData1Data = imgData1.data;
var imgData2Data = imgData2.data;
// 这里一个像素 4字节, 所以 i += 4
for(var i = 3, len = imgData1Data.length; i < len; i += 4) {
if(imgData1Data[i] > 0 && imgData2Data[i] > 0) {
return true
}
}
return false
}


#### 分离轴定理（Separating Axis Theorem SAT）

function polygonsCollide(polygon1, polygon2) { // 检测 polygon1 和 polygon2 两个多边形是否碰撞, 返回 true 表示发生了碰撞, 返回 false 表示没有发生碰撞
var axes, projection1, projection2; // 投影轴
// 根据多边形获取所有投影轴
axes = polygon1.getAxes();
axes.push(polygon2.getAxes());
// 遍历所有投影轴，获取多边形在每条投影轴上的投影
for(each axis in axes) {
projection1 = polygon1.project(axis)
projection2 = polygon2.project(axis)
// 判断投影轴上的投影是否存在重叠
if(!projection1.overlaps(projection2))
return false
}
return true
}


• 如何确定多边形的各个投影轴，也就是上述 getAxes 函数怎么实现
• 如何将多边形投射到某条投影轴上，也就是上述 project 函数怎么写
• 如何检测两段投影是否发生重叠, 也就是上述 overlaps 函数怎么写

##### 判断重叠（overlaps）

projection1.max > projection2.min && projection2.max > projection1.min


#### 圆形与多边形之间的碰撞检测

<html>
<style type="text/css">
* {
margin: 0;
}

canvas {
border: 1px solid orange;
margin: 20px auto 0;
display: block;
}
</style>
<body>
<canvas id="canvas" width="600" height="280"></canvas>
</body>
<script>
// 封装向量
var Vector = function(point) {
if (point === undefined) {
this.x = 0;
this.y = 0;
}
else {
this.x = point.x;
this.y = point.y;
}
}

Vector.prototype = {
// 获取向量的模
getMagnitude: function() {
return Math.sqrt(Math.pow(this.x, 2) + Math.pow(this.y, 2))
},
// 向量的加法
var v = new Vector()
v.x = this.x + vector.x
v.y = this.y + vector.y
return v
},
// 向量的减法
subtract: function(vector) {
var v = new Vector()
v.x = this.x - vector.x
v.y = this.y - vector.y
return v
},
// 点积
dotProduct: function(vector) {
return this.x * vector.x + this.y * vector.y
},

// 生成起点为vector的向量
edge: function(vector) {
return this.subtract(vector)
},

// 法向量, 即投影轴
perpendicular: function() {
var v = new Vector()
v.x = this.y
v.y = -this.x
return v
},
// 规范化
normalize: function() {
var v = new Vector(0, 0),
m = this.getMagnitude()

if(m !== 0) {
v.x = this.x / m
v.y = this.y /m
}
return v
},

// 投影轴的单位向量
normal: function() {
var p = this.perpendicular()
return p.normalize()
}
}

// 封装投影
var Projection = function(min, max) {
this.min = min
this.max = max
}

Projection.prototype = {
overlaps: function(projection) {
return this.max > projection.min && projection.max > this.min
}
}

// 封装多边形
var Shape = function() {
this.x = undefined
this.y = undefined
this.strokeStyle = 'rgba(255, 253, 208, 0.9)'
this.fillStyle = 'rgba(147, 147, 147, .8)'
}

Shape.prototype = {
// 返回 true 表示两个多边形相交, 否则没有
collidesWith: function(shape) {
// 计算两个多边形的所有投影轴
var axes = this.getAxes().concat(shape.getAxes())
return !this.separationOnAxes(axes, shape)
},
// 返回 true 表示分离轴存在, 即这两个多边形不相交
separationOnAxes: function(axes, shape) {
for(var i = 0, len = axes.length; i < len; i++) {
axis = axes[i]
projection1 = shape.project(axis)
projection2 = this.project(axis)
// 一旦发现不重叠, 则分离轴存在
if(!projection1.overlaps(projection2)) {
return true
}
}
return false
},

// 抽象类不实现方法, 实现交给子类 Polygon
project: function(axis) {
throw 'project(axis) not implemented'
},

getAxes: function() {
throw 'getAxes() not implemented'
},

move: function(dx, dy) {
throw 'move(dx, dy) not implemented'
},

createPath: function(context) {
throw 'createPath(context) not implemented'
},

// 模板设计模式
fill: function(context) {
context.save()
context.fillStyle = this.fillStyle
this.createPath(context)
context.fill()
// 恢复画布设置
context.restore()
},

stroke: function(context) {
context.save()
context.strokeStyle = this.strokeStyle
this.createPath(context)
context.stroke()
context.restore()
},

// 如果指定的点位于当前路径中，则返回 true，否则返回 false
isPointInPath: function(context, x, y) {
this.createPath(context)
return context.isPointInPath(x, y)
}
}

// 封装点
var Point = function(x, y) {
this.x = x
this.y = y
}

// 封装(凸)多边形
var Polygon = function() {
this.points = []
this.strokeStyle = 'blue'
this.fillStyle = 'white'
}

// 在凸多边形的原型链上挂Shape, 表明 凸多边形是 Shape 类型的, 则 new Polygon 可以调用 Shape 的方法
Polygon.prototype = new Shape()

// 获取凸多边形的投影轴
Polygon.prototype.getAxes = function() {
var v1 = new Vector(),
v2 = new Vector(),
axes = []

for(var i = 0, len = this.points.length - 1; i < len; i++) {
v1.x = this.points[i].x
v1.y = this.points[i].y

v2.x = this.points[i + 1].x
v2.y = this.points[i + 1].y
// v2v1
axes.push(v1.edge(v2).normal())
}
// 别漏了最后一条边
v1.x = this.points[this.points.length - 1].x
v1.y = this.points[this.points.length - 1].y

v2.x = this.points[0].x
v2.y = this.points[0].y

axes.push(v1.edge(v2).normal())

return axes
}

// 获取多边形到投影轴 axis 上的投影 scalars （标量的意思）
Polygon.prototype.project = function(axis) {
var scalars = [],
v = new Vector()
// 遍历多边形所有的顶点
this.points.forEach(function(point) {
v.x = point.x
v.y = point.y
// 做点积, 即做投影
scalars.push(v.dotProduct(axis))
})
// 得到多边形在 axis 投影轴上的投影范围
return new Projection(Math.min.apply(Math, scalars), Math.max.apply(Math, scalars))
}

Polygon.prototype.addPoint = function(x, y) {
this.points.push(new Point(x, y))
}

// 画多边形
Polygon.prototype.createPath = function(context) {
if(this.points.length === 0) {
return
}

context.beginPath()
context.moveTo(this.points[0].x, this.points[0].y)

for(var i = 0, len = this.points.length; i < len; i++) {
context.lineTo(this.points[i].x, this.points[i].y)
}

context.closePath()
}

// 多边形平移 (dx, dy) , 用于实现拖拽回调
Polygon.prototype.move = function(dx, dy) {
for(var i = 0, point, len = this.points.length; i < len; i++) {
point = this.points[i]
point.x += dx
point.y += dy
}
}

// 多边形是否和shape（圆形或者凸多边形）发生碰撞
Polygon.prototype.collidesWith = function(shape) {
var axes = shape.getAxes()
if(axes === undefined) {
return polygonCollidesWithCircle(this, shape)
} else {
axes = axes.concat(this.getAxes())
return !this.separationOnAxes(axes, shape)
}
}

// 封装圆形
var Circle = function(x, y, radius) {
this.x = x
this.y = y
this.strokeStyle = 'rgba(255, 253, 208, .9)'
this.fillStyle = 'rgba(147, 197, 114, .8)'
}

Circle.prototype = new Shape()

// 圆形是否和 shape （圆形或者凸多边形） 发生碰撞
Circle.prototype.collidesWith = function(shape) {
var point, length, min = 10000, v1, v2,
edge, perpendicular, normal,
axes = shape.getAxes(), distance
// shape 是圆形
if(axes === undefined) {
distance = Math.sqrt(Math.pow(shape.x - this.x, 2) + Math.pow(shape.y - this.y, 2))
// shape 是凸多边形
} else {
return polygonCollidesWithCircle(shape, this)
}
}

// 圆形的投影轴取决于判断是否和它相交的凸多边形, 而不能由圆形自己决定, 所以这里取 undefined
Circle.prototype.getAxes = function() {
return undefined
}

// 圆形向投影轴 axis 的投影
Circle.prototype.project = function(axis) {
var scalars = [],
point = new Point(this.x, this.y),
dotProduct = new Vector(point).dotProduct(axis)

scalars.push(dotProduct)

return new Projection(Math.min.apply(Math, scalars),
Math.max.apply(Math, scalars))
}

// 圆形平移, 用于实现拖拽回调
Circle.prototype.move = function(dx, dy) {
this.x += dx
this.y += dy
}

Circle.prototype.createPath = function(context) {
context.beginPath()
context.arc(this.x, this.y, this.radius, 0, Math.PI * 2, false)
}

// 获取和圆心最近的凸多边形上的一个点
function getPolygonPointClosestToCircle(polygon, circle) {
var min = 10000, length, testPoint, closestPoint

for(var i = 0, len = polygon.points.length; i < len; i++) {
testPoint = polygon.points[i]
length = Math.sqrt(Math.pow(testPoint.x - circle.x, 2), Math.pow(testPoint.y - circle.y, 2))

if(length < min) {
min = length
closestPoint = testPoint
}
}

return closestPoint
}

// 凸多边形 和 圆形是否发生碰撞
function polygonCollidesWithCircle(polygon, circle) {
var min = 10000, v1, v2,
edge, perpendicular,
axes = polygon.getAxes(),
closestPoint = getPolygonPointClosestToCircle(polygon, circle)
v1 = new Vector(new Point(circle.x, circle.y))
v2 = new Vector(new Point(closestPoint.x, closestPoint.y))
axes.push(v1.subtract(v2).normalize()) // 在凸多边形的投影轴基础上再加一条圆形的投影轴
return !polygon.separationOnAxes(axes, circle)
}

var canvas = document.getElementById('canvas'),
context = canvas.getContext('2d'),
shapes = [],
polygonPoints = [
[ new Point(250, 150), new Point(250, 250),
new Point(350, 250) ],

[ new Point(100, 100), new Point(100, 150),
new Point(150, 150), new Point(150, 100) ],

[ new Point(400, 100), new Point(380, 150),
new Point(500, 150), new Point(520, 100) ]
],

polygonStrokeStyles = [ 'blue', 'yellow', 'red'],
polygonFillStyles   = [ 'rgba(255,255,0,0.7)',
'rgba(100,140,230,0.6)',
'rgba(255,255,255,0.8)' ],

circle1 = new Circle(150, 75, 20),
circle2 = new Circle(350, 45, 30),

mousedown = { x: 0, y: 0 },
lastdrag = { x: 0, y: 0 },
// 被拖拽的图形
shapeBeingDragged = undefined;
// 根据鼠标在浏览器窗口中点击的位置计算出在画布中的坐标
function windowToCanvas(e) {
var x = e.x || e.clientX,
y = e.y || e.clientY,
bbox = canvas.getBoundingClientRect();

return { x: x - bbox.left * (canvas.width  / bbox.width),
y: y - bbox.top  * (canvas.height / bbox.height)
};
};

function drawShapes() {
shapes.forEach( function (shape) {
shape.stroke(context);
shape.fill(context);
});
}
function detectCollisions() {
var textY = 30,
numShapes = shapes.length,
shape,
i;

if (shapeBeingDragged) {
for(i = 0; i < numShapes; ++i) {
shape = shapes[i];

if (shape !== shapeBeingDragged) {
if (shapeBeingDragged.collidesWith(shape)) {
context.fillStyle = shape.fillStyle;
context.fillText('撞了...', 20, textY);
textY += 40;
}
}
}
}
}

canvas.onmousedown = function (e) {
var location = windowToCanvas(e);
// 确定画布中被拖拽的图形（shape）是哪一个
shapes.forEach( function (shape) {
if (shape.isPointInPath(context, location.x, location.y)) {
shapeBeingDragged = shape;
mousedown.x = location.x;
mousedown.y = location.y;
lastdrag.x = location.x;
lastdrag.y = location.y;
}
});
}

canvas.onmousemove = function (e) {
var location,
dragVector;

if (shapeBeingDragged !== undefined) {
location = windowToCanvas(e);
dragVector = { x: location.x - lastdrag.x,
y: location.y - lastdrag.y
};

shapeBeingDragged.move(dragVector.x, dragVector.y);

lastdrag.x = location.x;
lastdrag.y = location.y;

context.clearRect(0,0,canvas.width,canvas.height);
drawShapes();
detectCollisions();
}
}

canvas.onmouseup = function (e) {
shapeBeingDragged = undefined;
}

for (var i=0; i < polygonPoints.length; ++i) {
var polygon = new Polygon(),
points = polygonPoints[i];

polygon.strokeStyle = polygonStrokeStyles[i];
polygon.fillStyle = polygonFillStyles[i];

points.forEach( function (point) {
});

shapes.push(polygon);
}

shapes.push(circle1)
shapes.push(circle2)

context.font = '38px Arial';

drawShapes();

context.save();
context.fillStyle = 'cornflowerblue';
context.font = '24px Arial';
context.fillText('拖拽物体', 10, 25);
context.restore();
</script>

</html>


#### 关于碰撞检测的优化

Broad phase 能为你提供有可能碰撞的实体列表。这可通过一些特殊的数据结构实现，它们能为你提供这些信息：实体存在哪里和哪些实体在其周围。这些数据结构可以是：四叉树（Quad Trees）、八叉树（OcTree）、R树（R-Trees）或空间哈希映射（Spatial Hashmap）等，但据笔者所知，R 树在数据库的高维索引方面应用可能更加广泛，而不是用于游戏中的碰撞检测. 关于四叉树、八叉树，后续推文会再介绍.

0 条评论

• ### 一个关于仰望，崇拜和梦想的故事

从我接触程序竞赛到现在应该有十多年了，单说ACM竞赛，从第一次非正式参赛到现在也差不多有7年多的样子。有太多的故事，想说的话，却一直没能有机会写...

• ### 农夫与牛（STL-Queue、广度优先搜索）

现有一农夫和一母牛，假设农夫和母牛都站在一条数轴上，农夫开始的位置为N，母牛的位置为K。农夫有三种行动方式，每行动一次需要一秒钟时间，假设农夫的现在的位置为X，...

• ### DP专题 3 | LCS最长公共子序列 - POJ 1458

A subsequence of a given sequence is the given sequence with some elements (poss...

• ### 50行javaScript代码实现简单版的 call , apply ,bind 【中级前端面试基础必备】

其实 this 的指向，始终坚持一个原理：this 永远指向最后调用它的那个对象,这就是精髓。最关键所在

• ### 设计模式 | 建造者模式

这个设计模式主要是解决复杂对象的创建问题, 使这个抽象过程的不同实现方法可以构造出不同表现（属性）的对象。

• ### 【JS 口袋书】第 8 章：以更细的角度来看 JS 中的 this

JS 中的this关键字对于初学者来说是一个谜，对于经验丰富的开发人员来说则是一个永恒的难题。this 实际上是一个移动的目标，在代码执行过程中可能会发生变化，...

• ### Uncaught Error: _registerComponent(...): Target container is not a DOM element

Uncaught Error: _registerComponent(...): Target container is not a DOM element

• ### Laravel源码分析之Route

路由是外界访问Laravel应用程序的通路或者说路由定义了Laravel的应用程序向外界提供服务的具体方式：通过指定的URI、HTTP请求方法以及路由参数（可选...

• ### 聊聊原型 Prototype | 技术创作101训练营

原型和原型链，一直是 JavaScript 中的重要概念，也是面试官必问的知识点，或许有的同学认为，自己虽然没有很深入了解过原型和原型链，但并不影响自己日常的开...