点与路径之间的最短距离

Question

我正在寻找一个与地理在线游戏相关的算法，该算法可以找出指定点与由x/y坐标连接的已知路径之间的最短距离，以便我可以消除所有冗余点/节点。如果有该算法的链接或关键字，将对我很有帮助！谢谢阅读。

为了更好地理解：

- user355318

---

使用另一种方法进行了优化简化路径。因此问题已解决。 - user355318

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

- Vitaliy Polchuk

---

顺便提一下，如果你的“Point”是java.awt.Point，那么distance和distanceSq是内置方法。 - wchargin

Answer 2

这是一种常用于游戏中的点对点路径查找算法：

A*搜索算法

你可能需要在你的点和路径之间多次应用它，但通常它非常快速。该算法针对地图网格（其中方块之间的距离为整数）进行了一些优化。Mickey Kawick 在 使用 MS DirectX 6.0 进行实时策略游戏编程 中有描述。

Djikstra 算法 是一种很好的通用路径查找算法，从单个源节点到图中所有其他节点。当你找到所需的内容时，可以停止算法 - 在你的情况下，这将是当算法找到路径上每个节点的最短路径时。

我不知道有特定的“从节点到路径的最短路径”算法。

- richj

---

如果我理解A*算法正确的话，它可以找到到另一个节点的最短路径。我想要找到甚至是在两个节点之间的直线上的最短距离。为了更好地理解，我添加了一张图片。如果我理解有误，请纠正我。 - user355318

是的 - A*算法可以找到到另一个节点的最短路径。对于几何距离，bbadour的答案是正确的。 - richj

指定的问题似乎是网络路径查找和几何距离的混合。然而，“以便我可以杀死所有冗余点/节点”意味着这只是更广泛的路径查找问题的一部分 - 可能是更广泛问题的优化？ - richj

Answer 3

你想计算这个是为了像“如果点到路径的距离为零，则删除该点”这样的目的吗？如果是这样，那么可能有一种更简单的方法来删除冗余节点。每次取三个点（称它们为A、B和C）。计算A和B之间的角度以及B和C之间的角度。如果两个角度相同，则点B位于A和C之间的路径上，并且是多余的。您可以使用“atan2”函数（或您所使用的语言的等效函数）进行角度计算。

- bta