计算几何——极角排序
极角
在平面上任取一个顶点
O
O
O，称为极点；作射线
X
X
X，那么
O
X
OX
OX就是极轴。平面上任意一点和
O
O
O点作向量，与
O
X
OX
OX形成的夹角就叫做极角。通常选定逆时针方向为正，一般我们以
x
x
x轴为极轴，那么极角就是平面向量与
x
x
x轴的夹角
极角排序
给定极轴，在平面上分布着若干点，将这些点相对于极轴的极角大小排序，就叫做极角排序。注意如果极角相同，那么需要按 x x x升序处理
如下图，排序后的点集为
A
B
C
D
E
F
ABCDEF
ABCDEF
利用atan2(double y,double x)函数排序
a t a n 2 ( d o u b l e y , d o u b l e x ) atan2(double~~ y,double ~~x) atan2(double y,double x)函数返回的是原点至点 ( x , y ) (x,y) (x,y)的方位角，即与 x x x轴的夹角，单位是弧度,范围 ( − π , π ] (-π,π] (−π,π]。因此 a t a n 2 ( d o u b l e y , d o u b l e x ) atan2(double~~ y,double ~~x) atan2(double y,double x)函数天然适合极角排序
bool cmp(Point a, Point b) {
if(dcmp(atan2(a.y, a.x) - atan2(b.y, b.x)) == 0) //dcmp为判断浮点数是否为0的函数
return a.x < b.x;
return atan2(a.y, a.x) < atan2(b.y, b.x);
}
利用向量叉乘排序
下面是默认以 O O O点为极点
bool cmp(Point a, Point b) {
if((a ^ b) == 0) return a.x < b.x;
return (a ^ b) > 0;
}
如果需要自定义极点，那么就传入极点
Point o; //o为极点
bool cmp(Point a, Point b) {
Point p = a - c, q = b - o;
if((p ^ q) == 0) return p.x < q.x;
return (p ^ q) > 0;
}