Kürzester Abstand zwischen dem Punkt und dem Pfad

Question

für ein geo-basierte Online-Spiel, das ich bin auf der Suche für einen Algorithmus, den den kürzesten Abstand zwischen einem bestimmten Punkt und einem bekannten Pfad von x / y-Koordinaten verbunden findet, so dass ich all redundanten Punkte / Knoten töten. Ein Link oder ein Schlüsselwort für diesen Algorithmus würde mir sehr helfen! Dank für das Lesen

Zum besseren Verständnis:

Answer 1

Wollen Sie, diese zu berechnen, um etwas zu sagen, wie „wenn der Punkt-zu-Bahnweg Null ist, dann den Punkt entfernen“? Wenn ja, dann ist es wahrscheinlich ein einfacher Weg, redundanten Knoten zu entfernen. Nehmen Sie die Punkte drei auf einmal (nennen wir sie A, B und C). Berechnen des Winkels zwischen A und B, sowie den Winkel zwischen B und C. Wenn die beiden Winkel die gleichen, dann B Punkt liegt in dem Weg zwischen A und C sind und redundant ist. Sie können die ‚atan2‘ -Funktion (oder Ihre Sprache Äquivalent) die Winkelberechnungen zu tun.

Answer 2

Dies ist ein Punkt-zu-Punkt Wegfindungsalgorithmus, die häufig in Spielen verwendet wird:

A * -Algorithmus

Möglicherweise müssen sie einige Male zwischen Punkt und den Pfad gelten, aber es ist in der Regel sehr schnell. Der Algorithmus hat einige Optimierungen für die Kartengitter (wo die Abstände zwischen Quadraten sind ganze Zahlen). Es gibt eine Beschreibung dieses in: Echtzeit-Strategiespiel Programmierung mit MS DirectX 6.0 von Mickey Kawick.

Djikstra Algorithmus ein guter Allzweck-Weg zu finden, ist Algorithmus aus einer Hand Knoten zu allen anderen Knoten in dem graph. Sie können den Algorithmus stoppen, wenn Sie gefunden haben, was Sie brauchen -. Die in Ihrem Fall wäre, wenn der Algorithmus den kürzesten Weg zu jedem Knoten auf dem Weg gefunden hatte,

Ich weiß nicht, von einem bestimmten „kürzestem Weg von Knoten zu Pfad“ -Algorithmus.

Answer 3

Dies ist meine Java-Implementierung für den nächsten Punkt auf einem Pfad

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