c++ - 给定一个枢轴点，按照它们与枢轴点所成角度的递增顺序对一组点进行排序

Question

正如标题中所说，我们需要按角度升序对点进行排序。

我正在使用带有枢轴点和其他点的叉积。如果考虑任何两个点与枢轴点的叉积为正，则表示这两个点按升序排序。

我无法在这个想法中找到错误，但这不起作用。代码是：

//Here,a[0] is the pivot point.

//pivot is a global variable assigned to a[0].

vector<pair<int, int>>a(n);

sort(a.begin() + 1, a.end(), comp);

int comp(pair<int, int> x, pair<int, int> y) {
    int cross_product = crpd(pivot, x, y);

    if (cross_product >= 0)
        return 1;

    return 0;
}

int crpd(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
    //y2*x1 - y1*x2
    int y2 = a.second - c.second;
    int x2 = a.first - c.first;
    int y1 = a.second - b.second;
    int x1 = a.first - b.first;
    int ans = x1 * y2 - x2 * y1;
    return ans;
}

Sample Input:

Pivot: (0,-4)

Points: [ (-5,0) , (-5,1) , (-4,2) , (-3,3) , (-1,4) , (5,0) , (4,-3) , (0,-4) , (-4,-3) ] 
Expected Output: [ (4,-3) , (5,0) , (-1,4) , (-3,3) , (-4,2) , (-5,1) , (-5,0) , (-4,-3) ]
Displayed Output: [ (-5,0) , (4,-3) , (5,0) , (-1,4) , (-3,3) , (-4,2) , (-5,1) , (-4,-3) ] 

如果有人在任何地方发现任何错误，请回答

标签： c++algorithmmathoptimizationconvex-hull

Answer 1

叉积“原样”仅给出角度符号，因为您的向量未标准化（单位长度）。除以向量的大小是朝着正确方向迈出的一步，但它给出了可能的角度范围-Pi/2..Pi/2

您可以获得可比较的价值 - 使用全范围的-Pi..Pi角度atan2

angle = atan2(x1 * y2 - x2 * y1, x1 * x2 + y1 * y2);