战魂小筑

前几天需要做一个鼠标点击判定，具体是判断一个点是否在某个凸四边形中。

最简单的方法莫过于判断鼠标点是否在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;
}

这个算法效率并不是很高，但对于设计器来说无所谓了，如果有好的准确算法，可以讨论