平面中判断点在三角形内算法(重心法)

文章目录

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}) V0​P ​=u(V0​V1​ ​)+v(V0​V2​ ​)

将上式分别点乘 V 0 V 1 ⃗ \vec{V_0V_1} V0​V1​ ​和 V 0 V 2 ⃗ \vec{V_0V_2} V0​V2​ ​,有:
{ 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} {V0​P ​⋅V0​V1​ ​=u(V0​V1​⋅V0​V1​ ​)+v(V0​V2​ ​⋅V0​V1​ ​)V0​P ​⋅V0​V2​ ​=u(V0​V1​ ​⋅V0​V2​ ​)+v(V0​V2​ ​⋅V0​V2​ ​)​

很显然,这是个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=(V0​V1​⋅V0​V1​ ​)∗(V0​V2​ ​⋅V0​V2​ ​)−(V0​V2​ ​⋅V0​V1​ ​)∗(V0​V1​ ​⋅V0​V2​ ​)D1=(V0​P ​⋅V0​V1​ ​)∗(V0​V2​ ​⋅V0​V2​ ​)−(V0​V2​ ​⋅V0​V1​ ​)∗(V0​P ​⋅V0​V2​ ​)D2=(V0​V1​⋅V0​V1​ ​)∗(V0​P ​⋅V0​V2​ ​)−(V0​P ​⋅V0​V1​ ​)∗(V0​V1​ ​⋅V0​V2​ ​)​

{ 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,但没有保证空间内的向量方程能够成立。

3. 参考

  1. 判断点是否在三角形内
  2. 空间中判断点在三角形内算法(方程法))

详细代码

上一篇:数组延伸.


下一篇:Linux 下实现 MySQL 数据库每天自动备份定时备份