判断一个点是否在三角形内

---

判断点$P$是否在$\triangle ABC$组成的三角形内

---

面积法

---

如果 $\triangle PAB,\triangle PAC,\triangle PBC$ 三个三角形的面积和等于三角形$\triangle ABC$的面积，则代表点$P$在$\triangle ABC$内

---

内角和法

---

连接点$P$和$\triangle ABC$三个顶点得到$\vec{pa},\vec{pb},\vec{pc}$;

求出这三条线段与三角形的个边的夹角，如果所有夹角之和为$180^\circ$，则点$P$在$\triangle ABC$内

---

同向法

---

沿$\triangle ABC$，$\vec{AB},\vec{BC},\vec{CA}$，点$P$在同一侧，则点$P$在$\triangle ABC$内

static bool insideTriangle(int x, int y, const Vector3f* _v)
{   
    // TODO : Implement this function to check if the point (x, y) is inside the triangle represented by _v[0], _v[1], _v[2]
    // Vector3f v(x,y,0.0);
    // float z0 = (v-_v[0]).cross(_v[1] - _v[0]).z();
    // float z1 = (v-_v[1]).cross(_v[2] - _v[1]).z();
    // float z2 = (v-_v[2]).cross(_v[0] - _v[2]).z();
    // if(z0>0&&z1>0&&z2>0){return true;}
    // else if(z0<0&&z1<0&&z2<0){return true;}
    // return false;

    // Vector3f v[3];
    // for(int i=0;i<3;i++)
    //     v[i] = Vector3f(_v[i].x(),_v[i].y(), 0.0f);
    // Vector3f p(x,y,0.0f);
    // Vector3f f0 = (p-v[0]).cross(v[1] - v[0]);
    // Vector3f f1 = (p-v[1]).cross(v[2] - v[1]);
    // Vector3f f2 = (p-v[2]).cross(v[0] - v[2]);
    // p.z() = 1.0f;
    // if((p.dot(f0) > 0 && p.dot(f1) > 0 && p.dot(f2) > 0) || (p.dot(f0) < 0 && p.dot(f1) < 0 && p.dot(f2) < 0)){return true;}
    // return false;

    Vector3f v[3];
    for(int i=0;i<3;i++)
        v[i] = {_v[i].x(),_v[i].y(), 1.0};
    Vector3f f0,f1,f2;
    f0 = v[1].cross(v[0]);
    f1 = v[2].cross(v[1]);
    f2 = v[0].cross(v[2]);
    Vector3f p(x,y,1.);
    if((p.dot(f0)*f0.dot(v[2])>0) && (p.dot(f1)*f1.dot(v[0])>0) && (p.dot(f2)*f2.dot(v[1])>0))
        return true;
    return false;
}

---

重心法

---

$$\vec{AP}=u*\vec{AB}+v*\vec{AC}$$

• 1.u>=0
• 2.v>=0

• 3.u+v<=1
  满足上述条件则点$P$在$\triangle ABC$内

• 1.v==0,则点$P$在$\vec{AB}$ 上

• 2.u==0,则点$P$在$\vec{AC}$ 上
• 3.u+v==1,则点$P$在$\vec{BC}$ 上

bool IsPointInTriangle(lt::Vector3<float> p, lt::Vector3<float> a, lt::Vector3<float> b, lt::Vector3<float> c) {
	lt::Vector2<float> ap = p - a;
	lt::Vector2<float> ab = b - a;
	lt::Vector2<float> ac = c - a;
	float u = 0, v = 0;
	u = (ap.x * ac.y - ac.x*ap.y) / (ab.x * ac.y - ac.x * ab.y);
	v = (ap.x * ab.y - ab.x*ap.y) / (ac.x * ab.y - ab.x * ac.y);
	return u >= 0 && v >= 0 && u + v <= 1;
}

---