algorithm - 配列内の角度の最大差を見つける

Question

-180 から 180 までの値の配列である加速度計データを使用しています。角度を度で表します。

任意の 2 つの角度の最大差を見つけるための巧妙なアルゴリズムはありますか?

Answer 1

角度が [0, 180] にある場合は正であり、[-180, 0] にある場合は負であるとします。

リストをスキャンして、次のことを行います。
1 最大および最小の正の角度を記録します。
2 最大および最小の負の角度を記録
します。変換によるものであることを示すフラグ

#1 の場合、最大の差は単純に最大の角度から最小の角度を差し引いたものです。#2もそうです。

#3 では、最初に角度を並べ替えます。ソートされたリストの最後からスキャンします。隣接する角度の種類が異なる場合 (1 つは変換によるもので、もう 1 つは変換によるものではありません)、差を計算します。その差がこれまでに遭遇した最小のものである場合は、それを記録し、スキャンを続けます。完了したら、180 - 差を使用し、結果を差 #3 とします。

これで 3 つの違いがあります。最も大きいものを選択してください。それが答えだと思います。

複雑さのために、すべてのスキャンは O(n) です。並べ替えの場合、すべての角度が正または負の場合、フェーズ #3 はまったく必要ありません。フェーズ 3 が必要な場合は、角度を小さくすることができます。たとえば、リストの正の角度が少ない場合、正を負に、またはその逆に変換できます。並べ替えは O(nlgn) ですが、n を小さくすることができます。

Answer 2

これはRWチュートリアルから入手しました。

あなたが望むものとは反対です（最小の角度を返します）が、微調整することができます。

// Returns shortest angle between two angles,
// between -M_PI and M_PI

static inline CGFloat ScalarShortestAngleBetween(const CGFloat a, const CGFloat b)
{
    CGFloat difference = b - a;
    CGFloat angle = fmodf(difference, M_PI * 2);
    if (angle >= M_PI)
    {
        angle -= M_PI * 2;
    }
    return angle;
}