凸包问题

起因, Leetcode里的587.安装栅栏, 第二次遇到凸包问题了, 不会就学, 老碰见很烦

基本概念

• 凸多边形: 所有内角大小都在 $[0, \pi]$ 范围内的多边形
• 凸包(Convex Hull): 在平面上能包含所有给定点的最小凸多边形叫做凸包
• 向量积判断点在直线哪一侧: 右手螺旋定则, 直线方向向量与直线上任意一点与判断点向量的积, 为正则在左侧, 为零则在线上, 为负则在右侧(向量积的结果方向符合右手螺旋定则)

Andrew Algorithm

将集合内的所有点按照 x 坐标以及 y 坐标升序排序, 我们可以认为排序后的首尾两点, 从左下至右上将所求的凸包分成了上凸包与下凸包两部分

我们按照排序顺序逐个遍历点, 可以想得到的是, 我们遍历点的方向是右手螺旋的, 因此, 如果遍历到的点, 相较于前两个点左旋时, 我们应当弹出上一点, 压入该点, 因此用一个栈来存储点比较合适, 同时我们可以用前文通过向量积的知识来判断遍历点是否左旋.

同理, 我们可以用相同的方式遍历获得上凸包, 应当注意的是, 遍历下凸包时, 我们根据栈中点个数大于二来决定是否需要判断新增点右旋, 而遍历上凸包时, 我们需要保证在下凸包的点不被遍历(除开起点), 且下凸包的点不应该被弹出, 因此需要记录是否遍历过

#include <vector>
#include <iostream>
using namespace std;

// 判断是否右旋
bool isDextral(pair<int, int> &a, pair<int, int> &b, pair<int, int> &c)
{
    pair<int, int> ba, ac;
    ba = {a.first - b.first, a.second - b.second};
    ac = {c.first - a.first, c.second - a.second};
    return ba.first * ac.second - b2a.second * ac.first < 0;
}
vector<pair<int, int>> convexHull(vector<pair<int, int>> &trees)
{
    int sz = trees.size();
    // 点数小于三个自成凸包
    if (sz < 4)
        return trees;
    sort(trees.begin(), trees.end(), [&](const pair<int, int> &a, const pair<int, int> &b)
         { return a.first == b.first ? a.second < b.second : a.first < b.first; });
    vector<int> stk;
    vector<bool> visit(sz, false);
    // 存入左下点, 且visit = false使得遍历上凸壳时能够遍历起点
    stk.push_back(0);
    // 下凸壳
    for (int idx = 1; idx < sz; ++idx)
    {
        auto p = trees[idx];
        while (stk.size() >= 2)
        {
            // 右旋, 则弹出栈顶点
            if (isDextral(trees[stk.back()], trees[stk[stk.size() - 2]], p))
            {
                visit[stk.back()] = false;
                stk.pop_back();
            }
            // 左旋, 则加入栈
            else
                break;
        }
        stk.push_back(idx);
        visit[idx] = true;
    }
    int lowerConvexHullSz = stk.size();
    // 遍历上凸壳
    for (int idx = sz - 1; idx >= 0; --idx)
    {
        if (visit[idx])
            continue;
        auto p = trees[idx];
        // 栈内点数至少大于下凸壳点数, 且不弹出下凸壳点
        while (stk.size() > lowerConvexHullSz)
        {
            if (isDextral(trees[stk.back()], trees[stk[stk.size() - 2]], p))
            {
                visit[stk.back()] = false;
                stk.pop_back();
            }
            else
                break;
        }
        stk.push_back(idx);
        visit[idx] = true;
    }
    vector<pair<int, int>> res;
    // 起点重复
    for (int idx = 1; idx < stk.size(); ++idx)
        res.push_back(trees[stk[idx]]);
    return res;
}

int main()
{
    int m;
    cin >> m;
    vector<pair<int, int>> points(m);
    for (int idx = 0; idx < m; ++idx)
        cin >> points[idx].first >> points[idx].second;
    vector<pair<int, int>> res = convexHull(points);
    for (auto p : res)
        cout << p.first << "," << p.second << endl;
    return 0;
}

排序时间复杂度 $O(n\log(n))$, 每个点在遍历上下凸壳时只遍历一次, 时间 $O(2n)$, 总时间复杂度 $O(n\log(n))$, 空间复杂度 $O(n)$

Jarvis Algorithm

其实知道 Andrew 算法就行了, 因为那个是优化版本, 这个 Jarvis 算法等于是 Andrew 的前辈了, 时间复杂度 $O(n^2)$

大体思路与 Andrew 类似, 从最左点开始加入凸包, 找到下一个点使得其余剩余点都在该线的左侧, 然后加入凸包, 不断重复直至没有这样一个点为止

Graham Algorithm

极坐标下的 Andrew Algorithm