The mind is willing but the math is weak

October 6, 2008 12:41 PM

Long Forgotten Mathfilter: I have a point and a line segment in 2d space. How do I find the closest point on the line to the point?

Say that I have a line segment going from 0,0 to 20,100. And I have a point at... say 70,30. What coordinates on the line are closest to that point?

Great appreciation to anyone who keeps it simple and shows their work since my math skills have degraded to the point where I can just about calculate a tip. (Depending on how much wine is on the bill.)

posted by Ookseer to science & nature (13 comments total)

You can do it with a compass (pair of compasses) by drawing an arc from the point to intersect the line in two places.
Mark the halfway point on the chord, and join to the first point.
posted by weapons-grade pandemonium at 12:56 PM on October 6, 2008

First Google hit for closest point line.
posted by DevilsAdvocate at 12:57 PM on October 6, 2008

The line segment that connects the point to the other line segment will be the shortest line, and therefore the point on the line that is closest to the other point.

y=mx+b where m is the slope and b is the y-intercept, that is, where the line crosses the y-axis.

You have two points, and you know due to the point (0,0) that the y-intercept is 0. So your equation is 100=m(20). Solve for m and you get the slope, in this case 5.

So the line segment's equation is y=5x. Now to find the perpendicular line. The slope of a perpendicular line is the negative reciprocal of the first line's slope. In this case, it's -1/5. We know the line goes through (70,30) so we can use those values to find the second line's y-intercept.

30= -(1/5)(70)+b
30= -14+b
44=b
y= -(1/5)x+44

Now, to find the point, you simply find where the two equations meet. You substitute one equation for y in the other:

-(1/5)x+44=5x
44=5x+(1/5)x=(26/5)x then multiply both sides by 5...
220=26x
36 and 2/3 = x

Finally, you plug in that x value to get the y value.

y=5(36.67)
y=183.33

And you end up with the point (36.67,183.33), assuming we're rounding to the nearest hundredth.
posted by papayaninja at 1:03 PM on October 6, 2008

To help put words on the solution in DevilsAdvocate's link, imagine drawing a line that's perpendicular to your original one. Slide it up or down your orginal line (keeping it perpendicular) until it hits your extra point. The place where it intersects the original line is the nearest point. All the math is to give you those coordinates.
posted by vytae at 1:04 PM on October 6, 2008

Disregard everything in my above post after "220=26x."
When you solve for that without screwing up somehow like I did, you get x=8.46 (again, rounding...) THEN you solve for y with that value.

y=5(8.46)
y=42.3

And your point is (8.46,42.3).
posted by papayaninja at 1:10 PM on October 6, 2008

I know I'm repeating what other people have written, but I just spend ten minutes typing it, so you can jolly well read it anyway...

The formula for the line segment is y=5x.

To find the closest point on the line to some arbitrary point, you need to construct another line, perpendicular to the first, passing through that point. Draw it and you'll see what I mean.

The slope of this line will be 5. The slope of the perpendicular line will therefore be -1/5, because the slope of a perpendicular line is -1 divided by the slope of the original line.

Therefore the formula for the perpendicular line is y=(-1/5)x+c (general formula for any 2d line segment is y=mx+c, where m is the slope and c is the y-position where the line crosses the axis).

Putting in your value of (70,30), we get 30=(-1/5)x70 + c, or c=44. So that gives us an equation for the perpendicular line of y=(-1/5)x + 44, or y=-0.2x + 44

Now all you need to do is to find the point where the two lines cross. At this point, the y coordinate will be the same for both lines, so we can write:

5x = -0.2x + 44. Adding 0.2x to each side (basic algebra) gives us:
5.2x = 44, or x=8.46.

Plug this value of x into the first equation to get y=5*8.46, or y=42.3

So the coordinates of the nearest point are (8.46, 42.3)
posted by le morte de bea arthur at 1:11 PM on October 6, 2008

The above answers seem to ignore that you said it's a line segment. For that, you need to compute the value they've described, and also the distance from the point to the end points of the line segment. Then the one of the three which is the closest is what you seek. In case you don't know how to compute the distance, the distance between (70, 30) and (20, 100), for instance is √((70-20)²+(100-30)²)≅86.02. For (70,30) to (0,0), it's ≅76.16. The distance for the point computed by papyaninja is ≅62.76, so in this case the computation given above did yield the correct answer, but that wouldn't always be the case. (E.g. if the lone point were (22,110), the above computation would give back (22,110) again, but the closest point on the line segment is (20,100))
posted by Coventry at 1:25 PM on October 6, 2008

Coventry is right. You don't have to mess with the distance formula, however. When you find the intersection of the two line segments, if the point is higher than (100,20) or lower than (0,0) then you know the closest point to the lone point is (100,20) or (0,0) respectively. Also, mad props for the superscript 2s, Coventry.
posted by papayaninja at 2:13 PM on October 6, 2008

Remember that some of these algorithms will fall down and go boom when you deal with a vertical lines.
posted by sebastienbailard at 2:57 PM on October 6, 2008

In the usual xy-coordinates the shortest distance between any line and any point will be when a line joining the point to the original line is perpendicular to the original line. (This is similar to the "shortest distance between two points is a straight line" idea that most people are familiar with)

Call the original line y1=mx+b and call the point P at location (p,q).
Well that isn't much use to you since you only have two points on this y1, so if those two points are (g,h) and (i,j) (i.e. g=0, h=0 and i=20, j=100)
m=(j-h)/(i-g)
and b=h-m*g or b=j-m*i

For your case m=5, b=0

The second line will be y2=(-1/m)x+c in order to be perpendicular to the first.

After some more math, the gory details of which are not included you get your "closest point" (x,y)
x= (mq+p-mb)/(m^2+1)
y= mx+b

For your case you get: x=8.462 and y=42.307 (as did everyone else)

I hope this helps, and you can probably fire this off in Excel too if you have several cases that need solving.
posted by KevCed at 3:01 PM on October 6, 2008

Thanks for breaking it down for me into simple discreet steps so that is actually makes sense to me. I can now do this particular calculation for my self!

Although most of the answers gave a correct answer I'm marking papayaninja's answer as the best because he made a mistake the first time through. And given my recent trials at solving this question I have a soft spot for making mistakes. (And then fixing them.)
posted by Ookseer at 4:50 PM on October 6, 2008

It seems the question has already been answered, but if you're interested in how to generalize this to higher dimensions....

Let L be the line in question. Describe L by specifying a point P on L, and a direction, v. In other words, write L = P + tv, where t is a real number. Let Q be a point in the ambient space. Then PQ is a vector from P to Q. Let w be the projection of PQ onto L; it is given by w = (PQ dot v / |v|^2)v. Now, the point in question is P + w.
posted by metastability at 5:17 PM on October 6, 2008

There's no need to go through calculating the intermediate line. The distance (squared) between the point (xp,yp) and a point (y,x) on the line y=mx+b is:

s^2 = (x-xp)^2 + (y-yp)^2 ] = Sqrt[ (x-xp)^2 + (mx + b - yp)^2

We want to minimize this, which we do by setting the derivative equal to zero.

d(s^2)/dx = (x-xp) + m * (mx+b-yp) = x*(1+m^2) - (m*yp - m* b + xp) = 0
So:
x = (m*yp - m*b + xp) / (1+m^2) as above.
And of course, y = mx + b = (m^2 yp + m*xp + b) /(1+m^2), just like the others got.

Compare your calculated value of x to the x-coordinates of the endpoints of your line segment. If it's between them, this is your point. If it's to the left, then the left-most endpoint is the one you want, and vice-versa.

This method is easily extended to finding the closest point on some arbitrary curve y(x) and another point in space. The answer is found by solving (x-xp) + dy/dx*(y(x)-yp) = 0. Of course, with other curves, there can be more than one "closest" point.
posted by dsword at 5:45 PM on October 6, 2008