distance la plus courte entre le point et le chemin

Question

pour un jeu en ligne basé sur la géo-je suis à la recherche d'un algorithme qui trouve la plus courte distance entre un point spécifié et un chemin connu relié par x / y coordonnées, afin que je puisse tuer tous les points redondants / nœuds. Un lien ou un mot clé pour cet algorithme me aiderait beaucoup! merci pour la lecture

Pour une meilleure compréhension:

Answer 1

Êtes-vous désireux de calculer cela pour dire quelque chose comme « si la distance point à chemin est égal à zéro, puis retirez le point »? Si oui, alors il y a probablement un moyen de supprimer des nœuds redondants plus facile. Prendre des points trois à la fois (les appeler A, B et C). Calculer l'angle entre A et B, ainsi que l'angle entre B et C. Si les deux angles sont les mêmes, alors le point B se trouve dans le chemin entre A et C et est redondant. Vous pouvez utiliser pour faire les calculs d'angle de la fonction « atan2 » (ou l'équivalent de votre langue).

Answer 2

Ceci est un algorithme chemin d'enquête point à point qui est couramment utilisé dans les jeux:

A * algorithme de recherche

Vous devrez peut-être appliquer un certain nombre de fois entre votre point et le chemin, mais il est généralement très rapide. L'algorithme a des optimisations pour les grilles de la carte (où les distances entre les carrés sont des nombres entiers). Il y a une description de ce à: temps réel jeu de stratégie de programmation en utilisant MS DirectX 6.0 par Mickey Kawick.

algorithme de Djikstra est un bon algorithme chemin de découverte objectif général à partir d'une seule source noeud à tous les autres noeuds dans le graphe. Vous pouvez arrêter l'algorithme lorsque vous avez trouvé ce que vous avez besoin -. Qui dans votre cas serait lorsque l'algorithme avait trouvé le chemin le plus court à chaque noeud sur le chemin

Je ne sais pas d'un « chemin le plus court de noeud à chemin » spécifique algorithme.

Answer 3

Ceci est mon implémentation de Java pour le point le plus proche sur un chemin

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