點是否存在三角形內

前言

會有這個需求是前陣子試了試 Unity 新的 UI Toolkit，並給小項目加個選色盤的機能，用外環選定色相之後，可以用內圈的三角形決定明度與飽和度。

但是，問題就出在這裡，因為是連外環一併渲染的（共享輸入事件），所以我需要判斷滑鼠點擊事件是否在內圈三角形內。

定義

$ p_x $：目標點

$ p_a $、$ p_b $、$ p_c $：順時針三角形頂點

叉乘法

叉乘定義為：

$$
a \times b= \Vert a \Vert \Vert b \Vert sin(\theta) n
$$

這個 $n$ 是依照右手定則決定的，三指方向分別對應：

• 中指 $b$
• 食指 $a$
• 拇指 $a \times b$

或是用 👍 四指收起表示由 $a$ 轉到 $b$。

而 $ \Vert a \Vert \Vert b \Vert sin(\theta) $ 計算長度，我們只在乎正負，也就是 $n$。

叉乘的結果必定與兩輸入向量垂直，但這裡是 UI 元件，輸入向量的 z 皆為 0，直接取結果 z 的正負就行了。

所以只要確定：

• $\vec{p_a p_x} \times \vec{p_a p_b}$
• $\vec{p_b p_x} \times \vec{p_b p_c}$
• $\vec{p_c p_x} \times \vec{p_c p_a}$

正負相同，代表點在三角形內。

// k_Vertices 為頂點陣列
bool CheckInsideTriangle(Vector2 p)
{
    Func<Vector2, Vector2, bool> checker = null;

    for (int i = 0; i < k_Vertices.Length; ++i)
    {
        Vector2 p1 = k_Vertices[i].position;
        Vector2 p2 = k_Vertices[(i + 1) % k_Vertices.Length].position;

        var v0 = p - p1;
        var v1 = p2 - p1;

        if (checker is null)
        {
            checker = Vector3.Cross(v0, v1).z > 0 ?
                (a, b) => Vector3.Cross(a, b).z > 0 :
                (a, b) => Vector3.Cross(a, b).z < 0;
        }
        else if (!checker(v0, v1))
            return false;
    }

    return true;
}

重心法

以某一頂點為原點（這裡用 $p_a$）將三頂點轉換成：

• $ p_a = (0,0) $
• $ p_b = \vec{p_a p_b} $
• $ p_c = \vec{p_a p_c} $

則 $ p_x $ 如果在三角形內，可用 $ p_x = u \cdot \vec{p_a p_b} + v \cdot \vec{p_a p_c} $ 表示，且須滿足：

• $ u \ge 0 $
• $ v \ge 0 $
• $ (u + v) \le 1 $

繁瑣的證明

解聯立方程，我們要把 向量 壓成 純量。

求出 $u$ 以及 $v$，設定向量：

• $ \vec{V_1} = p_b = \vec{p_a p_b} $
• $ \vec{V_2} = p_c = \vec{p_a p_c} $
• $ \vec{V_3} = \vec{p_a p_x} = u \cdot \vec{V_1} + v \cdot \vec{V_2} $

為了讓方便後續計算，可以將點乘的結果先提出：

• $ D_1 = (\vec{V_1} \cdot \vec{V_1}) $
• $ D_2 = (\vec{V_2} \cdot \vec{V_2}) $
• $ D_3 = (\vec{V_1} \cdot \vec{V_2}) $
• $ D_4 = (\vec{V_3} \cdot \vec{V_1}) $
• $ D_5 = (\vec{V_3} \cdot \vec{V_2}) $

對 $\vec{V_3}$ 點乘 $\vec{V_1}$ 與 $\vec{V_2}$：

• $ D_4 = u (\vec{V_1} \cdot \vec{V_1}) + v (\vec{V_1} \cdot \vec{V_2}) = u D_1 + v D_3 $
• $ D_5 = u (\vec{V_1} \cdot \vec{V_2}) + v (\vec{V_2} \cdot \vec{V_2}) = u D_3 + v D_2 $

解二聯立。

消除 $v$

• $ D_4D_2 = u D_1D_2 + \cancel{v D_3D_2} $
• $ D_5D_3 = u D_3D_3 + \cancel{v D_2D_3} $

得

$
D_4D_2 - D_5D_3 = u [D_1D_2 -D_3D_3]
$

所以

$
u =
\cfrac
{[D_4D_2 -D_5D_3]}
{[D_1D_2 -D_3D_3]}
$

消除 $u$

• $ D_4D_3 = \cancel{u D_1D_3} + v D_3D_3 $
• $ D_5D_1 = \cancel{u D_3D_1} + v D_2D_1 $

得

$
D_4D_3 - D_5D_1 =
v [D_3D_3 - D_2D_1] $

所以

$
v =
\cfrac{[
D_4D_3 -
D_5D_1
]}
{[
D_3D_3 -
D_2D_1
]}
$ 可以上下同乘 -1 得 $
\cfrac{[
D_5D_1 -
D_4D_3
]}
{[
D_2D_1 -
D_3D_3
]}
$（讓 $u$、$v$ 的分數部分一樣可提出）

分數部分

$
InvDenom = \cfrac{1}{[D_2D_1 -D_3D_3 ]}
$

整理後得：

• $ u = [D_2 D_4 - D_3 D_5] * InDenom $
• $ v = [D_1 D_5 - D_3 D_4] * InDenom $

可以寫成以下程式碼：

// k_Vertices 為頂點陣列
bool CheckInsideTriangle(Vector2 p)
{
    Vector2 a = k_Vertices[0].position;
    Vector2 b = k_Vertices[1].position;
    Vector2 c = k_Vertices[2].position;

    var v1 = b - a;
    var v2 = c - a;
    var v3 = p - a;

    var d1 = Vector2.Dot(v1, v1);
    var d2 = Vector2.Dot(v2, v2);
    var d3 = Vector2.Dot(v1, v2);
    var d4 = Vector2.Dot(v1, v3);
    var d5 = Vector2.Dot(v2, v3);

    var invDenom = 1 / (d1 * d2 - d3 * d3);
    var u = (d2 * d4 - d3 * d5) * invDenom;
    var v = (d1 * d5 - d3 * d4) * invDenom;

    return (u >= 0) && (v >= 0) && (u + v <= 1);
}