我'm trying to understand the 2915373 algorithm in Steven Halim and Felix Halim'的书竞争性编程 . 给定平面中n个点的集合P，"convex hull"问题是找到形成包含所有其他点的凸多边形的顶点的子集CH（P） . 这是一张概述其方法的图片：
他们的算法首先根据它们相对于"pivot"的角度对点进行排序，即P中最下面和最右边的点 .
我在理解他们的 angle_comp 功能时遇到了一些问题 - 它的作用是什么，目的是什么 . 任何人都可以帮我理解吗？
typedef struct {
double x, y ;
} point;
point pivot;
// A function to compute the distance between two points:
double dist2 (point a, point b)
{
double dx = a.x - b.x ;
double dy = a.y - b.y ;
return sqrt (dx *dx + dy * dy) ;
}
// A function to compare the angles of two points with respect to the pivot:
bool angle_comp (point a, point b)
{
if (fabs(area2(pivot, a, b) - 0) < 10e-9)
return dist2(pivot, a) < dist2(pivot, b);
int d1x = a.x - pivot.x, d1y = a.y - pivot.y;
int d2x = b.x - pivot.x, d2y = b.y - pivot.y;
return (atan2((double) d1y, (double) d1x)
- atan2 ((double) d2y, (double)d2x))
< 0;
}
1 回答
如果我正确理解你的问题，你想知道为什么sort函数很重要？这是因为你的代码使用了格雷厄姆的扫描，这是一种寻找凸包的方法 . 为了使Graham的扫描更有效，必须按照相对于固定点的角度对点进行排序 .
angle_comp函数比较两个点A和B相对于枢轴点的角度 . 当插入std::sort时，此功能允许我们根据枢轴相对于枢轴的角度或距枢轴的距离对枢轴周围的所有点进行排序 .对于枢轴周围的两个点A和B.如果A点和B点具有相同的角度，或者如果其中一个都在枢轴附近，那么我们需要一种替代方法来对两点进行排序 . 我们根据它们与枢轴的距离来对点进行排序 .
另外，我们找出A点和B点相对于我们的枢轴的位置 . 我们通过从我们的点中减去枢轴来实现这一点 . 因此，例如，如果我们的枢轴是（4,3）并且A是（5,7），那么A是1个单位右边，4个单位来自我们的枢轴 . 如果我们的轴是（0,0），那么A将是（1,4） . 希望这是可以理解的 .
在我们得到相对点（即D）之后，我们计算相对于我们的枢轴或原点的点的角度 .
atan2接受两个参数，即我们的点的y值和我们的点的x值，并以弧度为单位吐出我们的点的角度 . 对于atan2，0弧度定义为远离原点的任何点（N，0），随着弧度增加，该点围绕枢轴或原点逆时针旋转 .然后我们减去D的角度，远离D2的角度 . 如果D2的角度大于D1的角度，我们返回true，
std::sort可以使用返回的数据逆时针对角度进行排序 .