空间中判断点在三角形内算法(方程法)
目录
1. 概述
三维空间中判断点在三角形内外的算法与平面中有所不同，《平面中判断点在三角形内算法(同向法)》中提到的算法在三维空间中已经无法生效，也很难利用上。一个最简单的思路就是，获取三角形的空间向量方程，判断点是否能让这个空间向量方程成立。
2. 详论
2.1. 原理
在我的另外一篇文章《空间射线与三角形相交算法的两种实现》中提到了三角形的空间向量方程。对于三个顶点为V0，V1，V2组成的空间三角形，对于三角形内的任一点P，有如下参数方程：
→P=(1−u−v)→V0+u→V1+v→V2P→=(1−u−v)V0→+uV1→+vV2→
变换位置，有：
→P−→V0=(→V0−→V1)u+(→V0−→V2)vP→−V0→=(V0→−V1→)u+(V0→−V2→)v
→V0P=(→V0V1)u+(→V0V2)vV0P→=(V0V1→)u+(V0V2→)v
其中，u，v是未知的，而使用的向量是三维向量。显然，这是一个超定方程组。求解这个方程组，如果解是矛盾的，说明点不在空间三角形内；否则，点可能在三角形上。
2.2. 实现
具体的C++代码如下：
//空间三角形 //按照逆时针顺序插入值并计算法向量 template <class T> class Triangle { public: Vec3<T> v0; Vec3<T> v1; Vec3<T> v2; Vec3<T> vn; Vec3<T> min; Vec3<T> max; Triangle() { } Triangle(Vec3<T> v0, Vec3<T> v1, Vec3<T> v2) { this->v0 = v0; this->v1 = v1; this->v2 = v2; } void Set(Vec3<T> v0, Vec3<T> v1, Vec3<T> v2) { this->v0 = v0; this->v1 = v1; this->v2 = v2; } // 判断点P是否在空间三角形内 bool PointInTriangle3D(Vec3<T>& P) { auto v0p = P - v0; auto v0v1 = v1 - v0; auto v0v2 = v2 - v0; double D = v0v1.x() * v0v2.y() - v0v1.y() * v0v2.x(); if(D == 0.0) { return false; } double D1 = v0p.x() * v0v2.y() - v0p.y() * v0v2.x(); double D2 = v0v1.x() * v0p.y() - v0v1.y() * v0p.x(); double u = D1/D; double v = D2/D; double eps = v0v1.z() * u + v0v2.z() * v - P.z(); if(u >= 0 && v >= 0 && u + v <= 1 && abs(eps) < 0.000001) { return true; } return false; }
这里采取的算法是，通过x，y分量组成的两个方程式解出方程组的暂时u、v。然后将u、v带入到z分量方程式，检查能否保证z分量方程式成立。如果成立，且满足三角形内部点方程的条件（u >= 0， v >= 0， u + v <= 1），说明点在空间三角形上，反之，点在空间三角形外。
3. 参考
分类: 计算几何
