矢量的概念：
如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段 (directed
segment)。如果有向线段 p1p2 的起点 p1 在坐标原点，我们可以把它称为矢量(vector)p2。
矢量加减法：
设二维矢量 P = ( x1, y1 )，Q = ( x2 , y2 )，则矢量加法定义为： P + Q = ( x1 + x2 , y1 +
y2 )，同样的，矢量减法定义为： P - Q = ( x1 - x2 , y1 - y2 )。显然有性质 P + Q = Q + P，P
- Q = - ( Q - P )。
矢量叉积：
计算矢量叉积是与直线和线段相关算法的核心部分。设矢量 P = ( x1, y1 )，Q = ( x2, y2
)，则矢量叉积定义为由(0,0)、p1、p2 和 p1+p2 所组成的平行四边形的带符号的面积，即：
P × Q = x1*y2 - x2*y1，其结果是一个标量。显然有性质 P × Q = - ( Q × P ) 和 P × ( - Q ) = - (
P × Q )。一般在不加说明的情况下，本文下述算法中所有的点都看作矢量，两点的加减法
就是矢量相加减，而点的乘法则看作矢量叉积。
叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系：
若 P × Q > 0 , 则 P 在 Q 的顺时针方向。
若 P × Q < 0 , 则 P 在 Q 的逆时针方向。
若 P × Q = 0 , 则 P 与 Q 共线，但可能同向也可能反向。
折线段的拐向判断：
折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段 p0p1
和 p1p2，通过计算(p2 - p0) × (p1 - p0)的符号便可以确定折线段的拐向：
若(p2 - p0) × (p1 - p0) > 0,则 p0p1 在 p1 点拐向右侧后得到 p1p2。
若(p2 - p0) × (p1 - p0) < 0,则 p0p1 在 p1 点拐向左侧后得到 p1p2。
若(p2 - p0) × (p1 - p0) = 0,则 p0、p1、p2 三点共线。
具体情况可参照下图：
设点为 Q，线段为 P1P2 ，判断点 Q 在该线段上的依据是：( Q - P1 ) × ( P2 - P1 ) = 0 且
Q 在以 P1，P2 为对角顶点的矩形内。前者保证 Q 点在直线 P1P2 上，后者是保证 Q 点不在
线段 P1P2 的延长线或反向延长线上，对于这一步骤的判断可以用以下过程实现：
- 1
- 2
- 3
- 4
前往页