PrepBro
← Назад к вопросам

Как понять расстояние между двумя точками на экране?

1.0 Junior🔥 51 комментариев
#Структуры данных и алгоритмы

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI28 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Вычисление расстояния между двумя точками

Это фундаментальная задача в компьютерной геометрии, графике и обработке координат. Существует несколько подходов с разными трейд-офами между скоростью и точностью.

Евклидово расстояние (Euclidean Distance)

Самый распространённый способ.

#include <cmath>
#include <iostream>

struct Point {
    float x, y;
};

// Классический способ
float distance(const Point& p1, const Point& p2) {
    float dx = p2.x - p1.x;
    float dy = p2.y - p1.y;
    return std::sqrt(dx * dx + dy * dy);
}

int main() {
    Point p1 = {0, 0};
    Point p2 = {3, 4};
    
    float dist = distance(p1, p2);
    std::cout << "Расстояние: " << dist << std::endl;  // 5.0
    
    return 0;
}

Формула: d = √((x₂ - x₁)² + (y₂ - y₁)²)

Временная сложность: O(1) - константная Точность: зависит от типа (float/double)

Оптимизация 1: Квадратное расстояние (без sqrt)

Если нужно сравнивать расстояния, sqrt не требуется.

// МЕДЛЕННО - sqrt очень дорогая операция
if (distance(p1, p2) < 10.0f) {
    // ...
}

// БЫСТРО - сравниваем квадраты расстояний
float distance_squared(const Point& p1, const Point& p2) {
    float dx = p2.x - p1.x;
    float dy = p2.y - p1.y;
    return dx * dx + dy * dy;  // Без sqrt!
}

if (distance_squared(p1, p2) < 100.0f) {  // 10² = 100
    // ...
}

Ускорение: в 2-3 раза быстрее (sqrt очень дорогая операция) Когда использовать: всегда когда нужно сравнивать или проверять условия

Оптимизация 2: Быстрое приближение (Chebyshev)

Для минимальных вычислений (например, в игрях 60FPS).

float distance_chebyshev(const Point& p1, const Point& p2) {
    float dx = std::abs(p2.x - p1.x);
    float dy = std::abs(p2.y - p1.y);
    return std::max(dx, dy);  // Грубое приближение
}

Плюсы: супер быстро, нет sqrt, нет умножений Минусы: менее точно (дает макс из разностей, не диагональ) Использование: collision detection в простых играх

Оптимизация 3: Manhattan Distance (Manhattan Distance)

Для сеток и дискретных координат.

float distance_manhattan(const Point& p1, const Point& p2) {
    float dx = std::abs(p2.x - p1.x);
    float dy = std::abs(p2.y - p1.y);
    return dx + dy;  // Сумма разностей
}

int main() {
    Point p1 = {0, 0};
    Point p2 = {3, 4};
    
    float euclidean = distance(p1, p2);      // 5.0
    float manhattan = distance_manhattan(p1, p2);  // 7.0
    
    return 0;
}

Когда использовать: для шахматных координат, в алгоритмах поиска пути (A*), для сеток

Трёхмерное расстояние

Для 3D графики.

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

float distance_3d(const Point3D& p1, const Point3D& p2) {
    float dx = p2.x - p1.x;
    float dy = p2.y - p1.y;
    float dz = p2.z - p1.z;
    return std::sqrt(dx*dx + dy*dy + dz*dz);
}

float distance_3d_squared(const Point3D& p1, const Point3D& p2) {
    float dx = p2.x - p1.x;
    float dy = p2.y - p1.y;
    float dz = p2.z - p1.z;
    return dx*dx + dy*dy + dz*dz;  // Без sqrt
}

Практический пример: Обнаружение клика мышки

class Button {
private:
    Point center;
    float radius;
    
public:
    Button(Point c, float r) : center(c), radius(r) {}
    
    bool is_clicked(const Point& mouse_pos) {
        // Используем квадратное расстояние для скорости
        float dist_sq = distance_squared(center, mouse_pos);
        float radius_sq = radius * radius;
        return dist_sq <= radius_sq;  // Не используем sqrt!
    }
};

int main() {
    Button btn({100, 100}, 20.0f);
    Point mouse = {110, 105};
    
    if (btn.is_clicked(mouse)) {
        std::cout << "Button clicked!" << std::endl;
    }
    
    return 0;
}

Оптимизация 4: SIMD для множественных вычислений

Если считаете расстояния до тысяч точек.

#include <immintrin.h>  // SSE/AVX

// SIMD версия для 4 точек одновременно
void distance_simd(const Point* points, int count, float* results) {
    for (int i = 0; i < count; i += 4) {
        __m128 x = _mm_loadu_ps(&points[i].x);
        __m128 y = _mm_loadu_ps(&points[i].y);
        
        __m128 dx = _mm_sub_ps(x, _mm_set_ps1(0));  // x - ref_x
        __m128 dy = _mm_sub_ps(y, _mm_set_ps1(0));  // y - ref_y
        
        __m128 dist_sq = _mm_add_ps(
            _mm_mul_ps(dx, dx),
            _mm_mul_ps(dy, dy)
        );
        
        __m128 dist = _mm_sqrt_ps(dist_sq);
        _mm_storeu_ps(&results[i], dist);
    }
}

Ускорение: в 4 раза (обрабатываем 4 точки параллельно) Когда использовать: обработка больших облаков точек, scientific computing

Сравнение методов

Метод              | Скорость | Точность | Использование
──────────────────|----------|----------|────────────────────
Евклидово         | O(1)     | ⭐⭐⭐   | Стандарт
Квадратное (sqrt) | O(1)     | ⭐⭐⭐   | Сравнения расстояний
Chebyshev         | O(1)     | ⭐      | Грубые приближения
Manhattan         | O(1)     | ⭐⭐    | Сетки, A*
SIMD              | ⭐⭐⭐   | ⭐⭐⭐   | Большие облака

Ошибки и лучшие практики

Ошибка 1: Вычисление sqrt когда не нужно

// ПЛОХО - всегда считаем sqrt
if (distance(p1, p2) < threshold) { }

// ХОРОШО - сравниваем квадраты
if (distance_squared(p1, p2) < threshold * threshold) { }

Ошибка 2: Использование float когда нужен double

// Для высокой точности используйте double
double distance_precise(const Point& p1, const Point& p2) {
    double dx = p2.x - p1.x;
    double dy = p2.y - p1.y;
    return std::sqrt(dx * dx + dy * dy);
}

Ошибка 3: Забывают про границы значений

// Уходит в переполнение если координаты большие
int dx = (large_int1 - large_int2);
int result = dx * dx;  // Может переполниться!

// Правильно - используйте более широкие типы
long long dx = (large_int1 - large_int2);
long long result = dx * dx;  // Безопасно

Реальный пример: Collision Detection

#include <vector>
#include <cmath>

class Circle {
public:
    Point center;
    float radius;
    
    bool intersects(const Circle& other) const {
        float dist_sq = distance_squared(center, other.center);
        float min_dist = radius + other.radius;
        return dist_sq <= min_dist * min_dist;
    }
};

int main() {
    Circle c1({0, 0}, 5);
    Circle c2({8, 0}, 5);
    
    if (c1.intersects(c2)) {
        std::cout << "Circles collide!" << std::endl;
    }
    
    return 0;
}

Вывод

Для большинства случаев:

float distance_squared(const Point& p1, const Point& p2) {
    float dx = p2.x - p1.x;
    float dy = p2.y - p1.y;
    return dx * dx + dy * dy;  // Быстро и точно
}

Если нужна точная величина:

float distance(const Point& p1, const Point& p2) {
    float dx = p2.x - p1.x;
    float dy = p2.y - p1.y;
    return std::sqrt(dx * dx + dy * dy);  // Точно но медленнее
}
Как понять расстояние между двумя точками на экране? | PrepBro