二维叉积

在几何计算中，二维叉积(2D Cross Product) 是最重要的基础工具。本质上，二维叉积是将三维空间向量叉积退化到 $xy$ 平面上的标量形式。

定义

给定二维平面上的两个向量：

$$\overrightarrow{a}=(x_1,y_1),\overrightarrow{b}=(x_2,y_2)$$

二维叉积计算：

$$\overrightarrow{a}\times \overrightarrow{b}=\left|\begin{array}{cc}{x}_1& x_2\\ y_1& y_2\end{array}\right|=x_1{y}_2-x_2{y}_1$$

三角函数表示法：
由向量点积与模长的定义，叉积也可表示为：

$$\overrightarrow{a}\times \overrightarrow{b}=|\overrightarrow{a}||\overrightarrow{b}|\sin \theta$$

其中 $\theta$ 是从向量 $\overrightarrow{a}$ 逆时针旋转到向量 $\overrightarrow{b}$ 的有向夹角（$\theta \in (-\pi ,\pi ]$）。

二维叉积不满足交换律

• 叉积交换向量后符号取反：$\overrightarrow{a}\times \overrightarrow{b}=-\overrightarrow{b}\times \overrightarrow{a}$

几何意义

1. 转向判定

• $\overrightarrow{a}\times \overrightarrow{b}>0$：$\sin \theta >0$，表示 $\overrightarrow{b}$ 在 $\overrightarrow{a}$ 的逆时针方向（向左转）。
• $\overrightarrow{a}\times \overrightarrow{b}<0$：$\sin \theta <0$，表示 $\overrightarrow{b}$ 在 $\overrightarrow{a}$ 的顺时针方向（向右转）。
• $\overrightarrow{a}\times \overrightarrow{b}=0$：$\sin \theta =0$，表示 $\overrightarrow{a}$ 与 $\overrightarrow{b}$ 共线（方向相同或相反）。

2. 有向面积

• 以 $\overrightarrow{a}$ 和 $\overrightarrow{b}$ 为邻边的平行四边形的面积为 $|\overrightarrow{a}\times \overrightarrow{b}|$。
• 以 $\overrightarrow{a}$ 和 $\overrightarrow{b}$ 为邻边的三角形面积为 $\frac{1}{2}|\overrightarrow{a}\times \overrightarrow{b}|$。
• “有向”特性：如果以逆时针方向排列顶点，计算得到的面积为正；反之为负。

代数性质

1. 反对称性：

$$\overrightarrow{a}\times \overrightarrow{b}=-(\overrightarrow{b}\times \overrightarrow{a})$$

1. 分配律：

$$\overrightarrow{a}\times (\overrightarrow{b}+\overrightarrow{c})=\overrightarrow{a}\times \overrightarrow{b}+\overrightarrow{a}\times \overrightarrow{c}$$

1. 数乘结合律：

$$(k\overrightarrow{a})\times \overrightarrow{b}=\overrightarrow{a}\times (k\overrightarrow{b})=k(\overrightarrow{a}\times \overrightarrow{b})$$

应用

1. 点相对于直线的相对位置
判断点 $P$ 在有向直线 $AB$（从 $A$ 指向 $B$）的哪一侧： 计算 $\overrightarrow{AB}\times \overrightarrow{AP}$：

• $>0$：点 $P$ 在向量 $\overrightarrow{AB}$ 的左侧。
• $<0$：点 $P$ 在向量 $\overrightarrow{AB}$ 的右侧。
• $=0$：点 $P$ 在直线 $AB$ 上。

2. 线段相交判定
线段 $AB$ 与 $CD$ 规范相交（端点不重合）的充要条件是 $C,D$ 分别在 $AB$ 两侧，且 $A,B$ 分别在 $CD$ 两侧：

$$(\overrightarrow{AB}\times \overrightarrow{AC})\cdot (\overrightarrow{AB}\times \overrightarrow{AD})<0\text{且}(\overrightarrow{CD}\times \overrightarrow{CA})\cdot (\overrightarrow{CD}\times \overrightarrow{CB})<0$$

3. 任意简单多边形面积&
按顺序给出多边形顶点 $P_1,P_2,\dots ,P_n$：

$$\text{Area}=\frac{1}{2}|\sum _{i=1}^n(P_i\times P_{i+1})|(P_{n+1}=P_1)$$

4. 凸包构建（Andrew 算法 / Graham 扫描法）
维护凸包边界时，用叉积检查连续三点 $P_{i-1},P_i,P_{i+1}$ 是否保持“向左转”（逆时针）：

• 若 $(\overrightarrow{P_{i-1}{P}_i})\times (\overrightarrow{P_i{P}_{i+1}})\le 0$，说明出现了右转或共线，需要将栈顶点 $P_i$ 弹出。

5. 点在凸多边形内的 $O(\log N)$ 判定 固定起点 $P_1$，利用二分查找快速定位待测点 $Q$ 落在哪个极角扇区 $\mathrm{△}{P}_1{P}_i{P}_{i+1}$，最后用一次叉积判断 $Q$ 是否在边 $P_i{P}_{i+1}$ 的左侧。

6. 旋转卡壳
计算凸包直径或最小外接矩形时，无需直接算点到直线的距离，通过比较三角形的叉积面积，即可在 $O(N)$ 时间内单调维护对踵点对。