矢量的叉积

在看到有人讨论如何判断线段相交的问题的时候，发现自己有矢量这块基础知识的缺失，因此写篇笔记填个坑，以便记忆。

矢量的基本知识

  • 矢量的概念：如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed segment)。如果有向线段$p_1p_2$的起点$p_1$在坐标原点，则将其称为矢量(vector)$p_2$。
  • 矢量加减法：设二维矢量$P=(x_1,y_1),Q=(x_2,y_2)$
    ​ 矢量加法定义为：$P+Q=(x_1+x_2,y_1+y_2)$
    ​ 矢量减法定义为： $P-Q=(x_1-x_2,y_1-y_2)$
    ​ 显然有性质 $P+Q=Q+P,P-Q=-(Q-P)$
  • 矢量的叉积：计算矢量叉积是与直线和线段相关算法的核心部分。设矢量$P=(x_1,y_1),Q=(x_2,y_2)$，则矢量叉积定义为由$(0,0)$、$P_1$、$P_2$和$P_1+P_2$所组成的平行四边形的带符号的面积，即：$P × Q = x_1y_2 - x_2y_1$，其结果是一个标量。显然有性质 $P × Q = - ( Q × P ) $和$ P × ( - Q ) = - ( P × Q )$。
    叉积的另一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系：
    　　若 $P × Q > 0$ , 则P在Q的顺时针方向。
    　　若 $P × Q < 0$ , 则P在Q的逆时针方向。
    　　若 $P × Q = 0$ , 则P与Q共线，但可能同向也可能反向。
  • 折线段的拐向判断：折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段$p_0p_1$和$p_1p_2$，通过计算$(p_2 - p_0) × (p_1 - p_0)$的符号便可以确定折线段的拐向：
    若$(p_2 - p_0) × (p_1 - p_0) > 0$,则$p_0p_1$在$p_1$点拐向右侧后得到$p_1p_2$。
    　　若$(p_2 - p_0) × (p_1 - p_0) < 0$,则p_0p_1在p_1点拐向左侧后得到p_1p_2。
    　　若(p_2 - p_0) × (p_0 - p_0) = 0,则$p_0$、$p_1$、$p_2$三点共线。
    这一条判断也可用来判断点在线段或直线的哪一测。

判断两条直线是否相交

　　第一个可能会想到的办法，就是判断斜率，这个在中学时代就学过了，不过斜率需要考虑垂直的特殊情况，比较麻烦。计算两个向量的叉积或许是一个更好的办法，如果两个向量叉乘为0，则是平行或者重合的，否则两直线相交。这里贴出来一个便于理解原理的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <opencv2\highgui\highgui.hpp>  
#include <opencv2\opencv.hpp>  
using namespace std;  
using namespace cv;  
  
 struct point  
{  
    int x;  
    int y;  
};  
struct v  
{  
    point start;  
    point end;  
};  
int crossProduct(v* v1, v* v2)  
{  
    v vt1, vt2;  
    int result = 0;  
  
    vt1.start.x = v1->start.x;  
    vt1.start.y = v1->start.y;  
    vt1.end.x = v1->end.x - v1->start.x;  
    vt1.end.y = v1->end.y - v1->start.y;  
      
    vt2.start.x = v2->start.x;  
    vt2.start.y = v2->start.y;  
    vt2.end.x = v2->end.x - v2->start.x;  
    vt2.end.y = v2->end.y - v2->start.y;  
  
    result = vt1.end.x * vt2.end.y - vt2.end.x * vt1.end.y;  
    return result;  
}  
  
int main()  
{  
    Point p1end(1, 2);  
    Point p1start(0, 0);  
    Point p2end(2, 1);  
    Point p2start(0, 0);  
    v pt1, pt2;  
    pt1.end.x = p1end.x;  
    pt1.end.y = p1end.y;  
    pt1.start.x = p1start.x;  
    pt1.start.y = p1start.y;  
    pt2.end.x = p2end.x;  
    pt2.end.y = p2end.y;  
    pt2.start.x = p2start.x;  
    pt2.start.y = p2start.y;  
    cout << "CrossProduct: " << crossProduct(&pt1, &pt2) << endl;  
    system("pause");  
    return 0;  
}

输出结果为: CrossProduct: -3
矢量的叉积
如图所示，向量$P_1$，$P_2$的叉乘就是图中平行四边形的面积=3，负号就表示向量$P_1$在$P_2$的逆时针方向。

判断两线段相交

经典方法，就是跨立实验，即如果一条线段跨过另一条线段，则线段的两个端点分别在另一条线段的两侧。但是，还需要检测边界情况，即两条线段中可能某条线段的某个端点正好落在另一条线段上。
程序模拟如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
int direction(point* pi, point* pj, point* pk){  
point p1, p2;  
  
p1.x = pk->x - pi->x;  
p1.y = pk->y - pi->y;  
  
p2.x = pj->x - pi->x;  
p2.y = pj->y - pi->y;  
  
return crossProduct(&p1, &p2);  
}  
int onSegment(point* pi, point* pj, point* pk){  
int minx, miny, maxx, maxy;  
if (pi->x > pj->x){  
    minx = pj->x;  
    mxx = pi->x;   
}  
else{  
    minx = pi->x;  
    maxx = pj->x;  
}  
  
if (pi->y > pj->y){  
    miny = pj->y;  
    maxy = pi->y;   
}  
else{  
    miny = pi->y;  
    maxy = pj->y;  
}  
  
if (minx <= pk->x && pk->x <= maxx && miny <= pk->y && pk->y <= maxy)  
    return 1;  
else  
    return 0;  
}  
int segmentIntersect(point* p1, point* p2, point* p3, point* p4)
{  
    int d1 = direction(p3, p4, p1);  
    int d2 = direction(p3, p4, p2);  
    int d3 = direction(p1, p2, p3);  
    int d4 = direction(p1, p2, p4);  
    if (d1 * d2 < 0 && d3 * d4 < 0)  
        return 1;  
    else if (!d1 && onSegment(p3, p4, p1))  
        return 1;  
    else if (!d2 && onSegment(p3, p4, p2))  
        return 1;  
    else if (!d3 && onSegment(p1, p2, p3))  
        return 1;  
    else if (!d4 && onSegment(p1, p2, p4))  
        return 1;  
    else  
        return 0;  
}

实际上，如果想改进上述算法，还可以在跨立试验前加一步，就是先做快速排斥试验。那就是，先分别判断以两条线段为对角线的矩形是否相交，如果不相交，则两个线段肯定不相交。

计算交点

设一条线段为$L_0=P_1P_2$, 另一条线段或直线为$L_1=Q_1Q_2$, 要计算的就是$L_0$和$L_1$的交点。
1、首先判断$L_0$和$L_1$是否相交(方法已在前文讨论过), 如果不相交则没有交点, 否则说明$L_0$和$L_1$一定有交点, 下面就将$L_0$和$L_1$都看作直线来考虑.

2、如果$P_1$和$P_2$横坐标相同, 即$L_0$平行于Y轴

  • 若$L_1$也平行于Y轴
    • 若$P_1$的纵坐标和$Q_1$的纵坐标相同, 说明$L_0$和$L_1$共线, 假如$L_1$是直线的话他们有无穷的交点, 假如$L_1$是线段的话可用”计算两条共线线段的交点”的算法求他们的交点(该方法在前文已讨论过);
    • 否则说明$L_0$和$L_1$平行, 他们没有交点;
  • 若$L_1$不平行于Y轴, 则交点横坐标为$P_1$的横坐标, 代入到$L_1$的直线方程中可以计算出交点纵坐标;

3、如果$P_1$和$P_2$横坐标不同, 但是$Q_1$和$Q_2$横坐标相同, 即$L_1$平行于Y轴, 则交点横坐标为$Q_1$的横坐标, 代入到$L_0$的直线方程中可以计算出交点纵坐标;

4、如果$P_1$和$P_2$纵坐标相同, 即$L_0$平行于X轴

  • 若$L_1$也平行于X轴,
    • 若$P_1$的横坐标和$Q_1$的横坐标相同, 说明$L_0$和$L_1$共线, 假如$L_1$是直线的话他们有无穷的交点, 假如$L_1$是线段的话可用”计算两条共线线段的交点”的算法求他们的交点(该方法在前文已讨论过);
    • 否则说明$L_0$和$L_1$平行, 他们没有交点;
  • 若$L_1$不平行于X轴, 则交点纵坐标为$P_1$的纵坐标, 代入到$L_1$的直线方程中可以计算出交点横坐标;

5、如果$P_1$和$P_2$纵坐标不同, 但是$Q_1$和$Q_2$纵坐标相同, 即$L_1$平行于X轴, 则交点纵坐标为$Q_1$的纵坐标, 代入到$L_0$的直线方程中可以计算出交点横坐标;

6、剩下的情况就是$L_1$和$L_0$的斜率均存在且不为0的情况

  • 计算出$L_0$的斜率K0, $L_1$的斜率$k_1$;
  • 如果$k_1$ = $k_2$
    • 如果$Q_1$在$L_0$上, 则说明$L_0$和$L_1$共线, 假如$L_1$是直线的话有无穷交点, 假如$L_1$是线段的话可用”计算两条共线线段的交点”的算法求他们的交点(该方法在前文已讨论过);
    • 如果$Q_1$不在$L_0$上, 则说明$L_0$和$L_1$平行, 他们没有交点.
  • 联立两直线的方程组可以解出交点来

这个算法并不复杂, 但是要分情况讨论清楚, 尤其是当两条线段共线的情况需要单独考虑, 所以在前文将求两条共线线段的算法单独写出来. 另外, 一开始就先利用矢量叉乘判断线段与线段(或直线)是否相交, 如果结果是相交, 那么在后面就可以将线段全部看作直线来考虑. 需要注意的是, 我们可以将直线或线段方程改写为$$ax+by+c=0$$这样一来上述过程的部分步骤可以合并, 缩短了代码长度, 但是由于先要求出参数, 这种算法将花费更多的时间.