1. 矢量叉积

设矢量 $P(x1, y1)$, $Q(x2, y2)$，如果：

1. P x Q > 0 : 则P在Q的顺时针方向;
2. P x Q < 0 : 则P在Q的逆时针方向;
3. P x Q = 0 : 则P与Q共线，但可能同向或也可能反向。

  1. 向量拐向判断

已知线段 $PQ$ 和 $QR$，记 $ans = (R-P) \times (Q-P)$，有如下结论：

1. ans > 0: PQ在Q点向右侧拐后得到QR；
2. ans < 0：PQ在Q点向左侧拐后得到QR；
3. ans = 0: P、Q、R 三点共线。

  1. 判断点在线段上

首先判断点是否在线段所在的直线上，然后判断点的坐标是否在线段的坐标范围内。

ON-SEGMENT(P, Q, R)
    if (R-P) x (Q-P) == 0 and min(px, qx) <= rx <= max(px, qx)
        return True
    else
        return False

  1. 判断线段相交

如果两线段相交，那么每条线段的两个端点都在另一条线段的两侧（不考虑端点在另一条线段上的情形）。由上文中的判断向量拐向的方法，不难得出判断线段相交的方法 如下：

  1. 首先，判断每条线段的端点是否在另一条线段上，如果存在这种情况，则相交，交点为该端点。

  2. 然后，分别判断每条线段的两个端点是否在另外一条线段的两侧，如果是，则相交。

  3. 判断线段和直线相交

线段和直线相交于两条线段类似，只不过要求更加宽松。

  1. 首先判断线段的两个端点是否在直线上，如果是，则相交，该端点为交点。
  2. 然后，判断线段的两个端点是否在直线的两侧（计算时直接从直线上任取一向量即可），如果是，则相交。

该算法可以总结为如下的公式：

如果线段PQ和直线MN相交，那么有：

(P-M)x(N-M) * (N-M)(Q-M) >= 0

  1. 点在多边形内

点与多边形的关系

点与多边形的关系有三种：

  1. 点在多边形内
  2. 点在多边形外
  3. 点在多边形上

此处主要总结如何判断点在多边形内/外。判断点与多边形的关系，有如下两种方法：

射线法

从点出发，取定某一方向（通常取X轴正方向）做射线，如果该射线与多边形相交奇数次，则在多边形内，相交偶数次，则在多边形外。

为判断相交次数，可以判断多边形的每一条边与线段 $(P,\infty)$ ($\infty$ 为一个大正整数）相交的次数。时间复杂度为 $O(N)$。

同时，还需要考虑如下两种特殊情况：

射线可能会与多边形的某一条边重合，对于这种情况，如果取定X轴正方向为射线方向，在判断时直接忽略多边形的水平边即可。

射线还可能与多边形的某一顶点重合，对于这种情况，判断于该定点相连的两条边的另两个端点是否在射线两侧，如果是，则算一次相交，否则忽略。

  1. 判断线段是否在多边形内

首先判断线段的两个端点是否在多边形内，然后判断线段是否与多边形的每条边都不相交。

  1. 求点到线段的最近点

首先，从点出发向线段所在的直线做垂线，如果垂足在线段上，则返回垂足，否则返回距离垂足最近的端点。

  1. 凸包问题

  2. 卷包裹算法(Gift Wrapping)

思路：尽量找在外侧的点。算法时间复杂度：$O(HN)$，其中，$H$为最终在凸包上的点的个数。

  1. Graham Scan算法

思路：先按照斜率排序，再朝着一个方向(顺时针或逆时针)栈扫描。

  1. 快速凸包算法(Quickhull Algorithm)

思路：类似于快速排序，递归分治。

凸包问题的两个应用

  1. 平面最远点对

思路：平面最远点对必然是凸包上的两个顶点。算法：旋转卡壳算法(Rotating Calipers Algorithm)。

  1. 最小矩形覆盖

最小矩阵覆盖指的是用一个尽量小的矩形来覆盖一个平面上所有的点。具体思路：最小矩形的一条边和平面上点集的凸包共线。

因此，找到凸包后，采用旋转卡壳算法找边到点的最小距离即可找到矩形的一条边，从而使得问题得以求解。