Нахождение расстояния между двумя объектами

Question

Для моей игры мне нужно найти расстояние между двумя объектами в определенное время. У меня вопрос просто можно ли улучшить функцию findDistance? Кажется, у меня нет никаких проблем, мне только любопытно, если бы это было сделано лучше. Кроме того, если бы я сделал это в 3D-настройке, как бы я рассчитал его, поскольку есть другая ось?

#include <math.h>
#include <iostream>

struct point{float x, y;};

float findDistance(point &x, point &y)
{
    float distance, tempx, tempy;
    tempx = (x.x - y.x);
    tempx = pow(tempx, 2.0f);
    tempy = (x.y - y.y);
    tempy = pow(tempy, 2.0f);
    distance = tempx + tempy;
    distance = sqrt(distance);
    return distance;
}

int main()
{
    point a, b;
    a.x = -2;
    a.y = -3;
    b.x = -4;
    b.y = 4;

    std::cout << "The distance between point x and y is: " << findDistance(a, b) << std::endl;
    return 0;
}

Answer 1

3d:

float findDistance(point &x, point &y)
{
    float distance, tempx, tempy, tempz;
    tempx = (x.x - y.x);
    tempx = tempx * tempx; //compiler _might_ be able to make this faster
    tempy = (x.y - y.y);
    tempy = tempy * tempy;
    tempz = (x.z - y.z);
    tempz = tempz * tempz;
    distance = tempx + tempy + tempz;
    distance = sqrt(distance);
    return distance;
}

Кроме замены pos(x,2) на x*x, это не может быть оптимизировано и остается универсальным / точным, но если вам не нужен универсальный, это может быть быстрее:

bool distanceLessThan(point &x, point &y, float distance)
{
    float tempx, tempy, tempz, tempd;
    tempx = std::abs(x.x - y.x);
    tempy = std::abs(x.y - y.y);
    tempz = std::abs(x.z - y.z);
    if (tempx + tempy + tempz < distance) //for small distances, don't square
        return true;
    if (tempx + tempy + tempz > distance/2) //for large distances, don't square
        return false;
    tempx = tempx * tempx;
    tempy = tempy * tempy;
    tempz = tempz * tempz;
    tempd = distance * distance; 
    if (tempx + tempy + tempz < tempd)
        return true;
    return false;
}

Answer 2

Я чувствую себя в целом pow (foo, 2) будет медленнее, чем foo * foo

Также спросите себя, нужно ли в ваших расчетах расстояние илидостаточно square_of_distance.

Например, чтобы определить, какое расстояние больше, вы можете просто сравнить square_of_distances вместо фактического расстояния, тем самым сохранив вызов в sqrt

Answer 3

Для 3D, просто добавьте tempz к расстоянию:

tempz = (x.z - y.z);
tempz = pow(tempz, 2.0f);
distance = tempx + tempy + tempz;

Кстати, «если он не сломался, не чините его». Не нужно беспокоиться об изменении того, что уже работает.

Answer 4

Ваш текущий подход хорош, и для новой координации просто добавьте его, как и другие:

struct point{float x, y,z;};

float findDistance(point &x, point &y)
{
    float distance, tempx, tempy;

    tempx = (x.x - y.x);
    tempx = pow(tempx, 2.0f);
    tempy = (x.y - y.y);
    tempy = pow(tempy, 2.0f);
    tempz = (x.z - y.z);
    tempz = pow(tempz, 2.0f);
    distance = tempx + tempy + tmpz;
    distance = sqrt(distance);
    return distance;
}

Фактически для n измерений у вас есть та же формула для расчета расстояния, но вы должны добавить новые измерения.

Answer 5

Я бы не использовал функцию pow:

distance = tempx*tempx + tempy*tempy;

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

Но имейте в виду «преждевременную оптимизацию» и правило 80-20 (80% времени выполнения тратится на 20% кода), поэтому, возможно, сначала запустите некоторые тесты производительности и только если вы видите, что тратите много времени в функции findDistance начните ее оптимизировать.

Answer 6

Вы могли бы повысить производительность, если передадите по значению:

float findDistance(point a, point b)
{
    a.x -= b.x;
    a.x *= a.x; 
    a.y -= b.y;
    a.y *= a.y
    return sqrt(a.x * a.y);
}

Ответ Mooing Duck содержит все остальное, что вы должны знать.

Answer 7

Просто добавьте z, но вы не можете сделать намного лучше, чем это.Вы можете заменить pow (x, 2) на x * x, но это все.Если вам не нужно знать расстояние, просто столкнулись ли два объекта, тогда есть некоторые оптимизации, но в остальном:

float findDistance(point &x, point &y)
{
  float distance, tempx, tempy, tempz;
  tempx = x.x - y.x;
  tempy = x.y - y.y;
  tempz = x.z - y.z;
  distance = sqrt(tempx*tempx + tempy*tempy + tempz*tempz);
  return distance;
}

- это лучшее, что вы можете сделать.

Answer 8

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