这篇文章上次修改于 372 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

算法学习笔记1——极角排序

基础含义

对于一个平面的多个点，选择一个点作为极点O，再从O出去一条射线定为极轴OX（一般把X轴正半轴作为极轴），对于每个平面上的点我们有一种新的表示方法：极坐标（γ、θ），γ为线段OP的长度，θ为OP与OX所夹的角。

极角排序顾名思义就是根据极坐标的角度值进行排序，对于一个中心点，类似于雷达一样，按照雷达扫描的顺序进行排序的点。

平面叉乘：对于向量u=(u1，u2)和 v=(v1,v2) 它们的叉乘定义如下：u x v = u1v2 - u2v1 = |OU||OV|sin a 并且

当 u x v > 0, v在p的右方向即向量u在向量v的顺时针方向

当 u x v < 0, v在p的左方向即向量u在向量v的逆时针方向

当 u x v = 0, 两个向量共线

abs(u1v2 - u2v1) = 2 S△OUV

极角排序常用方法：

要求输入为多个点的(x, y)坐标，按照某个点例如(0, 0)进行极角排序。

建立的基本结构体来总结以上的性质

struct Vector{
    double x, y;
	double operator^(const Vector& other) const {
        return (x * other.y - other.x * p1); // 计算叉积
    }
    bool isOnLeft(const Vector& other) const{
        return *this ^ other < 0;
    }
    bool isCollinear(const Vector& other) const{
        return *this ^ other == 0; // 是否共线
    }
};

struct Point{
	double x, y;
    Vector operator-(const Point& other) const {
        return Vector({x - other.x, y - other.y}); // 获得两点之间的向量
    }
};

对此我们有多种实现方法

方法1：利用atan2（）函数按极角从小到大排序。

介绍atan2()函数：

double atan2(double y, double x); // 函数原型

与简单的 atan(y/x) 不同，atan2 能够正确处理各个象限内的角度，并避免由于除零操作引起的错误。它能够通过坐标的符号来确定角度所在的象限。

对于atan(y/x)，由于仅仅使用 y 和 x 的比值，atan(y/x) 无法确定角度所在的象限，因此需要额外的逻辑来处理。它的值域在−π/2 到 +π/2

对于atan2(y, x)

atan2 是为了弥补 atan(y/x) 的不足而设计的。它接受两个参数 y 和 x，并根据它们的符号来确定角度所在的象限，避免了由于 x 接近零而引起的问题。atan2 返回的角度范围通常是 −π 到 π。

double angle = std::atan2(y, x);

第一象限：atan2 返回值在 0 到 π/2 之间（开区间）。
第二象限：atan2 返回值在 -π/2 到 0 之间（闭区间）。
第三象限：atan2 返回值在 -π 到 -π/2 之间（闭区间）。
第四象限：atan2 返回值在 π/2 到 π 之间（开区间）。

在进行atan2的比较之前我们需要先判断象限，然后再进行比较

int Quadrant(const Point & a)　　// 象限排序，注意包含四个坐标轴
{
    if(a.x > 0 && a.y >= 0)  return 1;
    if(a.x <= 0 && a.y > 0)  return 2;
    if(a.x < 0 && a.y <= 0)  return 3;
    if(a.x >= 0 && a.y < 0)  return 4;
}

bool cmp1(const Point & a, const Point & b)
{
    if(atan2(a.y, a.x)!=atan2(b.y, b.x))
        return atan2(a.y, a.x)<atan2(b.y, b.x);
    else return a.x < b.x;
}

bool cmp3(const Point & a, const Point & b)  // 先按象限从小到大排序 再按极角从小到大排序
{
    if(Quadrant(a) == Quadrant(b)) // 返回值就是象限
        return cmp1(a, b);
    else Quadrant(a) < Quadrant(b);
}

方法2：利用叉积性质小到大排序

叉积正负性可以判断位于左侧还是右侧，利于排序。

bool cmp(const Point & a, const Point & b) 
{
    Point p({0, 0}); // 原点
	Vector v1 = a - p;
    Vector v2 = b - p;
    if(v1 ^ v2 == 0)
        return a.x < b.x;
    else return v1 ^ v2 > 0;
}

极角排序的应用：

1.凸包问题（Graham扫描法）

假设平面上有多个点，过某些点作一个多边形，使这个多边形能把所有点都“包”起来。当这个多边形是凸多边形的时候，我们就叫它“凸包”。

给定多个点，求形成凸包的点有哪些？

对于这种问题，我们就可以采用极角排序

首先，最左下角的一个点是必然在凸包上的。我们以这个点为极点进行极角排序。按照极角排序的顺序将多个点依次相连，可以获得到一个多边形，这个多边形不一定是凸多边形，但是包含了所有的点。

更换思路

我们维护一个栈，按照极角排序后的顺序遍历每个点。如果栈中点数小于3，就直接进栈；否则，检查栈顶三个点组成的两个向量的旋转方向是否为逆时针（用叉乘判断），若是则进栈，若不是则弹出栈顶，直到栈中点数小于3或者满足逆时针条件为止。组成的多边形，向量不断逆时针旋转，这必定是凸多边形。

using Points = vector<Point>;
double theta(Point p) { return p == O ? -1 / 0. : atan2(p.y, p.x); } // 求极角
void psort(Points &ps, Point c = O)                                  // 极角排序
{
    sort(ps.begin(), ps.end(), [&](auto p1, auto p2) {
        return lt(theta(p1 - c), theta(p2 - c));
    });
}
bool check(Point p, Point q, Point r) // 检查三个点组成的两个向量的旋转方向是否为逆时针
{
    return lt(0, cross(q - p, r - q));
}
Points chull(Points &ps)
{
    psort(ps, *min_element(ps.begin(), ps.end())); // 以最左下角的点为极角排序
    Points H{ps[0]};
    for (int i = 1; i < ps.size(); i++)
    {
        while (H.size() > 1 && !check(H[H.size() - 2], H.back(), ps[i]))
            H.pop_back();
        H.push_back(ps[i]);
    }
    return H;
}

Mai Icy