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 に答える