Самый быстрый способ рассчитать расстояние между двумя CGPoints? - PullRequest
Новая
       10

Самый быстрый способ рассчитать расстояние между двумя CGPoints?

13 голосов
/ 02 февраля 2012

Расстояние между двумя точками: 

sqrt((x1-x2)^2 + (y1-y2)^2)

Есть ли способ сделать эту математику быстрее в target-C?

РЕДАКТИРОВАТЬ: Я думаю, что мне нужно уточнить выше. Я написал формулу выше, чтобы уточнить, какую формулу я использую для расчета расстояния. ^ не предназначен для представления xor - я просто хотел представить математическую формулу без использования каких-либо функций, таких как pow или что-то еще, поэтому я хотел использовать ^, чтобы «поднять до выключения». Мне было интересно, если кто-нибудь знает, даст ли оптимизированная версия использование побитовых операторов или иным образом написание кода на ассемблере. Я использую формулу в приложении для iPhone / iPad.

Ответы [ 5 ]

35 голосов
/ 02 февраля 2012

Нет, если вам нужно точное расстояние, вы не можете превзойти эту формулу.

Хотя для ясности ^ это не оператор возведения в квадрат значения, а битовый оператор, который выполняет xor.

вам понадобится что-то вроде 

double dx = (x2-x1);
double dy = (y2-y1);
double dist = sqrt(dx*dx + dy*dy);

Если вы можете жить только с квадратом (что полезно, когда вы просто хотите сделать что-то вроде сортировки по расстоянию, вы можете использовать гораздо более эффективный 

double dx = (x2-x1);
double dy = (y2-y1);
double dist = dx*dx + dy*dy;

Они будут, по крайней мере, так же хороши, как раствор. В худшем случае pow () будет использовать стек и будет менее эффективным, но, возможно, ваш компилятор преобразует его в x * x для этого случая.

8 голосов
/ 08 октября 2014

Просто предлагая это как простое, красивое решение.Скорее всего, не быстрее, чем ранее, просто короче.Я лично использую hypot. 

double dist = hypot((x1-x2), (y1-y2));

По документам , это вернет вам "квадратный корень из (x ^ 2 + y ^ 2)".

7 голосов
/ 02 февраля 2012

На Intel Mac Clang скомпилирует: 

double distance = ({double d1 = x1 - x2, d2 = y1 - y2; sqrt(d1 * d1 + d2 * d2); });

в общей сложности 6 инструкций по математике: sub, mul, sub, mul, add, sqrt;довольно трудно победить это.(sqrt - это одна инструкция, хотя она занимает несколько циклов).

3 голосов
/ 03 февраля 2012

Единственное, что здесь можно улучшить - это функция вычисления квадратного корня.

Я пробовал эти две функции (которые можно найти в статье Википедии о вычислении квадратного корня ) для вычисления приблизительных значений квадратного корня: 

float fsqrt(float x)
{
  float xhalf = 0.5f * x;
  union
  {
    float x;
    int i;
  } u;

  u.x = x;
  u.i = 0x5f3759df - (u.i >> 1);
  x *= u.x * (1.5f - xhalf * u.x * u.x);

  return x;
}

float fsqrt2(float z)
{
    union
    {
        int tmp;
        float f;
    } u;

    u.f = z;

    /*
     * To justify the following code, prove that
     *
     * ((((val_int / 2^m) - b) / 2) + b) * 2^m = ((val_int - 2^m) / 2) + ((b + 1) / 2) * 2^m)
     *
     * where
     *
     * val_int = u.tmp
     * b = exponent bias
     * m = number of mantissa bits
     *
     * .
     */

    u.tmp -= 1 << 23; /* Subtract 2^m. */
    u.tmp >>= 1; /* Divide by 2. */
    u.tmp += 1 << 29; /* Add ((b + 1) / 2) * 2^m. */

    return u.f;
}

Но на моем процессоре Core 2 Duo Pentium они работают не быстрее, чем инструкция x87 FPU FSQRT. Посмотрите, работают ли они быстрее, чем стандартный sqrtf()/sqrt() на вашей платформе, и достаточно ли точности.

3 голосов
/ 02 февраля 2012 
double dist = sqrt ( pow((x1-x2), 2) + pow((y1-y2), 2) );

с учетом x1, x2, y1, y2 равны float или double или целому числу.

...