点 P 是否在三角形内部

原理：

假设有一个三角形 $\triangle$ABC，有一点 P，如何判断点 P 是否在三角形内部呢？

如果点 P 在三角形内部，那么对于 $\overrightarrow{AB}$，假定 C 在左边，那么 P 也在左边

这个问题本来是二维的，但是可以从三维来判断方向，那么点 A、B、C、P 的 z 轴值都是 0

三维向量的叉乘：

向量 $\boldsymbol{a}=(x_a, y_a, z_a)$，向量 $\boldsymbol{b}=(x_b, y_b, z_b)$，

三维空间中单位向量 $\boldsymbol{i}=(1,0,0)$，$\boldsymbol{j}=(0,1,0)$，$\boldsymbol{k}=(0,0,1)$，

那么叉乘： \(\vec{a} \times \vec{b} = (y_az_b - z_ay_b, z_ax_b - x_az_b, x_ay_b - y_az_b)\) 可以看到，如果我们在二维平面计算，那么前两轴都是 0，因为叉乘得到的向量是垂直于原来的两个向量的，这里就是垂直于 x-y 平面。

所以 $\overrightarrow{AB} \times \overrightarrow{AC}$ 得到垂直于二维平面的一个向量 $\boldsymbol{z_1} = (0, 0, x_{ab}y_{ac} - x_{ac}y_{ab})$

同理 $\overrightarrow{AB} \times \overrightarrow{AP}$ 得到向量 $\boldsymbol{z_2}$

向量 $\boldsymbol{z_1}$ 和 $\boldsymbol{z_2}$ 的 x 轴和 y 轴都是 0，不需要管，z 轴要么都是正数，要么都是负数，因为是同向，当然也可能是 0，由此可判断是否同向

判断完 P 和 C 在边 $\overrightarrow{AB}$ 同一侧后，同理也去判断 P 和 A 在 $\overrightarrow{BC}$ 同一侧，P 和 B 在 $\overrightarrow{CA}$ 同一侧

都符合，那就说明 P 在三角形 $\triangle$ABC 内部

代码：

bool IsSameSide(const vector<double> &a, const vector<double> &b, const vector<double> &c, const vector<double> &p) {
    const vector<double> ab = {b[0]-a[0], b[1]-a[1]};
    const vector<double> ac = {c[0]-a[0], c[1]-a[1]};
    const vector<double> ap = {p[0]-a[0], p[1]-a[1]};

    const double z1 = ab[0]*ac[1] - ab[1]*ac[0];
    const double z2 = ab[0]*ap[1] - ab[1]*ap[0];
    return z1 * z2 >= 0;
}

bool IsPointInTriangle(const vector<double> &a, const vector<double> &b, const vector<double> &c, const vector<double> &p) {
    return IsSameSide(a, b, c, p) && IsSameSide(b, c, a, p) && IsSameSide(c,a, b, p);
}