戰魂小筑

前幾天需要做一個鼠標點擊判定，具體是判斷一個點是否在某個凸四邊形中。

最簡單的方法莫過于判斷鼠標點是否在2個三角形中。但是很多判定方法都是有問題的，比如說

copy自IndieLib

bool Triangle2D::Inside2( const Vector2& p )
{
    Vector2 v0 = mP3 - mP1;
    Vector2 v1 = mP2 - mP1;
    Vector2 v2 = p - mP1; 

    // Compute dot products
    float dot00 =  Vector2::DotProduct( v0, v0 );
    float dot01 =  Vector2::DotProduct( v0, v1 );
    float dot02 =  Vector2::DotProduct( v0, v2 );
    float dot11 =  Vector2::DotProduct( v1, v1 );
    float dot12 =  Vector2::DotProduct( v1, v2 ); 

    // Compute barycentric coordinates
    float invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
    float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
    float v = (dot00 * dot12 - dot01 * dot02) * invDenom; 

    // Check if point is in triangle
    return (u > 0) && (v > 0) && (u + v < 1);
} 

  

Google出的某人代碼

float Triangle2D::CrossProduct3(const Vector2& p1,const Vector2& p2, const Vector2& p0 )
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
} 

bool Triangle2D::Inside( const Vector2& p )
{
    return (CrossProduct3(mP1,p,mP2)*CrossProduct3(mP3,p,mP2)<0) &&
           (CrossProduct3(mP2,p,mP1)*CrossProduct3(mP3,p,mP1)<0) &&
           (CrossProduct3(mP1,p,mP3)*CrossProduct3(mP2,p,mP3)<0);
} 

這2個方法都有缺陷，當點在三角形邊上時，就無法得出。當用在一個正方形判斷時，正方形中心點就判定為沒有在其內部，顯然是一個錯誤。

之后，又Google出某幾個大俠的算法和思想，考慮了下，判定點與四邊形重心點的線段是否與四邊形4條邊相交，相交時，其在四邊形外部，反之亦然。

bool Quadrangle::Inside2( const Vector2& p )
{
    Vector2 c = Segement2D::GetCrossPoint( mP1, mP3, mP2, mP4 ); 

    return !(Segement2D::Intersect( mP1, mP2, c, p) || 
           Segement2D::Intersect( mP2, mP3, c, p) ||
           Segement2D::Intersect( mP3, mP4, c, p) ||
           Segement2D::Intersect( mP4, mP1, c, p) );
} 

bool Segement2D::Intersect( const Vector2& p1, const Vector2& p2,const Vector2& p3, const Vector2& p4 )
{
    float gradab, gradcd, ycptab, ycptcd, interceptX, intercepty; 

    // In order to avoid divisions by zero
    //if (mP1.y == mP2.y)
    //    mP2.y += 0.0001f; 

    //if (mP1.x == mP2.x)
    //    mP2.x += 0.0001f; 

    //if (seg.mP1.y == seg.mP2.y)
    //    seg.mP2.y += 0.0001f; 

    //if (seg.mP1.x == seg.mP2.x)
    //    seg.mP2.x += 0.0001f; 

    // Calculates the intersection between the two lines
    gradab = (p1.y - p2.y) / (p1.x - p2.x);
    gradcd = (p3.y - p4.y) / (p3.x - p4.x); 

    ycptab = p1.y - p1.x * gradab;
    ycptcd = p3.y - p3.x * gradcd;
    interceptX = (ycptab - ycptcd) / (gradcd - gradab);
    intercepty = (ycptab - (gradab * ycptcd) / gradcd) / (1 - gradab / gradcd); 

    // Checking in the intersection is inside the segment
    if (!((interceptX >= p1.x && interceptX <= p2.x) || (interceptX >= p2.x && interceptX <= p1.x)))
        return 0; 

    if (!((intercepty >= p1.y && intercepty <= p2.y) || (intercepty >= p2.y && intercepty <= p1.y)))
        return 0; 

    if (!((interceptX >= p3.x && interceptX <= p4.x) || (interceptX >= p4.x && interceptX <= p3.x)))
        return 0; 

    if (!((intercepty >= p3.y && intercepty <= p4.y) || (intercepty >= p4.y && intercepty <= p3.y)))
        return 0; 

    return 1;
} 

Vector2 Segement2D::GetCrossPoint(const Vector2& p1, const Vector2& p2, const Vector2& q1, const Vector2& q2)
{
    //必須相交求出的才是線段的交點，但是下面的程序段是通用的 

    /*根據兩點式化為標準式，進而求線性方程組*/
    Vector2 crossPoint;
    //求x坐標
    float tempLeft = (q2.x - q1.x) * (p1.y - p2.y) - (p2.x - p1.x) * (q1.y - q2.y);
    float tempRight = (p1.y - q1.y) * (p2.x - p1.x) * (q2.x - q1.x) + q1.x * (q2.y - q1.y) * (p2.x - p1.x) - p1.x * (p2.y - p1.y) * (q2.x - q1.x);
    crossPoint.x = tempRight / tempLeft;
    //求y坐標
    tempLeft = (p1.x - p2.x) * (q2.y - q1.y) - (p2.y - p1.y) * (q1.x - q2.x);
    tempRight = p2.y * (p1.x - p2.x) * (q2.y - q1.y) + (q2.x- p2.x) * (q2.y - q1.y) * (p1.y - p2.y) - q2.y * (q1.x - q2.x) * (p2.y - p1.y);
    crossPoint.y = tempRight / tempLeft; 

    return crossPoint;
}

這個算法效率并不是很高，但對于設計器來說無所謂了，如果有好的準確算法，可以討論