录十六

求线段交点，是计算几何中一种非常基础的计算几何算法。但是发现网上的好几种算法，性能都不是特别好。下面提供一种在国外论坛上发现的，效率比较高的算法。

如下图所示，已知线段A(P1，P2) 和线段B(P3，P4)，求两条线段的交点P。

根据向量知识，可知：

P = P1 + u_a ( P2 - P1 )        P = P3 + u_b ( P4 - P3 )

当线段A和B相交，交点为P时，有0≤u_a≤1，0≤u_b≤1，那么：

根据以上两个等式，求得：

最终完整的代码如下：

typedef struct Point2D
{
    float x;
    float y;

}Point2D;

enum STATUS
{
    NON_INTERSECT = 0, //不相交
    INTERESECT    = 1, //相交 
    COINCIDENT    = 2, //重合
    PARALLEL      = 3, //平行
};

STATUS LineIntersect(const Point2D& P1, const Point2D& P2, 
                     const Point2D& P3, const Point2D& P4, Point2D *Pt)
{
    float  numera = (P4.x-P3.x) * (P1.y-P3.y) - (P4.y-P3.y) * (P1.x-P3.x);
    float  numerb = (P2.x-P1.x) * (P1.y-P3.y) - (P2.y-P1.y) * (P1.x-P3.x);

    float  denom  = (P4.y-P3.y) * (P2.x-P1.x) - (P4.x-P3.x) * (P2.y-P1.y);

    if(denom == 0.0f)
    {
        if(numera == 0.0f && numerb == 0.0f)
        {
            return COINCIDENT;
        }
        return PARALLEL;
    }

    float ua = numera / denom;
    float ub = numerb / denom;

    if(ua >= 0.0f && ua <= 1.0f && ub >= 0.0f && ub <= 1.0f)
    {
        Pt->x = P1.x + ua*(P2.x - P1.x);
        Pt->y = P1.y + ua*(P2.y - P1.y);

        return INTERESECT;
    }

    return NON_INTERSECT;
}