path - ポイントとパス間の最短距離

Question

地理ベースのオンラインゲームの場合、指定されたポイントとx / y座標で接続された既知のパスとの間の最短距離を見つけて、冗長なポイント/ノードをすべて削除できるアルゴリズムを探しています。このアルゴリズムのリンクまたはキーワードは私に大いに役立ちます！読んでくれてありがとう

理解を深めるために：

Answer 1

これは、パス上の最も近いポイントの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;
}

Answer 2

「ポイントからパスまでの距離がゼロの場合は、ポイントを削除する」などと言うために、これを計算しますか？もしそうなら、おそらく冗長ノードを削除するより簡単な方法があります。ポイントを一度に3つ取ります（、、、およびと呼びAますB）C。Aとの間の角度、およびとBの間の角度を計算しBますC。2つの角度が同じである場合、ポイントBはとの間のパスにAありC、冗長です。'atan2'関数（または言語に相当するもの）を使用して、角度の計算を行うことができます。

Answer 3

これは、ゲームで一般的に使用されるポイントツーポイントのパスファインディングアルゴリズムです。

A*検索アルゴリズム

ポイントとパスの間に何度も適用する必要があるかもしれませんが、一般的には非常に高速です。このアルゴリズムには、マップグリッド（正方形間の距離が整数）に対していくつかの最適化があります。これについては、MickeyKawickによるMSDirectX6.0を使用したリアルタイムストラテジーゲームプログラミングに説明があります。

ダイクストラのアルゴリズムは、単一のソースノードからグラフ内の他のすべてのノードへの優れた汎用パスファインディングアルゴリズムです。必要なものが見つかったら、アルゴリズムを停止できます。この場合、アルゴリズムがパス上のすべてのノードへの最短パスを見つけたときです。

特定の「ノードからパスへの最短パス」アルゴリズムがわかりません。