极角排序理解

佚名 6年前 (2019-05-15) 随笔 2173人围观抢沙发百度已收录

https://www.cnblogs.com/aiguona/p/7248311.html

极角排序：根据数学知识，在极坐标的情况下，有一个原地，一个参考方向（x轴正方向），现在对于其他点，对于原点，即存在一个极坐标（r，thata），对于极角排序。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

关于叉积：叉积=0是指两向量平行（重合）；叉积>0，则向量a在向量b的顺时针方向（粗略的理解为在a在b的下方）；叉积<0，则向量a在向量b的逆时针方向（粗略的理解为在a在b的上方）

如下利用叉积进行极角排序。

1 bool cmp2(point a,point b) 
2 {
3     point c;//原点
4     c.x = 0;
5     c.y = 0;
6     if(compare(c,a,b)==0)//计算叉积，compare函数是计算向量c->a,c->b的叉积，如果叉积相等，按照X从小到大排序
7         return a.x<b.x;
8     else return compare(c,a,b)>0;
9 }

如下利用atan2函数计算atan2值利用atan2排序。

函数形式：atan2（y，x）。范围是[-pi,pi]

由于3，4象限的atan2值为负，可以对他们加上一个2*pi，这样sort之后，象限就是从第一到第四排序好了。

atan2函数值举例如下：

0.785398 :atan2(1,1) 一象限

2.35619 :atan2(1,-1)二象限

-2.35619 :atan2(-1,-1)三象限
-0.785398 :atan2(-1,1)四象限

int cnt=0;
for(int j=0;j<n;j++){
if(i!=j)p[cnt++]=atan2(po[j].y-po[i].y,po[j].x-po[i].x);
if(p[cnt-1]<0)p[cnt-1]+=2*pi;
}
sort(p,p+cnt);
for(int j=0;j<cnt;j++)p[j+cnt]=p[j]+2*pi;//这行代码可选，是为了把前后的向量合起来，如果需要比较向量的相邻关系