Distancia más corta entre el punto y la ruta

Question

Para un juego en línea basado en geografía, estoy buscando un algoritmo que encuentre la distancia más corta entre un punto específico y una ruta conocida conectada por coordenadas x/y, de modo que pueda eliminar todos los puntos/nodos redundantes.¡Un enlace o palabra clave para este algoritmo me ayudaría mucho!gracias por leer

Para un mejor entendimiento:

Answer 1

¿Usted está queriendo para calcular esto para decir algo como "si la distancia de punto a ruta es cero, a continuación, quitar el punto"? Si es así, entonces es probable que haya una manera más fácil para eliminar nodos redundantes. Tomar los puntos de tres en tres (llamarlos A, B y C). Calcular el ángulo entre A y B, así como el ángulo entre B y C. Si los dos ángulos son iguales, entonces mentiras punto B en la trayectoria entre A y C y es redundante. Puede utilizar la función 'atan2' (o de su frase equivalente) para hacer los cálculos angulares.

Answer 2

Este es un algoritmo de búsqueda de ruta punto a punto que se usa comúnmente en juegos:

Un* algoritmo de búsqueda

Es posible que tengas que aplicarlo varias veces entre el punto y la ruta, pero generalmente es muy rápido.El algoritmo tiene algunas optimizaciones para las cuadrículas de mapas (donde las distancias entre cuadrados son números enteros).Hay una descripción de esto en: Programación de juegos de estrategia en tiempo real utilizando MS DirectX 6.0 por Mickey Kawick.

algoritmo de Djikstra es un buen algoritmo de búsqueda de rutas de propósito general desde un único nodo fuente hasta todos los demás nodos del gráfico.Puede detener el algoritmo cuando haya encontrado lo que necesita, lo que en su caso sería cuando el algoritmo haya encontrado la ruta más corta a cada nodo en la ruta.

No conozco un algoritmo específico de "ruta más corta de nodo a ruta".

Answer 3

Esta es mi aplicación Java para el punto más cercano en un camino

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;
}