射线法判断一个点是否在多边形内部

更新时间: 2021-12-13 10:43:09

# 原理

首先我们先随便画一个多边形，为了避免有特殊性，我就画得随意一点：
怎么样，够不够复杂刁钻，然后判断一下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
}

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
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)

旋转矩阵 →