平面中判斷點在三角形内算法(重心法)

通過重心法，判斷平面中點在三角形内外關系。

目錄

• 1. 概述
• 2. 詳論
  • 2.1. 原理
  • 2.2. 實作
  • 2.3. 總結
• 3. 參考

在文章《判斷點是否在三角形内》中還提到了一種判斷點在三角形内外的算法——重心法。這種算法同樣用到了三角形的空間向量方程，但是值得注意的是，這種算法卻隻能判斷平面中點在三角形的内外關系(已知空間向量方程，是可以判斷三維空間關系的:空間中判斷點在三角形内算法(方程法))。

重心法的推導過程與空間中判斷點在三角形内算法(方程法))的推導過程比較相似。對于三個頂點為V0，V1，V2組成的空間三角形，對于三角形内的任一點P，有如下參數方程：

\[\vec{P} = (1 - u - v) \vec{V_0} + u \vec{V_1} + v \vec{V_2}

\]

變換位置，我們可以将其調整為：

\[\vec{V_0P} = u(\vec{V_0V_1}) + v(\vec{V_0V_2})

将上式分别點乘\(\vec{V_0V_1}\)和\(\vec{V_0V_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}

很顯然，這是個2行2列的線性方程組，通過克萊姆法則來求解：

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}) \\

u = D1 / D \\

v = D2 / D \\

詳細的代碼實作如下：

//空間三角形
//按照逆時針順序插入值并計算法向量
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 ;
    }

};
           

本質上，這個算法與空間中判斷點在三角形内算法(方程法)是同一種算法的不同推導，都是通過空間三角形中點的向量方程來求解的，但是是采用了不同的解法。不過為什麼一個可以判斷空間關系，一個隻能判斷平面關系呢？關鍵在于點是否能讓向量方程成立，這個求解算法可以求解u，v，但沒有保證空間内的向量方程能夠成立。

1. 判斷點是否在三角形内
2. 空間中判斷點在三角形内算法(方程法))

詳細代碼