平面中判断点在三角形内算法(重心法)
目录
1. 概述
在文章《判断点是否在三角形内》中还提到了一种判断点在三角形内外的算法——重心法。这种算法同样用到了三角形的空间向量方程，但是值得注意的是，这种算法却只能判断平面中点在三角形的内外关系(已知空间向量方程，是可以判断三维空间关系的:空间中判断点在三角形内算法(方程法))。
2. 详论
2.1. 原理
重心法的推导过程与空间中判断点在三角形内算法(方程法))的推导过程比较相似。对于三个顶点为V0，V1，V2组成的空间三角形，对于三角形内的任一点P，有如下参数方程：
→P=(1−u−v)→V0+u→V1+v→V2P→=(1−u−v)V0→+uV1→+vV2→
变换位置，我们可以将其调整为：
→V0P=u(→V0V1)+v(→V0V2)V0P→=u(V0V1→)+v(V0V2→)
将上式分别点乘→V0V1V0V1→和→V0V2V0V2→，有：
{→V0P⋅→V0V1=u(→V0V1⋅→V0V1)+v(→V0V2⋅→V0V1)→V0P⋅→V0V2=u(→V0V1⋅→V0V2)+v(→V0V2⋅→V0V2){V0P→⋅V0V1→=u(V0V1⋅V0V1→→)+v(V0V2→⋅V0V1→)V0P→⋅V0V2→=u(V0V1→⋅V0V2→)+v(V0V2→⋅V0V2→)
很显然，这是个2行2列的线性方程组，通过克莱姆法则来求解：
⎧⎪ ⎪ ⎪⎨⎪ ⎪ ⎪⎩D=(→V0V1⋅→V0V1)∗(→V0V2⋅→V0V2)−(→V0V2⋅→V0V1)∗(→V0V1⋅→V0V2)D1=(→V0P⋅→V0V1)∗(→V0V2⋅→V0V2)−(→V0V2⋅→V0V1)∗(→V0P⋅→V0V2)D2=(→V0V1⋅→V0V1)∗(→V0P⋅→V0V2)−(→V0P⋅→V0V1)∗(→V0V1⋅→V0V2){D=(V0V1⋅V0V1→→)∗(V0V2→⋅V0V2→)−(V0V2→⋅V0V1→)∗(V0V1→⋅V0V2→)D1=(V0P→⋅V0V1→)∗(V0V2→⋅V0V2→)−(V0V2→⋅V0V1→)∗(V0P→⋅V0V2→)D2=(V0V1⋅V0V1→→)∗(V0P→⋅V0V2→)−(V0P→⋅V0V1→)∗(V0V1→⋅V0V2→)
{u=D1/Dv=D2/D{u=D1/Dv=D2/D
2.2. 实现
详细的代码实现如下：
//空间三角形 //按照逆时针顺序插入值并计算法向量 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; } void Set(Vec3<T> v0, Vec3<T> v1, Vec3<T> v2) { this->v0 = v0; this->v1 = v1; this->v2 = v2; } // 判断平面点P是否在平面三角形内(重心法) bool PointInTriangle2D(Vec3<T>& P) { auto v01 = v1 - v0 ; auto v02 = v2 - v0 ; auto v0p = P - v0 ; double dot00 = v01 * v01 ; double dot01 = v01 * v02 ; double dot02 = v01 * v0p ; double dot11 = v02 * v02 ; double dot12 = v02 * v0p ; double D = (dot00 * dot11 - dot01 * dot01); if(D == 0.0) { return false; } double inverDeno = 1 / D ; double u = (dot11 * dot02 - dot01 * dot12) * inverDeno ; if (u < 0 || u > 1) { return false ; } double v = (dot00 * dot12 - dot01 * dot02) * inverDeno ; if (v < 0 || v > 1) { return false ; } return u + v <= 1 ; } };
2.3. 总结
本质上，这个算法与空间中判断点在三角形内算法(方程法)是同一种算法的不同推导，都是通过空间三角形中点的向量方程来求解的，但是是采用了不同的解法。不过为什么一个可以判断空间关系，一个只能判断平面关系呢？关键在于点是否能让向量方程成立，这个求解算法可以求解u，v，但没有保证空间内的向量方程能够成立。
3. 参考
分类: 计算几何
