Shortest distance between point and path

Question

for a geo-based online game I'm looking for an algorithm which finds the shortest distance between a specified point and a known path connected by x/y-coordinates, so that I can kill all redundant points/nodes. A link or keyword for this algorithm would help me a lot! thanks for reading

For better understanding: alt text

http://stackoverflow.com/questions/3032630/optimizing-simplifying-a-path did it. But with another approch. so solved — , Aug 31 '10 at 13:43

score 0 · Answer 1 · edited Feb 23 '16 at 17:42

This is my Java implementation for the nearest point on a path

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

By the way, if your "Point" is `java.awt.Point`, then `distance` and `distanceSq` are built-in methods. — wchargin, May 26 '13 at 04:04

richj · Answer 2 · 2010-08-31T13:00:11.037

-1

This is a point-to-point path-finding algorithm that is commonly used in games:

A* search algorithm

You might need to apply it a number of times between your point and path, but it is generally very fast. The algorithm has some optimizations for map grids (where the distances between squares are integers). There's a description of this in: Real-Time Strategy Game Programming using MS DirectX 6.0 by Mickey Kawick.

Djikstra's algorithm is a good general purpose path-finding algorithm from a single source node to all other nodes in the graph. You can stop the algorithm when you've found what you need - which in your case would be when the algorithm had found the shortest path to every node on the path.

I don't know of a specific "shortest path from node to path" algorithm.

edited Aug 31 '10 at 13:00

answered Aug 31 '10 at 12:44

richj

7,499
3
32
50

So if I unterstand the A* algorithm right, it finds the shortest way to another node. I intend to find the shortest distance even to the line between two nodes. For better unterstanding I added an image. Please correct me if I understand wrong. – Aug 31 '10 at 13:00
Yes - A* finds the shortest way to another node. For geometric distance the answer by bbadour is correct. – richj Aug 31 '10 at 13:05
The specified problem seems to be a mix of network path finding and geometric distance. However "so that I can kill all redundant points/nodes" implies that this is only part of a wider path-finding problem - possibly an optimization to the wider problem? – richj Aug 31 '10 at 13:09

score -1 · Accepted Answer · answered Aug 31 '10 at 18:00

Are you wanting to calculate this in order to say something like "if the point-to-path distance is zero, then remove the point"? If so, then there is probably an easier way to remove redundant nodes. Take the points three at a time (call them A, B, and C). Calculate the angle between A and B, as well as the angle between B and C. If the two angles are the same, then point B lies in the path between A and C and is redundant. You can use the 'atan2' function (or your language's equivalent) to do the angle calculations.

Shortest distance between point and path

3 Answers3

Linked