Быстрый расчет растояния между двумя точками (с погрешностью).

Автор: Eldar

Как правило для правильного расчета расстояния между двумя точками используется функция наподобие этой:

float distance_0 ( float dx, float dy )   
{  
  return sqrt(dx*dx+dy*dy);  
}

где dx=p1_x - p2_x;    а  dy=p1_y - p2_y
если ее использовать для нахождения растояния от центра области, то получится следующее:

Эта функция точна и проста в написании, но у нее есть серьезный недостаток - она очень медленная из-за квадратного корня.
Поэтому ради скорости можно пожертовать этим корнем - это не позволит найти расстояние, но позволяет сравнивать его с другим. (Для сравнения, известное расстояние надо возвести в квадрат и после этого сравнивать)

float distance_0 ( float dx, float dy )   
{  
  return dx*dx+dy*dy;  
}

А для того чтобы все же найти само расстояние, и главное быстро - придется пожертовать точностью, которая не всегда и нужна (например проверка столкновений).

float distance_1( float dx, float dy )
{
  if ( dx < 0 ) dx = -dx;
  if ( dy < 0 ) dy = -dy;
  if ( dx < dy )  return 0.961f*dy+0.398f*dx;  
  else    return 0.961f*dx+0.398f*dy;
}

Функция работает в 2 раза быстрее первого варианта и имеет погрешность 5%
При этом получается следующий график

Но и это еще не предел - если ее перевести на int то она станет в 2,5 раза быстрее первого варианта, с погрешностью 5%
и тем же графиком

int distance2( int dx, int dy )
{
  if ( dx < 0 ) dx = -dx;
  if ( dy < 0 ) dy = -dy;
  if ( dx < dy )  return (123*dy+51*dx)/128;  
  else    return (123*dx+51*dy)/128;
}

Также это можно упростить до квадрата со скоростью в 3,5 раза быстрее первого варианта, с погрешностью 30%

int distance2( int dx, int dy )
{
  if ( dx < 0 ) dx = -dx;
  if ( dy < 0 ) dy = -dy;
  if ( dx < dy )  return dy;  
  else    return dx;
}

3 октября 2003