3

点到点的距离：dist = sqrt(dx * dx + dy * dy); 但是 sqrt 太慢了，我不能接受。我找到了一种叫做 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)

还有一个链接： 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. 如果你想检查一个100 > distance你也可以检查10000 > distanceSquared

使用程序中的距离平方而不是距离通常可以避免计算sqrt.

这取决于您的应用程序是否适合您，但始终值得考虑。

于 2013-09-09T08:13:34.837 回答