判断一个点是否在三角形内部

判断一个点 $P$ 是否在三角形 $ABC$ 内部，我们通常会把它转化为一个等价的问题：$P$ 是不是同时在三条有向边 $AB$、$BC$、$CA$ 的同一侧？

二维向量的叉积刚好能给出这个"在哪一侧"的符号，所以整个判断需要三次叉积。

叉积的几何含义

对二维向量（第三维度分量是 0 的三维向量） $\overrightarrow{u} = (u_x, u_y)$、$\overrightarrow{v} = (v_x, v_y)$ 做叉积，则其叉积的 $z$ 分量为：

$$(\overrightarrow{u} \times \overrightarrow{v})_z = u_x v_y - u_y v_x = \|\overrightarrow{u}\|\,\|\overrightarrow{v}\|\sin\theta$$

这里我们不关心它的绝对值，只关心它的符号。它的符号可以说明 $\overrightarrow{v}$ 在 $\overrightarrow{u}$ 的左侧（正）还是右侧（负）。

通过同侧法进行判定

设三角形按逆时针绕序排列（$A \to B \to C$ 围出的面积为正），对点 $P$ 计算：

$$d_0 = (B - A)\times(P - A),\qquad d_1 = (C - B)\times(P - B),\qquad d_2 = (A - C)\times(P - C)$$

$d_0$、$d_1$、$d_2$ 分别是 $\triangle ABP$、$\triangle BCP$、$\triangle CAP$ 有向面积的两倍。$P$ 在内部时，三个子三角形都保持与 $ABC$ 相同的绕序，三个值同时为正；$P$ 越过某条边时，与该边相对的那个子三角形翻面，对应值变负。所以判据就是：

$$P \in \triangle ABC \iff d_0, d_1, d_2 \text{ 同号}$$

点在某条边上时其对应的叉积为 $0$，落在某个顶点上时该顶点所在的两条边对应的叉积均为 $0$。

可以将上面的逻辑用代码实现大致如下：

// 二维叉积的 z 分量：正数表示 v 在 u 的左侧
float cross2(const Vec2& u, const Vec2& v)
{
    return u.x * v.y - u.y * v.x;
}

bool insideTriangle(const Vec2& a, const Vec2& b, const Vec2& c, const Vec2& p)
{
    float d0 = cross2(b - a, p - a);   // 边 AB
    float d1 = cross2(c - b, p - b);   // 边 BC
    float d2 = cross2(a - c, p - c);   // 边 CA
    bool all_non_negative = d0 >= 0.0f && d1 >= 0.0f && d2 >= 0.0f;
    bool all_non_positive = d0 <= 0.0f && d1 <= 0.0f && d2 <= 0.0f;
    return all_non_negative || all_non_positive;
}

这里不写死"三个都大于 0"，而是一并接受"三个都小于 0"：绕序为顺时针（包括屏幕坐标 $y$ 轴向下这种常见情形）时，所有符号整体翻转，判据依然成立。

三维的情形

三角形在三维空间中一定共面，但只要对法线 $\overrightarrow{n} = (B-A)\times(C-A)$ 做点乘，同一套叉积判据就能用：

$$d_0 = \overrightarrow{n}\cdot\big((B-P)\times(C-P)\big)$$

因为三维叉积的结果平行于 $\overrightarrow{n}$，点乘实质上就是获得此向量在法线方向的投影，把它再变成标量。

• 这个做法等价于先沿法线把 $P$ 投影到三角形所在平面，再做二维判断，$P$ 离平面多远都不影响结果
• 若还需要排除"不在平面上"的点，只需要另外检查 $\overrightarrow{n}\cdot(P-A) \approx 0$ 即可。

一种更省事的做法是把三角形投影到 $|\overrightarrow{n}|$ 最大的那个坐标平面上（丢掉法线最占优的那个分量），退化成二维问题；投影后的绕序符号可能翻转，仍然用"同号"进行判定。

边界与浮点

• 边和顶点算不算内部要事先约定。光栅化里的常用规则是 top-left rule：规定上边和左边属于内部、其余边不属于，这样共享一条边的两个三角形不会都通过测试，也不会都失败，留下空隙。
• 绕序与坐标系：屏幕空间 $y$ 轴向下时，逆时针在数学意义上变成了顺时针，符号全部反转。用"三个同号"而不是"三个为正"，能同时兼容两种绕序。
• 退化三角形：三点共线时 $S = 0$，重心坐标要除以 0。光栅化前就该把面积为零的图元剔除（见 图元）。
• 浮点误差：直接和 $0$ 比较，会让本该落在边上的点随机地判进或判出。要么留一个 epsilon，要么在规则网格上用整数/定点运算做精确判定；epsilon 也不能贪大，狭长三角形会被它整片吞掉。