http://blog.csdn.net/anikan_yu/article/details/1154035上的伪代码简洁易懂，在应用到这题时要注意精度，可以拿1e-4f作为极小值。
贴出判定线段相交的模板： 
double CJ(double x1,double y1,double x2,double y2,double x3,double y3)
{
    double xa=x3-x1,ya=y3-y1,xb=x2-x1,yb=y2-y1;
    return xa*yb-xb*ya;
}
bool OS(double x1,double y1,double x2,double y2,double x3,double y3)
{
    if(x3-min(x1,x2)>=1e-4f && max(x1,x2)-x3>=1e-4f && y3-min(y1,y2)>=1e-4f && min(y1,y2)-y3>=1e-4f) return 1;
    return 0;
}
bool inter(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4)
{
    double d1=CJ(x3,y3,x4,y4,x1,y1),d2=CJ(x3,y3,x4,y4,x2,y2),d3=CJ(x1,y1,x2,y2,x3,y3),d4=CJ(x1,y1,x2,y2,x4,y4);
    if(((d1>=1e-4f && d2<=-(1e-4f)) || (d1<=-(1e-4f) && d2>=1e-4f)) && ((d3>=1e-4f && d4<=-(1e-4f)) || (d3<=-(1e-4f) && d4>=(1e-4f)))) 
        return 1;
    if(d1<1e-4f && OS(x3,y3,x4,y4,x1,y1)) return 1;
    if(d2<1e-4f && OS(x3,y3,x4,y4,x2,y2)) return 1;
    if(d3<1e-4f && OS(x1,y1,x2,y2,x3,y3)) return 1;
    if(d4<1e-4f && OS(x1,y1,x2,y2,x4,y4)) return 1;
    return 0;
}

• Re:计算几何——线段相交 (1104) lidabao 2012-07-15 12:53:57