CODEWITHSUNDEEP
mathlanguage-agnosticgeometry
Tatu Ulmanen
Tatu Ulmanen

Reputation: 124848

Calculating distance to a path

I have a set of points that form a path. I would like to determine the minimum distance from any given 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 the y coordinate. The path is open ended (it will not form a closed loop) and is made of straight segments between the points.

So, given a point, eg. [90, 84], how to calculate the shortest distance from that point to the path?

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

Upvotes: 7

Views: 3846

Answers (7)

Mikael Östberg
Mikael Östberg

Reputation: 17166

You need to use linear algebra (shivers) to calculate the distance from the point to each of the lines.

Here is a link to an article that describes the math: Link

And here is a pretty good library. You need to look at the methods called PointSegmentDistance. A segment is apparently a line that begins at one point and ends at the second point, whereas a line has two points but continue in infinity.

Upvotes: 0

erekalper
erekalper

Reputation: 887

The distance between a point and a line is given by:

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 expansion of the dot product, where (x_0, y_0) are the coordinates of the point, and (x_1, y_1) & (x_2, y_2) are the endpoints of the line.

It would be pretty simple to calculate this for each set of points, and then just determine which one is the lowest. I'm not unconvinced there's not a more elegant way to do so, but I'm not aware of it. Though I'd love to see if someone here answers with one!

Edit: Sorry that the math in here looks so messy without formatting. Here's an image of what this equation looks like, done nicely:

Point to line!
(from MathWorld - A Wolfram Web Resource: wolfram.com)

Another edit: As Chris pointed out in his post, this doesn't work if the points are in-line, i.e., if the line is defined by (0,0)-(0,1) and the point by (0,10). Like he explains, you need to check to make sure that the point being looked at isn't actually on the "extended path" of line itself. If it is, then it's just the distance between the closer endpoint and the point. All credit to Chris!

Upvotes: 1

S L
S L

Reputation: 14328

The best thing would be to find the closest point from a line (making the path) measure the distance and move on along the path (and store the point for shortest distance).

demo

Upvotes: 2

Jeffrey L Whitledge
Jeffrey L Whitledge

Reputation: 59523

It is possible to construct pathological cases in which the closest line segment to a point P connects two points which are themselves farther from P than any other points in the path. Therefore, unless I am missing something very subtle, you must calculate the distance to each line segment 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)

Given point (10,1), the closest distance to the path would be to the point (10,3), which is along the line segment (1,3)-(20,3), but those two points are farther from (10,1) than any other point in the path.

So I don't believe there are any shortcuts to the naïve algorithm of finding the distance to each line segment and taking the minimum.

Upvotes: 3

Chris
Chris

Reputation: 2060

So, I just though about it for a second. erekalper already posted the distance between a point and a line. However, the problem with this formula is that it assumes the line has infinite length, which is not the case for your problem. Just an example for the problem: Assume a simple line that goes from (0,0) to (0,1) and a point with coordinates (0,10). The formula posted above would return o distance of 0, because if you extend the line it would hit the point. Unfortunately, in your case the line ends at (0,1), thus the distance is actually 9.

Thus my algorithm would be: Check if the angles at the endpoints of your lines are <= 90°. If so, the shortest distance for this path will be computable by the formula already posted. If not, the shortest distance is the distance to one of the endpoints. Do this for all parts of the path, choose the minimum

Upvotes: 1

Judge Maygarden
Judge Maygarden

Reputation: 27603

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

Area of a Parallelogram

Upvotes: 1

mgronber
mgronber

Reputation: 3419

First you need to find out shortest distance to each line segment and then you choose the smallest distance. When you calculate the shortest distance, you need to find out the nearest point in the line segment. If the nearest point is not between the start and end point, you must use the distance to start or end point (whichever is the nearest).

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

Upvotes: 0

Related Questions