极角排序

wenge · 2024-02-01 19:49:52 · 个人记录

极角排序

极角排序，是以一点为坐标原点，将其他点按照在这个系中的极角排序。

从数学上来讲，极坐标系中一个点的极角有无穷多个，但是在 (-\pi,\pi] 之间的只有一个。本文中的极角一般指这个值。（有一些定义认为极角的范围是 [0,2\pi)，但是由于atan2函数是这个取值范围，所以在本文中约定如上。）

很多问题在极角有序的时候会更好解决，一个比较经典的例子是 Graham 算法求凸包。

极角排序的方法

1.atan2

使用atan2可以直接计算出极角比较，简单粗暴。

2.叉乘法

atan2有精度问题，实际使用的时候有可能会被出题人卡，或者这题本来不卡atan2结果由于实现太过拉胯而被卡精度。而叉乘不会被卡精度。

基本原理是：

• 一个点（非原点）的 x,y 唯一确定这个点的极角。
• 假如 \vec b 是 \vec a 的逆时针方向（不能大于等于 \pi）等价于 \vec a \times \vec b >0。

由于叉乘是一个环形的东西（感性理解），正经的叉乘写法的极角排序的比较函数相对atan2复杂。

我整理了一个实现方法：一比象限，二比叉乘，三比模长。

叉乘虽然没精度问题，但是叉乘是一个环形的东西，假设有这么一种情境：假如 \vec a ,\vec b 极角分别是 -\dfrac{3\pi}{4},\dfrac{3\pi}{4}，那么按照叉乘，\vec a 应该在 \vec b 的顺时针方向，因为叉乘大于 0，这不是我们想要的。

所以我就见过一个很妙的操作：就是把去掉原点的整个平面分成两部分：

• 极角在 (0,\pi] 的，即：y>0 或者 y=0,x<0
• 极角在 (-\pi,0] 的，即不在第一部分的。

如果两点不在同一个部分之内，则在第一部分的点一定比第二部分的极角大。否则每个区间之内，任意两点极角之差一定小于 \pi，这个长度之内叉乘是可以有效比较大小的。

有一些题只关心极角这一个位置关系，不关心距离，可以不比较到原点的距离，有一些题就需要比较。

ll _cmp_by_polar(Point A,Point B){
    auto f=[](Point A){return A.y>0||(A.y==0&&A.x<0);};
    if(f(A)!=f(B))return f(A)<f(B);
    else if(_cross(A,B)!=0)return _cross(A,B)>0;
    return _dist(A,{0,0})<_dist(B,{0,0});
}