射线法判断一个点是否在多边形内部
# 原理
首先我们先随便画一个多边形,为了避免有特殊性,我就画得随意一点:
怎么样,够不够复杂刁钻,然后判断一下P这个点在不在多边形里面,你别告诉我用眼睛看,我打不死你哦。
# 射线法原理
那到底要怎么办呢,有种方法叫射线法(别问,这方法不是我想出来的),即从P点引出一条射线,看这条射线和多边形相交的次数。
假如P点在多边形外,那么P点射线和多边形相交情况一定是:
穿入 -> ..(中间可能有N次穿入穿出)... ->穿出,即穿入穿出的次数是偶数次,交点是偶数个。
假如P点在多边形内,那么P点射线和多边形相交的情况一定是:
穿出 -> ...(后面可能有N次穿入穿出)...,总之最后一定是穿出,交点是奇数个。
是不是听不懂,我写得也有点晕乎,接下来看图吧:
# 一般情况
首先是P点在多边形外:
要么一个相交点也没有,要么是双数个
然后是P点在多边形内:
相交点总共是1个或者奇数个
# 特殊情况
因为所有方向的射线都是一样的,所以为了分析方便,我们使用从P点开始的一条水平线作为射线来分析。 然而还有特殊情况:
P点在多边形顶点上
这个还是很好判断,通过对比P的坐标和多边形顶点坐标就可以了P点在多边形线段上
可以求P点射出的射线和线段AB的交点,假如交点的坐标等于P点,那么P点就在多边形的线上
P点和多边形的交点是顶点
实际上明眼很容易看出P点不在多边形内或多边形上,但是交点只有A点一个,这样就不符合射线法的判断标准了。因为我们变通一下,判断一下,P点的射线,和AB,AC线段有没有相交,如果相交次数是偶数,就没有在多边形里,相交次数是奇数,就算在多边形里了。
判断线段有没有和射线P相交,只需要判断线段的两个端点是不是在P点两侧,将A点判定为在射线的上侧,那么现在就可以判定,射线P和AB,AC都相交,相交两次为偶数。P点的射线刚好经过多边形的一条边
按照刚刚第三点的解决方案,线段AB的两个顶点都在射线P上侧,所以没有和P相交,射线P和AF,BC线段相交两次为偶数,所以P在多边形外。 而射线P1,根据第三点的方案,ED两个顶点都在线段上方,所以线段ED没有和P1相交,线段FE,CD也没有和P1相交,相交次数为0,所以P在多边形外。P点的射线刚好经过多边形一条边,并且P点在这条边上
这种情况按照第四点的解析方法会判定成不相交,所以还需要判定一下,假如E点D点P点y坐标相等,同时P点的x坐标在ED的x坐标中间,就可以判定为第五种特殊情况。
# 代码解析
原理分析完毕,现在开始撸代码,js版本哦,我只会js了:
/**
* p :[x,y] ,带判定的P点
* poly: [[x0,y0],[x1,y1]......] 多边形的路径
*/
function rayCasting(p, poly) {
// px,py为p点的x和y坐标
let px = p[0],
py = p[1],
flag = false
//这个for循环是为了遍历多边形的每一个线段
for(let i = 0, l = poly.length, j = l - 1; i < l; j = i, i++) {
let sx = poly[i][0], //线段起点x坐标
sy = poly[i][1], //线段起点y坐标
tx = poly[j][0], //线段终点x坐标
ty = poly[j][1] //线段终点y坐标
// 点与多边形顶点重合
if((sx === px && sy === py) || (tx === px && ty === py)) {
return true
}
// 点的射线和多边形的一条边重合,并且点在边上
if((sy === ty && sy === py) && ((sx > px && tx < px) || (sx < px && tx > px))) {
return true
}
// 判断线段两端点是否在射线两侧
if((sy < py && ty >= py) || (sy >= py && ty < py)) {
// 求射线和线段的交点x坐标,交点y坐标当然是py
let x = sx + (py - sy) * (tx - sx) / (ty - sy)
// 点在多边形的边上
if(x === px) {
return true
}
// x大于px来保证射线是朝右的,往一个方向射,假如射线穿过多边形的边界,flag取反一下
if(x > px) {
flag = !flag
}
}
}
// 射线穿过多边形边界的次数为奇数时点在多边形内
return flag ? true : false
}
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
36
37
38
39
40
41
42
43
44
45
46
47
其中高亮的第31行理解起来可能有点困难,我们画个图理解一下:
线段AB和射线P相交于C点,已知P、A、B的坐标,求C点坐标。我们已经知道C点的y坐标等于P点的y坐标,所以只要求x坐标就好。
C点x坐标 = B点x坐标 + 线段BD的长度
而三角形BCD相似于三角形BAE,所以线段
CD : AE = BD : BE
所以: BD = CD * BE / AE
假设A点坐标是(tx,ty),B点坐标是(sx,sy)
就等于: BD = (py - sy) * (tx - sx) / (ty - sy)
所以,交点C的x坐标为 sx + (py - sy) * (tx - sx) / (ty - sy)