Наименьшее расстояние между точкой и путем - PullRequest
Новая
       71

Наименьшее расстояние между точкой и путем

3 голосов
/ 31 августа 2010

для гео-онлайн-игры. Я ищу алгоритм, который находит кратчайшее расстояние между указанной точкой и известным путем, соединенным координатами x / y, чтобы я мог убить все лишние точки / узлы.Ссылка или ключевое слово для этого алгоритма очень мне помогут!спасибо за чтение

Для лучшего понимания: alt text

Ответы [ 3 ]

1 голос
/ 31 августа 2010

Вы хотите рассчитать это, чтобы сказать что-то вроде "если расстояние от точки до пути равно нулю, то удалить точку"?Если это так, то, вероятно, существует более простой способ удаления избыточных узлов.Возьмите три очка за раз (назовите их A, B и C).Рассчитайте угол между A и B, а также угол между B и C.Если два угла одинаковы, то точка B лежит на пути между A и C и является избыточной.Вы можете использовать функцию 'atan2' (или эквивалент вашего языка) для вычисления углов.

0 голосов
/ 14 февраля 2013

Это моя реализация Java для ближайшей точки на пути 

private Point getNearestPoint(Point from, List<Point> to_path) {

    int count = to_path.size();

    if (count == 0)
        return null;
    if (count == 1)
        return to_path.get(0);

    double nearest_dist = Double.MAX_VALUE;
    Point nearest_point = null;

    for (int i = 1; i < count; i++) {

        Point p1 = to_path.get(i-1);
        Point p2 = to_path.get(i);

        Point p = getNearestPointOnSegment(from, p1, p2);
        if (p != nearest_point) {
            double dist = dist(from, p);
            if (dist < nearest_dist) {
                nearest_dist = dist;
                nearest_point = p;
            }
        }
    }

    return nearest_point;
}

private Point getNearestPointOnSegment(Point from, Point p1, Point p2) {

    if (dist(p1, p2) < 1e3) {
        Log.d(TAG, "Points are near");
        return p1;
    }

    double d2 = dist2(p1, p2);
    double t = ((from.x - p1.x) * (p2.x - p1.x) + (from.y - p1.y) * (p2.y - p1.y)) / d2;

    if (t < 0) {
        //Log.d(TAG, "p1");
        return p1;
    }
    if (t > 1) {
        //Log.d(TAG, "p2");
        return p2;
    }

    //Log.d(TAG, "t:" + t);
    return new Point((int)(p1.x + t * (p2.x - p1.x)),
        (int)(p1.y + t * (p2.y - p1.y)));
}

private double dist(Point p1, Point p2) {
    return Math.sqrt(dist2(p1, p2));
}

private double dist2(Point p1, Point p2) {
    return sqr(p1.x - p2.x) + sqr(p1.y - p2.y);
}

private double sqr(double x) {
    return x * x;
}
0 голосов
/ 31 августа 2010

Это алгоритм поиска пути «точка-точка», который обычно используется в играх:

A * алгоритм поиска

Возможно, вам придется применить егонесколько раз между вашей точкой и путем, но обычно это очень быстро.Алгоритм имеет некоторые оптимизации для сеток карты (где расстояния между квадратами являются целыми числами).Есть описание этого в: Программировании стратегии в реальном времени с использованием MS DirectX 6.0 от Микки Кавика.

Алгоритм Джикстры - это хороший универсальный алгоритм поиска путиот одного исходного узла ко всем остальным узлам на графике.Вы можете остановить алгоритм, когда вы найдете то, что вам нужно - что в вашем случае было бы, когда алгоритм нашел кратчайший путь к каждому узлу на пути.

Я не знаю конкретного "алгоритм "кратчайший путь от узла к пути".

...