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

叶飞影

发表于2014-10-31 14:14:57

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

算法使用的是同向法,其原理是:假设点P位于三角形ABC内,会有这样一个规律:三角形的每一个边,其对角点与P在边的同一侧;或者说三角形的每一个顶点与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