用向量叉乘求直線交點

• 2021 年 10 月 10 日
• 筆記
• 演算法, 計算幾何

求解方法

兩個技巧：

• 用向量來表示點，則可以用向量加法來表示點的平移。
• 用點和向量來表示直線，這樣可以處理斜率無窮大的情況。

如圖所示，有兩條直線交於點 \(I\)。我們用點 \(p_1\) 和向量 \(\vec v_1\) 來表示直線 1，用點 \(p_2\) 和向量 \(\vec v_2\) 來表示直線 2。

把點看成向量，則有 \(\mathbf I=\mathbf p_1+t\mathbf v_1\)（用向量加法表示點的平移），現在我們的任務就是求出標量 \(t\)。所謂用向量叉乘來求直線交點，就是利用 \(\overrightarrow{Ip_2}\times\vec v_2=\vec 0\)（兩向量平行）這個式子求出 \(t\)。

在開始推導之前，先複習一下向量叉乘的幾條運算規律：

• 加法的左分配律：\(\mathbf{a} \times (\mathbf{b} + \mathbf{c}) = \mathbf{a} \times \mathbf{b} + \mathbf{a} \times \mathbf{c}\)
• 加法的右分配律：\((\mathbf{a} + \mathbf{b}) \times \mathbf{c} = \mathbf{a} \times \mathbf{c} + \mathbf{b} \times \mathbf{c}\)
• 標量乘法：\((\lambda\mathbf{a})\times\mathbf{b} = \lambda(\mathbf{a}\times\mathbf{b}) = \mathbf{a}\times(\lambda\mathbf{b})\)

下面我們來求解標量 \(t\)，推導過程如下：

好了，現在我們求出了標量 \(t\)，接下來用 \(\mathbf I=\mathbf p_1+t\mathbf v_1\) 這個式子計算出交點 \(I\) 的坐標即可。

順便一提，這種「將點和向量統一表示」的思想在電腦圖形學中有很重要的應用，即齊次坐標。

程式碼

首先我們需要寫一個向量類。

注意，程式碼中的 cross 函數求的是向量積的模，所以返回的是個標量。

//二維向量
struct Vec
{
    double x, y;
    Vec() = default;
    Vec(double x, double y) : x(x), y(y) {}
    double len2() const { return x * x + y * y; }
    double len() const { return sqrt(len2()); }
    Vec operator+(const Vec &b) const { return Vec(x + b.x, y + b.y); }
    Vec operator-(const Vec &b) const { return Vec(x - b.x, y - b.y); }
    Vec operator*(double t) const { return Vec(x * t, y * t); }
    Vec operator/(double t) const { return Vec(x / t, y / t); }
    Vec operator-() const { return Vec(-x, -y); }
};

//向量積的模
double cross(const Vec &a, const Vec &b) { return a.x * b.y - b.x * a.y; }

求解兩直線交點的程式碼。程式碼相當簡潔，而且可以應對包括直線斜率無窮大在內的所有情況。

//求解兩直線交點
//p1、v1 用於表示直線 1，p2、v2 用於表示直線 2
Vec intersection(const Vec &p1, const Vec &v1, const Vec &p2, const Vec &v2)
{
    double t = cross((p2 - p1), v2) / cross(v1, v2);
    return p1 + v1 * t;
}