1

我正在尝试根据顺时针排序点按顺时针顺序在 0,0 附近对点向量进行排序？.

当我手动计算单个点的结果时，排序函数的逻辑是有意义的并检查出来。但是，结果向量似乎没有根据 sort 函数进行排序。例如，以下是特定排序运行后的前 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 进行编译。

4

1 回答 1

3

正如我所怀疑的那样（实际上比我所怀疑的还要糟糕）。我试过这段代码

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

换句话说，您的排序功能是说一个值小于另一个值，反之亦然。显然没有排序算法可以处理这个问题。

于 2013-04-27T21:56:57.583 回答