线段的性质

使用叉积 (cross product) 来计算线段的性质
$$p_1 \times p_2 = \det\left[\begin{matrix}
x_1 & x_2 \newline
y_1 & y_2
\end{matrix}\right] = x_1y_2-x_2y_1 = -p_2 \times p_1$$
正负号满足右手定则，绝对值是两个向量组成的平行四边形的面积。
如果叉积为 $0$，说明两个向量共线性，即方向相同或相反。

同起点有向线段的方向

两个有向线段 $\overrightarrow{p_0p_1}$ 和 $\overrightarrow{p_0p_2}$。
如果 $(p_1 - p_0) \times (p_2 - p_0)$ 为 正，则 $\overrightarrow{p_0p_1}$ 需要 逆时针 旋转，才能转到 $\overrightarrow{p_0p_2}$。
如果为 负，则 $\overrightarrow{p_0p_1}$ 需要 顺时针 旋转，才能转到 $\overrightarrow{p_0p_2}$

double cross_product(const Point& p0, const Point& p1, const Point& p3) {
    return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}

连续线段的是左转还是右转

两个有向线段 $\overrightarrow{p_0p_1}$ 和 $\overrightarrow{p_1p_2}$ 在 $p_1$ 处的转向，即 $\angle{p_0p_1p_2}$ 的转向。
可以通过计算 $\overrightarrow{p_0p_1}$ 和 $\overrightarrow{p_0p_2}$ 的转向来判断

如果 $(p_1 - p_0) \times (p_2 - p_0)$ 为 正，则在 $p_1$ 处 左转。如果为 负，在 $p_1$ 处则 右转。

两条线段相交

两条线段相交 $\iff$ 下面两个条件至少有一个成立:
1. 每条线段都跨越了另一条线段所在的直线
2. 一条线段的某个端点落在另一条线段上

判断线段 $\overrightarrow{p_1p_2}$ 和 $\overrightarrow{p_3p_4}$ 相交, 调用 segments_intersect(p1, p2, p3, p4)

bool on_segment(const Point& p1, const Point& p2, const Point& p3) {
    // 判断 点 p3 是否在 线段 p1p2 上，应该满足两个条件：
    //     1. (p2 - p1) \times (p3 - p1) 为 0
    //     2. p3 在 p1p2 为对角线的矩形内
    // 在这里，被调用时，`segments_intersect` 的判断条件已经保证了第一条满足条件，只需要判断第二条

    // min(x1, x2) < = x3 <= max(x1, x2) && min(y1, y2) < = y3 <= max(y1, y2)
    return (p1.x - p3.x) * (p2.x - p3.x) <= 0 &&  (p1.y - p3.y) * (p2.y - p3.y) <= 0;
}

bool segments_intersect(const Point& p1, const Point& p2, const Point& p3, const Point& p4) {
    const double d1 = cross_product(p3, p4, p1);
    const double d2 = cross_product(p3, p4, p2);
    const double d3 = cross_product(p1, p2, p3);
    const double d4 = cross_product(p1, p2, p4);

    if (d1 * d2 < 0 && d3 * d4 < 0) {
        return true;
    }

    if (std::abs(d1) < eps) {
        return on_segment(p3, p4, p1);
    }

    if (std::abs(d2) < eps) {
        return on_segment(p3, p4, p2);
    }

    if (std::abs(d3) < eps) {
        return on_segment(p1, p2, p3);
    }

    if (std::abs(d4) < eps) {
        return on_segment(p1, p2, p4);
    }

    return false;
}

线段集合中是否存在两条线段相交

$O(n\log n)$

Shamos–Hoey algorithm
对 $2n$ 个线段端点的排序，通常按照 $(x, e, y)$ 来对端点按照字典序排序。
其中 $x$ 和 $y$ 为端点的坐标，$e = 0$ 表示左端点，$e=1$表示右端点。
对垂直线段也适用：上述排序会将底部端点当做左端点，顶部端点当做右端点 （参见习题 33.2-9）

Bentley–Ottmann algorithm 对其做了改进？(wikipedia )

凸包

$n$ 为总点数, $h$ 为 凸包上的点的数目

Graham Scan

$O(n\log n)$

Jarvis’s march

$O(nh)$

incremental method

$O(n\log n)$

we first sort the points from left to right, yielding a sequence $\langle p_1, p_2,\cdots,p_n\rangle$. At the ith stage, we update the convex hull of the $i - 1$ leftmost points, $CH\left({ p_1, p_2,\cdots, p_{i-1}}\right)$, according to the ith point from the left, thus forming $CH\left({ p_1, p_2,\cdots, p_{i}}\right)$. Exercise 33.3-6 asks you how to implement this method to take a total of $O(n\log n)$ time.

divide-and-conquer method

$O(n\log n)$

we divide the set of n points in $\Theta(n)$time into two subsets, one containing the leftmost $\lceil \frac{n}{2}\rceil$ points and one containing the rightmost $\lfloor \frac{n}{2}\rfloor$ points, recursively compute the convex hulls of the subsets, and then, by means of a clever method, combine the hulls in $$O(n)$ time. The running time is described by the familiar recurrence $T(n) = 2T(\frac{n}{2} + O(n)$, and so the divide-and-conquer method runs in $O(n\log n)$ time.

prune-and-search method

$O(n\log h)$

With this method, we find the upper portion (or “upper chain”) of the convex hull by repeatedly throwing out a constant fraction of the remaining points until only the upper chain of the convex hull remains. We then do the same for the lower chain. This method is asymptotically the fastest