MENU

向量积与线段相交问题

March 27, 2018 • 文章

一:什么是向量积?

向量积,也称(向量)叉积,(向量)叉乘,外积,是一种在向量空间中对向量进行的二元运算。常见于物理学力学、电磁学、光学和计算机图形学等理工学科中,是一种很重要的概念。

设向量$\overrightarrow{c}$由两个向量$\overrightarrow{a}$和$\overrightarrow{b}$按如下公式定出:$\overrightarrow{c}$的模$|\overrightarrow{c}|=|\overrightarrow{a}||\overrightarrow{b}|sinθ$,其中$θ$为$\overrightarrow{a}$和$\overrightarrow{b}$间的夹角;$\overrightarrow{c}$的方向垂直于$\overrightarrow{a}$和$\overrightarrow{b}$所决定的平面,指向按右手规则从$\overrightarrow{a}$转向$\overrightarrow{b}$来确定,如下图:

那么,向量$\overrightarrow{c}$叫做向量$\overrightarrow{a}$与$\overrightarrow{b}$的向量积,记作$\overrightarrow{a}×\overrightarrow{b}$。

由上述的定义,我们很容易总结出两条性质:

$$
\begin{align}
\overrightarrow{a}×\overrightarrow{b}&=\overrightarrow{0} \tag{其中$\overrightarrow{a} 平行 \overrightarrow{b}$}\\
\overrightarrow{a}×\overrightarrow{b}&=- \overrightarrow{b}×\overrightarrow{a} \tag{不满足交换律}
\end{align}
$$

下面来推导向量积的坐标表达式,以二维向量为例。设$\overrightarrow{a}=(a_x, a_y),\overrightarrow{b}=(b_x, b_y)$,得:
$$
\begin{align}
\overrightarrow{a}×\overrightarrow{b}&=(a_x\overrightarrow{i}+a_y\overrightarrow{j})×(b_x\overrightarrow{i}+b_y\overrightarrow{j}) \tag{其中$\overrightarrow{i}$和$\overrightarrow{j}分别是$xy$轴上的单位向量$}\\
&=a_x\overrightarrow{i}×(b_x\overrightarrow{i}+b_y\overrightarrow{j})+a_y\overrightarrow{j}×(b_x\overrightarrow{i}+b_y\overrightarrow{j}) \tag{分解}\\
&=a_xb_x(\overrightarrow{i}×\overrightarrow{i})+a_yb_y(\overrightarrow{j}×\overrightarrow{j})+(a_xb_y-a_yb_x)(\overrightarrow{i}×\overrightarrow{j})\tag{合并}\\
&=(a_xb_x+a_yb_y)\overrightarrow{0}+(a_xb_y-a_yb_x)(\overrightarrow{i}×\overrightarrow{j}) \tag{消去平行向量}\\
&=(a_xb_y-a_yb_x)(\overrightarrow{i}×\overrightarrow{j}) \tag{消去0向量}
\end{align}
$$
仔细观察上式,得出:

  1. $a_xb_y-a_yb_x>0$,则$\overrightarrow{b}$在$\overrightarrow{a}$的逆时针方向上(参照$\overrightarrow{i}$和$\overrightarrow{j}$的位置);
  2. $a_xb_y-a_yb_x<0$,则$\overrightarrow{b}$在$\overrightarrow{a}$的顺时针方向上;
  3. $a_xb_y-a_yb_x=0$,则$\overrightarrow{a}$和$\overrightarrow{b}$共线,但是否同向不确定。

二:向量积与计算几何(线段相交)

在计算几何中,向量积也有很大的应用,最经典的就是"线段相交"问题:给定两条线段$AB$和$CD$,其中$A(a_x, a_y),B(b_x, b_y),C(c_x, c_y),D(d_x, d_y)$,判断它们是否相交。

我们只需利用两个实验即可完成判断,快速排斥实验和跨立实验。

先看跨立实验,若两条线段相交,则两线段必然会相互跨立对方。

代码如下:

struct Point
{
    double x, y;
};

/* 求出向量 AB 与向量 AC 的向量积,返回 0 代表共线 */
double cross(Point A, Point B, Point C)
{
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

if (cross(A, B, C) * cross(A, B, D) <= 0 &&
    cross(C, D, A) * cross(C, D, B) <= 0)
    pass test;

但是请考虑一个特殊情况,若两条线段共线呢?此时仅仅通过上面的跨立实验是无法检测的,因此还需要借助快速排斥实验。

所谓的快速排斥实验,就是以线段$AB$,$CD$为对角线作两个矩形,若两个矩形外离,则两条线段必定不相交。

代码如下:

if (min(A.x, B.x) <= max(C.x, D.x) &&
    min(C.x, D.x) <= max(A.x, B.x) &&
    min(A.y, B.y) <= max(C.y, D.y) &&
    min(C.y, D.y) <= max(A.y, B.y))
    pass test;

综合上面的分析,若要断定两条线段相交,则它们必须同时通过快速排斥实验和跨立实验。

全部代码如下:

struct Point
{
    double x, y;
};

/* 求出向量 AB 与向量 AC 的向量积,返回 0 代表共线 */
double cross(Point A, Point B, Point C)
{
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

/* 判断线段 AB 与线段 CD 是否相交,相交返回 true */
bool is_intersect(Point A, Point B, Point C, Point D)
{
    if (min(A.x, B.x) <= max(C.x, D.x) &&
        min(C.x, D.x) <= max(A.x, B.x) &&
        min(A.y, B.y) <= max(C.y, D.y) &&
        min(C.y, D.y) <= max(A.y, B.y) &&
        cross(A, B, C) * cross(A, B, D) <= 0 &&
        cross(C, D, A) * cross(C, D, B) <= 0)
        return true;

    return false;
}

三:参考文献

Archives QR Code Tip
QR Code for this page
Tipping QR Code