3

我试图理解 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;
}
4

1 回答 1

4

如果我正确理解您的问题，您想知道为什么排序功能很重要吗？这是因为您那里的代码使用格雷厄姆扫描，这是一种查找凸包的方法。为了使 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可以使用返回的数据对角度进行逆时针排序。

于 2013-08-04T05:59:04.853 回答