Ряд Тейлора Маклафлина для оценки расстояния двух точек

Question

Ряд Тейлора Маклафлина для оценки расстояния двух точек

Расстояние от точки к точке: dist = sqrt (dx * dx + dy * dy);
Но sqrt слишком медленный, и я не могу этого принять. Я нашел метод под названием «Ряд Тейлора Маклафлина» для оценки расстояния двух точек в книге. Но я не могу понять следующий код. Спасибо всем, кто мне помогает.

#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);
}

Я ознакомился с соответствующими данными о серии Маклафлина, но до сих пор не могу понять, как возвращаемое значение использует серию Маклафлина для оценки значения. Спасибо всем ~

3

algorithm c++graphic taylor-series

Решение

Другие решения

Вы правы sqrt довольно медленная функция. Но вам действительно нужно вычислить расстояние?

Во многих случаях вы можете использовать расстояние² вместо.
Например.

Если вы хотите узнать, какое расстояние короче, вы можете сравнить квадраты расстояния, а также реальные расстояния.
Если вы хотите проверить, если 100 > distance Вы также можете проверить 10000 > distanceSquared

Используя квадрат дитанса в своей программе вместо расстояния, которое вы часто можете избежать sqrt,

Это зависит от вашего заявления, если это вариант для вас, но это всегда стоит рассмотреть.

0

Источник

Accepted Answer

Эта задача почти дублирует другую задачу:
Очень быстрая проверка расстояния 3D?

И там была ссылка на отличную статью:
http://www.azillionmonkeys.com/qed/sqroot.html

В статье вы можете найти различные подходы к приближению root. Например, может быть, этот подходит для вас:

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 );
}

1