c++ - "competitive programming 1"的凸包代码

Question

我试图理解 Steven Halim 和 Felix Halim 的书 Competitive Programming 中的“凸包”算法。 “凸包”问题是，给定平面中 n 个点的集合 P，找到一个子集 CH(P ) 形成包含所有其他点的凸多边形的顶点。这是一张概述他们方法的图片:

他们的算法首先根据点相对于“枢轴”的角度对点进行排序，即 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;
}

Answer 1

如果我没有正确理解你的问题，你想知道为什么排序功能很重要？这是因为您的代码使用了格雷厄姆扫描，这是一种查找凸包的方法。为了使 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) 的任意点，随着弧度的增加，该点绕轴心点或原点逆时针旋转。

然后我们从 D2 的角度中减去 D 的角度。如果 D2 的角度大于 D1 的角度，我们返回 true，std::sort 可以使用返回的数据对角度进行逆时针排序。