计算几何

如果把一条线段的端点作出次序之分，则可将这种线段看作有向线段。如果有向线段${\displaystyle P_{1}P_{2}}$的起点${\displaystyle P_{1}}$在坐标原点，则把它称为矢量${\displaystyle {\boldsymbol {P}}_{2}}$。这样，点${\displaystyle P(x,y)}$ 可以看作起点为原点${\displaystyle O(0,0)}$的二维矢量。相应地，三维空间坐标系下的坐标也可以作类似理解为三维矢量。

设二维矢量${\displaystyle {\boldsymbol {P}}=(x_{1},y_{1}),{\boldsymbol {Q}}=(x_{2},y_{2})}$，则矢量的加法定义为${\displaystyle {\boldsymbol {P}}+{\boldsymbol {Q}}=(x_{1}+x_{2},y_{1}+y_{2})}$，矢量的减法定义为${\displaystyle {\boldsymbol {P}}-{\boldsymbol {Q}}=(x_{1}-x_{2},y_{1}-y_{2})}$。矢量的加减法有以下性质：${\displaystyle {\boldsymbol {P}}+{\boldsymbol {Q}}={\boldsymbol {Q}}+{\boldsymbol {P}},{\boldsymbol {P}}-{\boldsymbol {Q}}=-({\boldsymbol {Q}}-{\boldsymbol {P}})}$。因为点可视为坐标原点至该点的矢量，所以点的加减法就是矢量的加减法。

矢量的叉积，也称矢量的叉乘。矢量${\displaystyle {\boldsymbol {P}}}$与${\displaystyle {\boldsymbol {Q}}}$的叉乘记作${\displaystyle {\boldsymbol {P}}\times {\boldsymbol {Q}}}$。定义${\displaystyle {\boldsymbol {P}}\times {\boldsymbol {Q}}=x_{1}y_{2}-x_{2}y_{1}}$，其结果是一个标量。几何意义为由原点、点${\displaystyle P}$、点${\displaystyle Q}$、点${\displaystyle P+Q}$四点共同组成的平行四边形的面积（带正负号）。计算矢量叉积是直线和线段相关算法的核心。矢量的叉积有以下性质：${\displaystyle {\boldsymbol {P}}\times {\boldsymbol {Q}}=-({\boldsymbol {Q}}\times {\boldsymbol {P}}),{\boldsymbol {P}}\times (-{\boldsymbol {Q}})=-({\boldsymbol {P}}\times {\boldsymbol {Q}})}$。

叉乘的一个非常重要的性质是，可以通过它的正负号判断两矢量之间的顺逆时针关系：

• 若${\displaystyle {\boldsymbol {P}}\times {\boldsymbol {Q}}>0}$，则${\displaystyle {\boldsymbol {P}}}$在${\displaystyle {\boldsymbol {Q}}}$的顺时针方向；
• 若${\displaystyle {\boldsymbol {P}}\times {\boldsymbol {Q}}<0}$，则${\displaystyle {\boldsymbol {P}}}$在${\displaystyle {\boldsymbol {Q}}}$的逆时针方向；
• 若${\displaystyle {\boldsymbol {P}}\times {\boldsymbol {Q}}=0}$，则${\displaystyle {\boldsymbol {P}}}$和${\displaystyle {\boldsymbol {Q}}}$共线，可能同向也可能反向。

折线段的拐向判断方法可以直接由矢量叉积的性质推出。 对于有公共端点的线段${\displaystyle AP}$和${\displaystyle PB}$，通过计算${\displaystyle \nabla =(B-P)\times (P-A)}$的符号，就可以确定折线的拐向：

• 若${\displaystyle \nabla >0}$，则${\displaystyle AP}$在${\displaystyle P}$点拐向右侧得到${\displaystyle PB}$；
• 若${\displaystyle \nabla <0}$，则${\displaystyle AP}$在${\displaystyle P}$点拐向左侧得到${\displaystyle PB}$；
• 若${\displaystyle \nabla =0}$，则${\displaystyle A}$、${\displaystyle P}$、${\displaystyle B}$三点共线。