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

园子里有很多关于点是否在三角形内的文章，提供了各种方法。这让人很纠结，到底该用哪种算法？这里提供一套我认为最优的算法。如果你有不同的意见，亦或有更好的算法，欢迎来讨论。

算法使用的是同向法，其原理是：假设点P位于三角形ABC内，会有这样一个规律：三角形的每一个边，其对角点与P在边的同一侧；或者说三角形的每一个顶点与Ｐ在其对角边的同一侧。

一、代码

    public class Vec2
    {
        public float x, y;
        public Vec2()
        {
            x = 0.0f;
            y = 0.0f;
        }

        public Vec2(float fx, float fy)
        {
            x = fx;
            y = fy;
        }

        // Add
        public static Vec2 operator +(Vec2 x, Vec2 y)
        {
            return new Vec2(x.x + y.x, y.y + y.y);
        }

        public static Vec2 operator -(Vec2 x, Vec2 y)
        {
            return new Vec2(x.x - y.x, y.y - y.y);
        }

    }

    public class Vec2Helper
    {

        // Dot product
        public static float Vec2Dot(Vec2 v1, Vec2 v2)
        {
            return v1.x * v2.x + v1.y * v2.y;
        }

        // Cross product
        public static float Vec2Cross(Vec2 v1, 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的同一侧
        public static bool IsSameSide(Vec2 A, Vec2 B, Vec2 C, 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
        public static bool IsPointInTriangle(Vec2 A, Vec2 B, Vec2 C, 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内
        public static bool IsPointInAngle(Vec2 A, Vec2 B, Vec2 C, Vec2 P)
        {
            return IsSameSide(A, B, C, P) && IsSameSide(B, C, A, P);
        }
    }

注：以上代码是本站根据原文修改成的C#版代码，原文代码请见文章末尾的连接地址。

二、测试效果

我生成一幅1024*1024大小的图像，并设置三个顶点，对图像中的所有像素调用IsPointInAngle函数，以测试其效率：

图中显示出图像生成时间为868.758毫秒，这是DEBUG版本的(注，此时间是作者统计的时间)。

本文来源：http://www.cnblogs.com/WhyEngine/p/4064686.html