Calculation of the distance to the path

Question

I have a set of points that form a path. I would like to determine the minimum distance from any point to this path. The path might look something like this:

points = [ [50, 58], [53, 67], [59, 82], [64, 75], [75, 73] ]; 

where the first value is the x coordinate, and the second is the y coordinate. The path is open (it does not form a closed loop) and consists of straight segments between points.

So, given the point, for example. [90, 84] how to calculate the shortest distance from this point to the path?

I'm not necessarily looking for a complete solution, but any pointers and ideas will be appreciated.

Answer 1

It is possible to construct pathological cases in which the nearest line segment to the point P connects two points that are further from P than any other points on the path. Therefore, if I am missing something very thin, you must calculate the distance to each segment of the line to get the shortest distance to the path.

Here is a simple example:

 (5,1)-(4,2)-(1,3)-(20,3)-(15,2)-(14,1) 

For a given point (10.1), the closest distance to the path will be equal to the point (10.3), which is located along the line segment (1.3) - (20.3), but these two points are further from (10.1) than any other waypoint.

Therefore, I do not believe that there are shortcuts to the naive algorithm for finding the distance to each segment of the line and making a minimum.

Answer 2

The distance between a point and a line is defined as follows:

d = | (x_2 - x_1) (y_1 - y_0) - (x_1 - x_0) (y_2 - y_1) | / sqrt ((x_2 - x_1) ^ 2 - (y_2 - y_1) ^ 2),

which is an extension of the point product, where (x_0, y_0) are the coordinates of the point, and (x_1, y_1) and (x_2, y_2) are the end points of the line.

It would be quite simple to calculate this for each set of points, and then just determine which one is the lowest. I am not convinced that there is no more elegant way to do this, but I do not know about it. Although I would like to see someone here answers alone!

Edit: Sorry, the math here looks so messy without formatting. Here the image of what this equation looks like is beautifully executed:

Point in a line! http://mathworld.wolfram.com/images/equations/Point-LineDistance2-Dimensional/NumberedEquation8.gif

Another edit: as Chris noted in his post, this does not work if the points are in a row, i.e. if the line is defined (0,0) - (0,1), and the point is (0,10). As he explains, you need to check to make sure that the point in question is not actually on the “extended path” of the line itself. If so, then this is simply the distance between the closest endpoint and the point. All loans to Chris!

Answer 3

The distance from point C to segment AB is the area of ​​parallelogram ABCC '.

Answer 4

So, I only talk about it for a second. erekalper has already placed the distance between the point and the line. However, the problem with this formula is that it assumes that the line is of infinite length, which is not the case with your problem. Just an example of a problem: suppose a simple line goes from (0,0) to (0,1) and a point with coordinates (0,10). The formula laid out above will return o the distance 0, because if you expand the line, it will hit the point. Unfortunately, in your case, the line ends with (0,1), so the distance is actually 9.

So my algorithm would be: check if the angles at the ends of your lines are <= 90 °. If so, the shortest distance for this path will be calculated using an already published formula. If not, the shortest distance is the distance to one of the end points. Do it for all parts of the path, choose the minimum

Answer 5

It would be best to find the nearest point from the line (make a path), measure the distance and move along the path (and save the point for the shortest distance).

Answer 6

You need to use linear algebra (trembling) to calculate the distance from a point to each row.

Here is a link to an article describing math: http://mathforum.org/library/drmath/view/55501.html

And here is a pretty good library . You need to look at methods called PointSegmentDistance . A segment appears to be a line that starts at one point and ends at a second point, while a line has two points, but continues at infinity.

Answer 7

First you need to find out the shortest distance to each line segment, and then choose the smallest distance. When you calculate the shortest distance, you need to find out the closest point in the line segment. If the closest point is not between the start and end points, you should use the distance to the start or end point (depending on which of the nearest points).

This page contains some formulas that you are likely to need.