怎么编“判断点与三角形的位置关系”这个程序 谢谢！ 急

请问这个程序怎么编
读入一点的坐标和三角形的顶点坐标，判断该点在三角形内，在三角形边界上，还是在边界之外。

Input 

4个点坐标，每个一行。

Output 

点在三角形内，输出In 
点在三角形边上，输出On 
点在三角形外，输出Out

Sample Input 


0 0
-1 0
1 0
0 1

Sample Output 


On

5 个解决方案

#1

用向量叉乘。首先选择一个顶点，然后和判断的这个点相连，得到一条线段，然后分别和共点的的两条边进行叉乘，判断正负，一正一负则这个点在这两条线段之间，再用相同的方法选择另外两条边，如果还是在两条线段间，则这个点在三角形内，一组不满足则在三角形外面，如果叉乘得出一个0，一个一个正或者两个0则在三角形边上。

#2

int Test( const gtl::Vec3f& V0, const gtl::Vec3f& V1, const gtl::Vec3f& V2,  
                       gtl::Vec3f& I )
{
   gtl::Vec3f    u, v, n;             // triangle vectors  
    // get triangle edge vectors and plane normal  
    u = V1 - V0;  
    v = V2 - V0;  
    n = u.cross(v);  
   //// is I inside T?  
    float    uu, uv, vv, wu, wv, D;  
  
    uu = u.dot(u);  
    uv = u.dot(v);  
    vv = v.dot(v);  
    w = I - V0;  
    wu = w.dot(u);  
    wv = w.dot(v);  
    D = uv * uv - uu * vv;  
  
    // get and test parametric coords  
    float s, t;  
    s = (uv * wv - vv * wu) / D;  
    if (s < 0.0 || s > 1.0)        // I is outside T  
        return 0;  
    t = (uv * wu - uu * wv) / D;  
    if (t < 0.0 || (s + t) > 1.0)  // I is outside T  
        return 0;  
  
    return 1;                      // I is in T  
}

参见： http://blog.csdn.net/dizuo/article/details/5324770

#3

谢谢了

#4

 #include<iostream>
using namespace std;

// == 0 三点共线，但是不能确定方向。
// <  0 23在12的顺时针方向。
// >  0 23在12的逆时针方向。
// -----------------------------------------------------------------向量叉乘
double cross_product(double x1, double y1, double x2, double y2,
double x3, double y3)
{
    return (x3 - x2) * (y2 - y1) - (y3 - y2) * (x2 - x1);
}

// -------------------------------------------------某点与指定的三角形的关系
string  ptTra(double x1, double y1, double x2, double y2,
double x3, double y3, double x,  double y)
{
    double cp1 = cross_product(x1, y1, x2, y2, x, y);
    double cp2 = cross_product(x2, y2, x3, y3, x, y);
    double cp3 = cross_product(x3, y3, x1, y1, x, y);
    if(cp1 < 0 && cp2 < 0 && cp3 < 0)
     return "In";
    if(cp1 == 0 || cp2 == 0 || cp3 == 0)
     return "on";
    return "out";

}

int main()
{
double pt[8];
for(int i=0;i<8;i++)
cin>>pt[i];
    cout<<ptTra(pt[2],pt[3],pt[4],pt[5],pt[6],pt[7],pt[0],pt[1])<<endl;
return 0;
}

叉乘判断下方向关系：
如果叉乘结果都<0,三角形内;
其中一个结果=0，则在三角形上;
否则三角形外。

#5

上面判断在三角形内部的有点小错误，应该是叉乘结果的符号一致，要么都小于0.要么都大于0。