Distanza più breve tra il punto e il percorso

Question

per un gioco on-line geo-based Sto cercando un algoritmo che trova la distanza più breve tra un punto specificato e un percorso noto collegati da x / y coordinate, in modo che possa uccidere tutti ridondanti punti / nodi. Un link o parola chiave per questo algoritmo mi avrebbe aiutato un sacco! grazie per la lettura

Per una migliore comprensione:

Answer 1

Sei voler calcolare questo per dire qualcosa come "se la distanza punto-a-percorso è pari a zero, quindi rimuovere il punto"? Se è così, allora non v'è probabilmente un modo più semplice per rimuovere i nodi ridondanti. Prendere i punti di tre alla volta (chiamarli A, B, e C). Calcolare l'angolo tra A e B, così come l'angolo tra B e C. Se i due angoli sono uguali, risiede punto B nel percorso tra A e C ed è ridondante. È possibile utilizzare la funzione 'atan2' (o della vostra lingua equivalente) per fare i calcoli angolari.

Answer 2

Questo è un algoritmo di percorso conoscitiva point-to-point che viene comunemente utilizzato nei giochi:

A * algoritmo di ricerca

Potrebbe essere necessario applicare un certo numero di volte tra il punto e il percorso, ma in generale è molto veloce. L'algoritmo ha alcune ottimizzazioni per mappa griglie (dove le distanze fra i quadrati sono interi). C'è una descrizione di questo in: Real-Time Strategy Game Programming utilizzando MS DirectX 6.0 da Mickey Kawick.

algoritmo di Djikstra è un buon uso generale algoritmo percorso di accertamento da un'unica fonte nodo a tutti gli altri nodi del grafo. È possibile interrompere l'algoritmo quando hai trovato quello che vi serve -. Che nel tuo caso sarebbe quando l'algoritmo aveva trovato il percorso più breve per ogni nodo sul percorso

Non so di uno specifico "percorso più breve dal nodo al percorso" algoritmo.

Answer 3

Questa è la mia implementazione Java per il punto più vicino su un percorso

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