碰撞判断之射线法

引子
刚学编程时,编写小游戏,经常用到碰撞检测.比如贪吃蛇,如何判断碰到食物,或者碰到墙.
因为整个canvas都划分了格子.所以判断很简单.检测蛇头与食物的索引就可以.也算不上碰撞检测.
如果是需要手指点击的.就稍微复杂点.不过由于都是规则图形.矩形可以用九宫格判断法(判断四边与点击位置).
圆形用中心判断(判断圆心与点击位置距离).这些算法很简单.但无法应付内凹多边形.
通过检索.学习了一种射线检测法

原理
如果一个点对任意方向做射线与一个多边形的交点是奇数个,则点在多边形内部.
多边形相交

实现

对上述原理抽象下.
一个点(A)对左侧做水平射线,是否与一条线相交.(水平或垂直方向方便计算.上下左右均可)
线由两点(B,C)连接而成.
点由坐标(x,y)构成

则问题进一步分解为
垂直方向上,A点是否在BC之间

水平方向上,A点是否在B或C的右侧

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const checkPointInPolyline = (point, polylinePoints) => {
let leftSide = 0;
const A = point;
for (let i = 0; i < polylinePoints.length; i++) {
let B, C;
if (i === polylinePoints.length - 1) {
B = {
x: polylinePoints[i][0],
y: polylinePoints[i][1]
};
C = {
x: polylinePoints[0][0],
y: polylinePoints[0][1]
};
} else {
B = {
x: polylinePoints[i][0],
y: polylinePoints[i][1]
};
C = {
x: polylinePoints[i + 1][0],
y: polylinePoints[i + 1][1]
};
}
// 对BC排序,确定上下
let sortByY = [B.y, C.y].sort((a,b) => a-b)
if (sortByY[0] < A.y && sortByY[1] > A.y){
if(B.x<A.x || C.x < A.x){
leftSide++
}
}
}

return leftSide % 2 === 1
}

参考博文 监听Canvas内部元素点击事件的三种方法