3

ポイントからポイントまでの距離: dist = sqrt(dx * dx + dy * dy); しかし、sqrt は遅すぎて受け入れられません。本の 2 点の距離を推定するために、Taylor McLaughlin Series という方法を見つけました。しかし、次のコードが理解できません。私を助けてくれてありがとう。

#define MIN(a, b) ((a < b) ? a : b)
int FastDistance2D(int x, int y)
{
    // This function computes the distance from 0,0 to x,y with 3.5% error
    // First compute the absolute value of x, y
    x = abs(x);
    y = abs(y);

    // Compute the minimum of x, y
    int mn = MIN(x, y);

    // Return the distance
    return x + y - (mn >> 1) - (mn >> 2) + (mn >> 4);
}

McLaughlin Series に関する関連データを参照しましたが、戻り値が McLaughlin Series を使用して値を推定する方法をまだ理解できません。みんなありがとう〜

4

2 に答える 2

1

このタスクは、別のタスクとほとんど同じです: 非常に高速な 3D 距離チェック?

そして素晴らしい記事へのリンクがありました: http://www.azillionmonkeys.com/qed/sqroot.html

この記事では、ルートを近似するためのさまざまなアプローチを見つけることができます。たとえば、これはあなたに適しているかもしれません：

int isqrt (long r) {
    float tempf, x, y, rr;
    int is;

    rr = (long) r;
    y = rr*0.5;
    *(unsigned long *) &tempf = (0xbe6f0000 - *(unsigned long *) &rr) >> 1;
    x = tempf;
    x = (1.5*x) - (x*x)*(x*y);
    if (r > 101123) x = (1.5*x) - (x*x)*(x*y);
    is = (int) (x*rr + 0.5);
    return is + ((signed int) (r - is*is)) >> 31;
}

ルート操作を高速に計算できる場合は、通常の方法で距離を計算できます。

return isqrt(a*a+b*b)

もう 1 つのリンク: http://www.flipcode.com/archives/Fast_Approximate_Distance_Functions.shtml

u32 approx_distance( s32 dx, s32 dy )
{
   u32 min, max;

   if ( dx < 0 ) dx = -dx;
   if ( dy < 0 ) dy = -dy;

   if ( dx < dy )
   {
      min = dx;
      max = dy;
   } else {
      min = dy;
      max = dx;
   }

   // coefficients equivalent to ( 123/128 * max ) and ( 51/128 * min )
   return ((( max << 8 ) + ( max << 3 ) - ( max << 4 ) - ( max << 1 ) +
            ( min << 7 ) - ( min << 5 ) + ( min << 3 ) - ( min << 1 )) >> 8 );
}
于 2013-09-09T08:54:10.303 に答える
0

そうです、sqrtかなり遅い機能です。しかし、本当に距離を計算する必要がありますか?

多くの場合、代わりに距離² を使用できます。
例えば

  1. どの距離が短いかを調べたい場合は、距離の 2 乗と実際の距離を比較できます。
  2. 確認したい場合は、確認する100 > distanceこともできます10000 > distanceSquared

距離の代わりにプログラムで二乗されたディタンスを使用すると、多くの場合、 の計算を回避できますsqrt。

これがオプションであるかどうかは、アプリケーションによって異なりますが、常に考慮する価値があります。

于 2013-09-09T08:13:34.837 に答える