判断一个点是不是在一个多边形内是很经典的计算几何问题。一般可以是凸多边形也可以是凹多边形。

简单的特例：三角形

方法一

比较常用的算法是射线法，以要判断的点为起点任作一射线，计算该射线与多边形的交点数目。
若有偶数个交点则在形外，否则在形内。
若与线段在端点处相交或重合，则要进行复杂的判断。此时可另取一射线。

方法二

面积法：海伦公式、向量公式

方法三

向量法

例子

http://hihocoder.com/contest/hiho225/problem/1

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/*
在三角形内部的点形成的都是钝角三角形
点在x,y的中间并不能判断
*/

#include <bits/stdc++.h>
#define LL long double
using namespace std;

const double eps = 1e-5;
LL Heron(LL a, LL b, LL c)
{
    return 0.25 * sqrt((a + b + c) * (a + b - c) * (a + c - b) * (b + c - a));
}

LL Distance(LL x1, LL y1, LL x2, LL y2)
{
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int main()
{
    int T;
    cin >> T;
    while (T--) {
        LL x[4], y[4];
        for (int i = 0; i < 4; i++) cin >> x[i] >> y[i];
        LL s = 0;
        for (int i = 1; i <= 2; i++) {
            for (int j = i + 1; j < 4; j++) {
                LL a = Distance(x[0], y[0], x[i], y[i]), b = Distance(x[0], y[0], x[j], y[j]), c = Distance(x[i], y[i], x[j], y[j]);
                s += Heron(a, b, c);
            }
        }
        LL a = Distance(x[1], y[1], x[2], y[2]), b = Distance(x[1], y[1], x[3], y[3]), c = Distance(x[2], y[2], x[3], y[3]);
        //cout << s << ' ' << Heron(a, b, c) << endl;
        if (abs(s - Heron(a, b, c)) < eps) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

/*
输入的都是整数，三角形面积计算s=0.5*(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2));
所有面积里都有这个0.5，去掉这个0.5对结果不影响，于是面积计算出来就是整数，没有精度问题了。
向量法求面积。
*/
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL area(LL x1,LL y1,LL x2,LL y2,LL x3,LL y3)
{
    return abs(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2));
}

int main()
{
    LL Px, Py, Ax, Ay, Bx, By, Cx, Cy;
    LL S, S1, S2, S3;
    LL t;
    for(cin>>t;t>0;t--)
    {
        cin>>Px>>Py>>Ax>>Ay>>Bx>>By>>Cx>>Cy;
        S  = area(Ax, Ay, Bx, By, Cx, Cy);
        S1 = area(Px, Py, Ax, Ay, Bx, By);
        S2 = area(Px, Py, Ax, Ay, Cx, Cy);
        S3 = area(Px, Py, Bx, By, Cx, Cy);
        if(S1+S2+S3<=S)cout<<"YES\n";else cout<<"NO\n";
    }
    return 0;
}

/*
还有个简单的方法，判断三条边的向量与P跟三个点连接的向量的叉积，如果三个叉积值同正负，则在三角形内。
*/

#define G(v,_) scanf("%ld",&v),v-=_;
main(T){long p,P,a,A,b,B,c,C,x,y,z;for(G(T,0)T--;puts(((-x|-y|-z)&(x|y|z))<0?"NO":"YES")){G(p,0)G(P,0)G(a,p)G(A,P)G(b,p)G(B,P)G(c,p)G(C,P)x=a*B-b*A;y=b*C-c*B;z=c*A-a*C;}return 0;}

四边形特例：矩形

（1）面积和判别法：判断目标点与多边形的每条边组成的三角形面积和是否等于该多边形，相等则在多边形内部。
（2）夹角和判别法：判断目标点与所有边的夹角和是否为360度，为360度则在多边形内部。
（3）引射线法：从目标点出发引一条射线，看这条射线和多边形所有边的交点数目。如果有奇数个交点，则说明在内部，如果有偶数个交点，则说明在外部。

https://blog.csdn.net/u283056051/article/details/53980832
1、射线法理论：从这个点做一条射线，计算它跟多边形边界的交点个数，如果交点个数为奇数，那么点在多边形内部，否则点在多边形外。
2、特殊情况特殊处理：

1. 点在多边形的边上 ：判断点与边端点连线斜率是否相同。
2. 点和多边形的顶点重合 ：直接hash。
3. 射线经过多边形顶点：只需要规定被射线穿越的点都算作其中一侧。 
4. 射线刚好经过多边形的一条边：上面的特例，经过两个顶点。射线连续经过的两个顶点显然都位于射线以上的一侧，因此这种情况看作没有发生穿越就可以了。

多边形代码（射线法和回转数法）

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/*
测试题：http://hihocoder.com/problemset/problem/1450?sid=1416458
射线法没有过，回转数法连样例都不了，还弄不明白哪里错了。
参考：https://blog.csdn.net/u283056051/article/details/53980832
*/
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e3 + 5;
const double eps = 1e-5;
const double PI = atan(1) * 4;

struct node {
    int x, y;
};

// 射线法
string RayCasting(node p, node poly[], int n)
{
    bool flag = false;
    // 首尾相连n条边
    for (int i = 0, j = n - 1; i < n; j = i, i++) {
        int sx = poly[i].x, sy = poly[i].y;
        int ex = poly[j].x, ey = poly[j].y;
        // 1、判断p点和多边形顶点是否重合
        if ((p.x == sx && p.y == sy) || (p.x == ex && p.y == ey)) return "on";
        // 2、做一条水平射线，判断边两断点是否在射线两侧，并令穿过顶点的点在上端
        if ((sy < p.y && ey >= p.y) || (sy >= p.y && ey < p.y)) {
            // 3、判断p点是否在多边形边上，斜率公式或者三角形比例公式（方便）
            double x = sx + (p.y - sy) * (ex - sx) * 1.0 / (ey - sy);
            if (abs(x - p.x) < eps) return "on";
            // 水平向右作的射线，穿过一次就变换
            if (x > p.x) flag = !flag;
        }
    }
    return flag ? "in" : "out";
}

// 回转数法
string WindingNumber(node p, node poly[], int n)
{
    double sum = 0;  // 回转度数和
    // 首尾相连n条边
    for (int i = 0, j = n - 1; i < n; j = i, i++) {
        int sx = poly[i].x, sy = poly[i].y;
        int ex = poly[j].x, ey = poly[j].y;
        // 1、判断p点和多边形顶点是否重合或在多边形边上
        if ((p.x == sx && p.y == sy) || (p.x == ex && p.y == ey) || (p.x - sx) * (ey - sy) == (p.y - sy) * (ex - sx)) return "on";
        // 2、求夹角
        double angle = atan((sy - p.y) * 1.0 / (sx - p.x)) - atan((ey - p.y) * 1.0 / (ex - p.x));
        cout << angle << endl;
        // 3、确保夹角不超过取值范围（-PI到PI）
        if (angle >= PI) angle -= 2 * PI;
        else if (angle <= -PI) angle += 2 * PI;
        sum += angle;
    }
    cout << sum << endl;
    // 4、计算回转数
    return round(sum / PI) == 0 ? "out" : "in";

}

int main()
{
    node p, poly[maxn];
    int n = 3, T;
    cin >> T;
    while (T--) {
        cin >> p.x >> p.y;
        for (int i = 0; i < n; i++) {
            cin >> poly[i].x >> poly[i].y;
        }
        string res1 = RayCasting(p, poly, 3);
        string res2 = WindingNumber(p, poly, 3);
        if (res1 != res2) cout << "Wrong" << endl;
        else if (res1 == "out") cout << "NO" << endl;
        else cout << "YES" << endl;
    }
    return 0;
}