c++ - 对不服从排序函数的 vector 进行排序

Question

我正在尝试根据 Sort points in clockwise order? 在 0,0 左右按顺时针顺序对点 vector 进行排序.

当我手动计算各个点的结果时，排序函数的逻辑是有意义的并得到验证。但是，生成的 vector 似乎并未根据排序功能进行排序。例如，这是特定排序运行后的前 4 个元素:

[22.3701,450.519,-1045]   <- correct
[-22.429,-29.0513,-1006]  <- should be in position 2
[-147.806,65.0482,-1095]  <- should be in position 3
[68.0652,590.091,-942]    <- should be in position 1

这种情况应该被排序算法的第一个保护子句捕获:

if ( a.x >= 0 && b.x < 0 ) return true

变成:

if ( 68.0652 >= 0 && -22.429 < 0 ) return true

当然应该将 (68.0652,590.091) 点排序得更高。

这是我对排序函数的实现，由于我的中心点是 (0,0) 而被简化了:

bool sortVectorsClockwise( const Vec3f &a, const Vec3f &b )
{
    if ( a.x >= 0 && b.x < 0 ) return true;
    if ( a.x == 0 && b.x == 0 ) return a.y > b.y;

    float det = a.x * b.y - b.x * a.y;
    if ( det < 0 ) return true;
    if ( det > 0 ) return false;

    // points a and b are on the same line from the center, check which is
    // closer to the center
    return a.xy().length() > b.xy().length();
}

然后我像这样调用并打印结果:

sort( points.begin(), points.end(), sortVectorsClockwise );

for ( auto &p : points ) {
    cout << p << endl;
}

我正在使用 XCode 4.6、LLVM 4.2、C++11 进行编译。

Answer 1

正如我所怀疑的(实际上比我所怀疑的更糟)。我试过这段代码

int main()
{
    Vec3f a(22.3701, 450.519, -1045);
    Vec3f b(-22.429,-29.0513,-1006);
    if (sortVectorsClockwise(a, b))
        cout << "a<b\n";
    if (sortVectorsClockwise(b, a))
        cout << "b<a\n";
}

输出是

a<b
b<a

换句话说，您的排序函数表示一个值小于另一个，反之亦然。显然没有任何排序算法可以解决这个问题。