文章目录
1. 概述
在文章《判断点是否在三角形内》中还提到了一种判断点在三角形内外的算法——重心法。这种算法同样用到了三角形的空间向量方程，但是值得注意的是，这种算法却只能判断平面中点在三角形的内外关系(已知空间向量方程，是可以判断三维空间关系的:空间中判断点在三角形内算法(方程法))。
2. 详论
2.1. 原理
重心法的推导过程与空间中判断点在三角形内算法(方程法))的推导过程比较相似。对于三个顶点为V0，V1，V2组成的空间三角形，对于三角形内的任一点P，有如下参数方程：
P ⃗ = ( 1 − u − v ) V 0 ⃗ + u V 1 ⃗ + v V 2 ⃗ \vec{P} = (1 - u - v) \vec{V_0} + u \vec{V_1} + v \vec{V_2} P =(1−u−v)V0 +uV1 +vV2
变换位置，我们可以将其调整为：
V
0
P
⃗
=
u
(
V
0
V
1
⃗
)
+
v
(
V
0
V
2
⃗
)
\vec{V_0P} = u(\vec{V_0V_1}) + v(\vec{V_0V_2})
V0P
=u(V0V1
)+v(V0V2
)
将上式分别点乘
V
0
V
1
⃗
\vec{V_0V_1}
V0V1
和
V
0
V
2
⃗
\vec{V_0V_2}
V0V2
，有：
{
V
0
P
⃗
⋅
V
0
V
1
⃗
=
u
(
V
0
V
1
⋅
V
0
V
1
⃗
⃗
)
+
v
(
V
0
V
2
⃗
⋅
V
0
V
1
⃗
)
V
0
P
⃗
⋅
V
0
V
2
⃗
=
u
(
V
0
V
1
⃗
⋅
V
0
V
2
⃗
)
+
v
(
V
0
V
2
⃗
⋅
V
0
V
2
⃗
)
\begin{cases} \vec{V_0P} \cdot \vec{V_0V_1} = u(\vec{V_0V_1 \cdot \vec{V_0V_1}}) + v(\vec{V_0V_2} \cdot \vec{V_0V_1}) \\ \vec{V_0P} \cdot \vec{V_0V_2} = u(\vec{V_0V_1} \cdot \vec{V_0V_2}) + v(\vec{V_0V_2} \cdot \vec{V_0V_2}) \\ \end{cases}
{V0P
⋅V0V1
=u(V0V1⋅V0V1
)+v(V0V2
⋅V0V1
)V0P
⋅V0V2
=u(V0V1
⋅V0V2
)+v(V0V2
⋅V0V2
)
很显然，这是个2行2列的线性方程组，通过克莱姆法则来求解：
{
D
=
(
V
0
V
1
⋅
V
0
V
1
⃗
⃗
)
∗
(
V
0
V
2
⃗
⋅
V
0
V
2
⃗
)
−
(
V
0
V
2
⃗
⋅
V
0
V
1
⃗
)
∗
(
V
0
V
1
⃗
⋅
V
0
V
2
⃗
)
D
1
=
(
V
0
P
⃗
⋅
V
0
V
1
⃗
)
∗
(
V
0
V
2
⃗
⋅
V
0
V
2
⃗
)
−
(
V
0
V
2
⃗
⋅
V
0
V
1
⃗
)
∗
(
V
0
P
⃗
⋅
V
0
V
2
⃗
)
D
2
=
(
V
0
V
1
⋅
V
0
V
1
⃗
⃗
)
∗
(
V
0
P
⃗
⋅
V
0
V
2
⃗
)
−
(
V
0
P
⃗
⋅
V
0
V
1
⃗
)
∗
(
V
0
V
1
⃗
⋅
V
0
V
2
⃗
)
\begin{cases} D = (\vec{V_0V_1 \cdot \vec{V_0V_1}}) * (\vec{V_0V_2} \cdot \vec{V_0V_2}) - (\vec{V_0V_2} \cdot \vec{V_0V_1}) * (\vec{V_0V_1} \cdot \vec{V_0V_2}) \\ D1 = (\vec{V_0P} \cdot \vec{V_0V_1}) * (\vec{V_0V_2} \cdot \vec{V_0V_2}) - (\vec{V_0V_2} \cdot \vec{V_0V_1}) * (\vec{V_0P} \cdot \vec{V_0V_2}) \\ D2 = (\vec{V_0V_1 \cdot \vec{V_0V_1}}) * (\vec{V_0P} \cdot \vec{V_0V_2}) - (\vec{V_0P} \cdot \vec{V_0V_1}) * (\vec{V_0V_1} \cdot \vec{V_0V_2}) \\ \end{cases}
⎩⎪⎪⎨⎪⎪⎧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 = D 1 / D v = D 2 / D \begin{cases} u = D1 / D \\ v = D2 / D \\ \end{cases} {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，但没有保证空间内的向量方程能够成立。