判斷點是否在三角形內：向量同向法與面積法完整解析（含 2D/3D、整數/浮點優化）

問題定義

給定三角形 A, B, C 與點 P，判斷 P 是否在三角形內（含邊界）。最常用兩種等價方法：

• 向量同向法：AB × AP、AP × AC、PB × PC 與 AB × AC 同向（平行且同號）
• 面積法：Area(ABC) = Area(ABP) + Area(APC) + Area(PBC)

數學等價性證明

向量叉積模長即為平行四邊形面積，三角形面積為其一半：

Area(ABC) = |AB × AC| / 2

利用恆等式 PB × PC = (AB - AP) × (AC - AP) = AB × AC - AB × AP - AP × AC

可得面積關係：|AB × AC| = |AB × AP| + |AP × AC| + |AB × AC - AB × AP - AP × AC|

任意向量 a, b, c 滿足 |a + b + c| = |a| + |b| + |c| ⟺ a, b, c 同向，故兩法本質等價。

二維座標系統實作

向量模板

template <typename T> class Vec2 {
    T x, y;
public:
    typedef T value_type;
    Vec2(T xx = 0, T yy = 0) : x(xx), y(yy) {}
    T cross(const Vec2& v) const { return x * v.y - y * v.x; }  // 叉積
    Vec2 operator-(const Vec2& v) const { return Vec2(x - v.x, y - v.y); }
};

浮點座標版（面積法，含誤差容忍）

typedef Vec2<double> Vd2;
bool is_in_triangle(const Vd2& a, const Vd2& b, const Vd2& c, const Vd2& p) {
    Vd2 ab(b - a), ac(c - a), ap(p - a);
    double abc = ab.cross(ac);
    double abp = ab.cross(ap);
    double apc = ap.cross(ac);
    double pbc = abc - abp - apc;  // 等於 pb.cross(pc)
    double delta = fabs(abc) - fabs(abp) - fabs(apc) - fabs(pbc);
    return fabs(delta) < DBL_EPSILON;
}

整數座標版（避免浮點誤差）

typedef Vec2<int> Vi2;
bool is_in_triangle_int(const Vi2& a, const Vi2& b, const Vi2& c, const Vi2& p) {
    Vi2 ab(b - a), ac(c - a), ap(p - a);
    int abc = ab.cross(ac);
    int abp = ab.cross(ap);
    int apc = ap.cross(ac);
    int pbc = abc - abp - apc;

    // 方法 1：面積法（4 次絕對值，編譯器常優化為位運算無分支）
    return abs(abc) == abs(abp) + abs(apc) + abs(pbc);

    // 方法 2：向量同向法（1 次分支 + 3 次比較）
    if (abc < 0) { abp = -abp; apc = -apc; pbc = -pbc; }
    return (abp >= 0) && (apc >= 0) && (pbc >= 0);
}

整數版深度優化（無分支、位運算技巧）

絕對值位運算公式

設 y = (x >> (sizeof(int)*CHAR_BIT - 1))（算術右移，非負為 0，負為 -1）

abs(x) = (x ^ y) - y 或 (x + y) ^ y

多條件同向判斷合併

(a >= 0) && (b >= 0) && (c >= 0) ⟺ (a | b | c) >= 0

最終優化版

inline int chg_sign(int x, int sign) { return (x + sign) ^ sign; }  // sign 為 0 或 -1

bool is_in_triangle_opt(const Vi2& a, const Vi2& b, const Vi2& c, const Vi2& p) {
    Vi2 ab(b - a), ac(c - a), ap(p - a);
    int abc = ab.cross(ac);
    int abp = ab.cross(ap);
    int apc = ap.cross(ac);
    int pbc = abc - abp - apc;

    const int sign = (abc >= 0) - 1;  // abc ≥ 0 → 0；abc < 0 → -1
    return (chg_sign(abp, sign) | chg_sign(apc, sign) | chg_sign(pbc, sign)) >= 0;
}

此版本無分支、僅整數運算、指令數極少，適合高效能幾何運算庫。

三維擴展提示

三維情況下，需先判斷點是否在三角形平面上，再投影至最大分量座標平面（XY/YZ/ZX）套用二維演算法，或直接用重心座標法。乘法次數可從朴素 30 次降至 13 次（已知共面時 8 次）。