平面中判断点在三角形内算法(同向法)
目录
1. 概述
平面中判断点在三角形内外有很多中算法，文献1中提到了一种同向法，我认为是比较好的解法，兼顾了效率和可理解性。不过这个算法有两个要注意的地方。
2. 详论
2.1. 原理与实现
同向法的具体算法摘录如下：
关键的实现代码如下：
//空间三角形 //按照逆时针顺序插入值并计算法向量 template <class T> class Triangle { public: Vec3<T> v0; Vec3<T> v1; Vec3<T> v2; Triangle() { } Triangle(Vec3<T> v0, Vec3<T> v1, Vec3<T> v2) { this->v0 = v0; this->v1 = v1; this->v2 = v2; } // v1 = Cross(AB, AC) // v2 = Cross(AB, AP) // 判断矢量v1和v2是否同向 bool SameSide(Vec3<T>& A, Vec3<T>& B, Vec3<T>& C, Vec3<T>& P) { Vec3<T> AB = B - A ; Vec3<T> AC = C - A ; Vec3<T> AP = P - A ; Vec3<T> v1 = AB ^ AC; Vec3<T> v2 = AB ^ AP; // v1 and v2 should point to the same direction return v1*v2 >= 0 ; //return v1 * v2 > 0 ; } // 判断平面点P是否在平面三角形内 bool PointInTriangle2D(Vec3<T>& P) { Vec3<T> A(v0.x(), v0.y(), 0); Vec3<T> B(v1.x(), v1.y(), 0); Vec3<T> C(v2.x(), v2.y(), 0); return SameSide(A, B, C, P) && SameSide(B, C, A, P) && SameSide(C, A, B, P); } };
2.2. 注意事项
第一个要注意的是，为了方便表达出向量的叉积，使用了三维向量而不是二维向量。但是这个算法是针对的是平面而不是空间，也就是判断空间中点是否在三角形内是无效的。并且，传入的三维向量的第三分量最好都为0，否则，无法保证算法的有效性。
第二是点是通过点积来判断是否同向：
bool SameSide(Vec3<T>& A, Vec3<T>& B, Vec3<T>& C, Vec3<T>& P) { Vec3<T> AB = B - A ; Vec3<T> AC = C - A ; Vec3<T> AP = P - A ; Vec3<T> v1 = AB ^ AC; Vec3<T> v2 = AB ^ AP; // v1 and v2 should point to the same direction return v1*v2 >= 0 ; //return v1 * v2 > 0 ; }
理论上，两点积等于0，说明两向量是直角。但是这里的>=0考虑的是零向量的问题，零向量点乘任何点向量还是0。那么什么时候会出现零向量呢？当点正好在三角形的边界上的时候（两个相同的向量的叉积为零向量）。也就是说，这里的=0可以判断点正好在三角形的边界或者顶点上，而>0才是判断点是否在三角形的内部。使用的时候可以灵活掌握。
3. 参考
分类: 计算几何
