30

2 つのベクトル間の角度を見つけることは、コサイン ルールを使用して難しいことではありません。sqrtただし、リソースが非常に限られているプラ​​ットフォーム向けにプログラミングしているため、やなどの計算は避けたいと思いarccosます。単純な分割でも、可能な限り制限する必要があります。

幸いなことに、角度自体は必要ありませんが、角度に比例する値のみが必要です。

そこで、2 つのベクトル間の角度に関連する量を計算するための計算コストの低いアルゴリズムを探しています。これまでのところ、私は法案に適合するものを見つけていませんし、自分で何かを思いつくこともできませんでした.

4

9 に答える 9

19

実際のユークリッド角度は必要ないが、角度比較のベースとして使用できるものは必要ない場合は、タクシー ジオメトリに変更することをお勧めします。これは、三角法を削除でき、精度を維持しながら速度が低下するためです (または少なくとも精度がわずかに失われます。以下を参照してください)。

最新の主なブラウザ エンジンでは、高速化係数は 1.44 ～ 15.2 で、精度は atan2 とほぼ同じです。ひし形の角度の計算は、atan2 よりも平均 5.01 倍速く、Firefox 18 でインライン コードを使用すると、速度は 15.2 倍に達します。速度比較: http://jsperf.com/diamond-angle-vs-atan2/2 .

コードは非常に単純です。

function DiamondAngle(y, x)
{
    if (y >= 0)
        return (x >= 0 ? y/(x+y) : 1-x/(-x+y)); 
    else
        return (x < 0 ? 2-y/(-x-y) : 3+x/(x-y)); 
}

次の表に示すように、上記のコードは 0 から 4 の間の角度を提供しますが、atan2 は -PI と PI の間の角度を提供します。

ここに画像の説明を入力

ひし形の角度は常に正で、0 ～ 4 の範囲であることに注意してください。一方、atan2 は負のラジアンも与えます。そのため、ダイヤモンドの角度はより正規化されています。また、atan2 では、範囲の長さが 2*pi (つまり、6.283185307179586) であるのに対し、ダイヤモンドの角度では 4 であるため、もう少し正確な結果が得られることに注意してください。実際には、これはあまり重要ではありません。rad 2.3000000000000001 と 2.3000000000000002 はどちらもダイヤモンド角度 1.4718731421442295 ですが、0 を 1 つ削除して精度を下げると、rad 2.30000000000001 と 2.300000000000002 は両方とも異なるダイヤモンド角度になります。このダイヤモンド角度の「精度の低下」は非常に小さいため、距離が大きい場合にのみ大きな影響を与えます。http://jsbin.com/bewodonase/1/edit?outputで変換を試すことができます(旧バージョン:http://jsbin.com/idoyon/1 ):

ここに画像の説明を入力

上記のコードは角度をすばやく比較するには十分ですが、多くの場合、ダイヤモンドの角度をラジアンに、またはその逆に変換する必要があります。あなたが例えば。ラジアン角度としてある程度の許容範囲があり、この許容範囲が他の角度と比較される 100,000 回のループがある場合、atan2 を使用して比較を行うのは賢明ではありません。代わりに、ループする前に、ラジアン許容値をタクシー (ダイヤモンド角度) 許容値に変更し、ダイヤモンド許容値を使用してループ内比較を行います。このようにして、コードの速度が重要な部分で低速の三角関数を使用する必要がなくなります ( = inループ)。

この変換を行うコードは次のとおりです。

function RadiansToDiamondAngle(rad)
{
  var P = {"x": Math.cos(rad), "y": Math.sin(rad) };
  return DiamondAngle(P.y, P.x);
}

お気づきのように と がcosありsinます。ご存知のように、それらは遅いですが、ループ内で変換を行う必要はありませんが、ループする前に行うと、速度が大幅に向上します。

何らかの理由で、ダイヤモンドの角度をラジアンに変換する必要がある場合。ループして角度比較を行った後、たとえば返されます。比較の最小角度またはラジアンなど、コードは次のとおりです。

function DiamondAngleToRadians(dia)
{
  var P = DiamondAngleToPoint(dia);
  return Math.atan2(P.y,P.x);
}

function DiamondAngleToPoint(dia)
{
  return {"x": (dia < 2 ? 1-dia : dia-3), 
  "y": (dia < 3 ? ((dia > 1) ? 2-dia : dia) : dia-4)};
}

ここでは を使用していますがatan2、これは遅いですが、ループの外側でこれを使用することをお勧めします。単純に何らかの係数を掛けてダイアモンド角度をラジアンに変換することはできませんが、代わりに、その点と正の X 軸の間のダイアモンド角度が問題のダイアモンド角度であるタクシー ジオメトリの点を見つけ、atan2 を使用してこの点をラジアンに変換します。

これは、迅速な角度比較には十分なはずです。

もちろん、他のatan2高速化技術（CORDICやルックアップテーブルなど）がありますが、知る限り、それらはすべて精度を失い、atan2よりも遅い場合があります。

背景: 内積、内積、コサインの法則、単位円、ルックアップ テーブルなど、いくつかの手法をテストしましたが、速度と精度の両方が重要な場合には十分ではありませんでした。最後に、http://www.freesteel.co.uk/wpblog/2009/06/encoding-2d-angles-without-trigonometry/で、目的の機能と原理を備えたページを見つけました。

最初に、ユークリッドの距離が大きいほどタクシーでも距離が大きくなるため、タクシーの距離も正確かつ迅速な距離比較に使用できると想定しました。ユークリッド距離とは逆に、始点と終点の間の角度がタクシーの距離に影響を与えることに気付きました。ユークリッドとタクシーの間で簡単かつ迅速に変換できるのは、垂直方向と水平方向のベクトルの長さだけですが、それ以外の場合は角度を考慮する必要があり、プロセスが遅すぎます (?)。

結論として、角度および/または距離のいくつかの比較のループまたは再帰である速度が重要なアプリケーションでは、角度はタクシー空間で比較し、距離はユークリッド (平方、平方根を使用せずに) 空間で比較する方が速いと考えています。

于 2013-02-03T18:51:31.590 に答える
13

CORDICアルゴリズムを試しましたか? これは、極 ↔ 直交問題を加算/減算/ビットシフト + テーブルのみで解決するための一般的なフレームワークであり、基本的に形式 tan -1 (2 -n ) の角度で回転を行います。反復回数を変更することで、精度と実行時間をトレードオフできます。

あなたの場合、1 つのベクトルを固定参照として取り、もう 1 つのベクトルを一時的なベクトルにコピーします。このベクトルは、コーディック角度を使用して最初のベクトル (ほぼ二等分) に向けて、目的の角度精度に達するまで回転させます。

(編集:内積の符号を使用して、各ステップで順方向または逆方向に回転するかどうかを決定します。乗算が内積を使用できるほど安価である場合は、CORDIC を気にしないでください。おそらく、sin/cos ペアのテーブルを使用してください。角度 π/2 nの回転行列を使用して、二分法の問題を解決します。)

(編集:コメントで Eric Bainville の提案が気に入っています: 両方のベクトルをゼロに向かって回転させ、角度の差を追跡します。)

于 2009-09-15T14:34:03.890 に答える
4

ここで私はまだコメントする特権を持っていないので (math.se にはありますが)、これは実際にはティモのダイヤモンド角度に関する投稿への返信です。

L1 ノルムに基づくダイヤモンド角度の全体的な概念は最も興味深いものであり、正の X 軸に対してどのベクトルが大きい/小さいかを比較するだけであれば、それで十分です。ただし、OPは2つの一般的なベクトル間の角度について言及しており、OPはそれを滑らかさ/コーナーステータスまたはそのようなsthを見つけるための許容範囲と比較したいと考えていますが、残念ながら、jsperf.comで提供されている式のみでまたは freesteel.co.uk (上記のリンク) ダイヤモンド アングルを使用してこれを行うことはできないようです。

式の Asymptote 実装からの次の出力を観察します。

Vectors : 50,20 and -40,40
Angle diff found by acos      : 113.199
Diff of angles found by atan2 : 113.199
Diamond minus diamond         : 1.21429
Convert that to degrees       : 105.255
Rotate same vectors by 30 deg.
Vectors : 33.3013,42.3205 and -54.641,14.641
Angle diff found by acos      : 113.199
Diff of angles found by atan2 : 113.199
Diamond minus diamond         : 1.22904
Convert that to degrees       : 106.546
Rotate same vectors by 30 deg.
Vectors : 7.67949,53.3013 and -54.641,-14.641
Angle diff found by acos      : 113.199
Diff of angles found by atan2 : 113.199
Diamond minus diamond         : 1.33726
Convert that to degrees       : 116.971

つまり、atan2 の出力とは異なり、diamond(alpha)-diamond(beta) を実行して、それを許容範囲と比較することはできません。やりたいことがダイヤモンド(アルファ)>ダイヤモンド(ベータ)なら、ダイヤモンドでいいと思います。

于 2013-06-03T14:02:46.340 に答える
2

外積は 2 つのベクトル間の角度に比例します。ベクトルが正規化され、角度が小さい場合、外積は小さな角度近似によりラジアン単位の実際の角度に非常に近くなります。

具体的には：

I1Q2-I2Q1 は、I1Q1 と I2Q2 の間の角度に比例します。

于 2010-12-18T23:09:16.983 に答える
1

平方根を計算する必要がある場合は、invsqrt hackの使用を検討してください。

acos((x1*x2 + y1*y2) * invsqrt((x1*x1+y1*y1)*(x2*x2+y2*y2)));
于 2009-09-15T14:33:12.133 に答える