二维平面上判断点在三角形内的最优算法

admin1

[code]// 2D vector
class Vec2
{
public:
    Vec2()
    {
        x = 0.0f;
        y = 0.0f;
    }

    Vec2(float fx, float fy)
        :x(fx), y(fy)
    {
    }

    // Add
    Vec2 operator + (const Vec2& v) const
    {
        return Vec2(x + v.x, y + v.y);
    }

    // Subtract
    Vec2 operator - (const Vec2& v) const
    {
        return Vec2(x - v.x, y - v.y) ;
    }


public:
    float x, y;
};[/code]


[code][/code][code]// Dot product
inline float Vec2Dot(const Vec2& v1, const Vec2& v2)
{
    return v1.x * v2.x + v1.y * v2.y;
}

// Cross product
inline float Vec2Cross(const Vec2& v1, const Vec2& v2)
{
    return v1.x * v2.y - v1.y * v2.x;
}

// Determine whether two vectors v1 and v2 point to the same direction
// 判断C和P在直线AB的同一侧
inline bool IsSameSide(const Vec2& A, const Vec2& B, const Vec2& C, const Vec2& P)
{
    Vec2 AB = B - A;
    Vec2 AC = C - A;
    Vec2 AP = P - A;

    float f1 = Vec2Cross(AB, AC);
    float f2 = Vec2Cross(AB, AP);

    // f1 and f2 should to the same direction
    return f1*f2 >= 0.0f;
}

// Same side method
// Determine whether point P in triangle ABC
inline bool IsPointInTriangle(const Vec2& A, const Vec2& B, const Vec2& C, const Vec2& P)
{
    return IsSameSide(A, B, C, P) &&
        IsSameSide(B, C, A, P) &&
        IsSameSide(C, A, B, P);
}

// Determine whether point P in angle ABC
// 点P是否在角ABC内
inline bool IsPointInAngle(const Vec2& A, const Vec2& B, const Vec2& C, const Vec2& P)
{
    return IsSameSide(A, B, C, P) && IsSameSide(B, C, A, P);
}[/code]