首页 > 代码库 > 极角排序详解:

极角排序详解:

极角排序详解

名词释义:

在平面内取一个定点O,叫极点,引一条射线Ox,叫做极轴,再选定一个长度单位和角度的正方向(通常取逆时针方向)。对于平面内任何一点M,用ρ表示线段OM的长度(有时也用r表示),θ表示从Ox到OM的角度,ρ叫做点M的极径,θ叫做点M的极角,有序数对 (ρ,θ)就叫点M的极坐标

四种极角排序代码详解:

 

 1 struct point
 2 {
 3     double x,y;
 4 };
 5 
 6 double cross(double x1,double y1,double x2,double y2) //计算叉积
 7 {
 8     return (x1*y2-x2*y1);
 9 }
10 
11 double compare(point a,point b,point c)
12 {
13     return cross((b.x-a.x),(b.y-a.y),(c.x-a.x),(c.y-a.y));
14 }

 

1、利用complex类按极角从小到大排序:

1 bool cmp0(const point& a, const point& b) // 利用complex类按极角从小到大排序
2 {
3     complex<double> c1(a.x,a.y);                   //头文件 #include<complex>
4     complex<double> c2(b.x,b.y);
5     if( arg(c1) == arg(c2))
6         return a.x<b.x;
7     return arg(c1) < arg(c2);
8 }

2、利用atan2()函数按极角从小到大排序

1 bool cmp1(point a,point b)//利用atan2()函数按极角从小到大排序
2 {
3     if(atan2(a.y,a.x)!=atan2(b.y,b.x))
4         return atan2(a.y,a.x)<atan2(b.y,b.x);
5     else return a.x<b.x;
6 }

3、利用叉积按极角从小到大排序

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)
7         return a.x<b.x;
8     else return compare(c,a,b)>0;
9 }

4、先按象限从小到大排序 再按极角从小到大排序

 1 int Quadrant(point a)  //象限排序
 2 {
 3     if(a.x>0&&a.y>=0)  return 1;
 4     if(a.x<=0&&a.y>0)  return 2;
 5     if(a.x<0&&a.y<=0)  return 3;
 6     if(a.x>=0&&a.y<0)  return 4;
 7 }
 8 
 9 
10 bool cmp3(point a,point b)  //先按象限从小到大排序 再按极角从小到大排序
11 {
12     if(Quadrant(a)==Quadrant(b))
13         return cmp1(a,b);
14     else Quadrant(a)<Quadrant(b);
15 }

 


本文为个人随笔,如有不当之处,望各位大佬多多指教.
若能为各位博友提供小小帮助,不胜荣幸.

极角排序详解: