Point on a line closest to x,y

Question

Possible Duplicate:
How can I tell if a point is nearby a certain line?

//Returns the point on the line traced from start to end which
//comes nearest to 500,000, 500,000. The points are scaled between
//1,000,000 and 0 from their original fp types.
Point closestToCentre(Point start, Point end);

Anyone know of quicker way than single stepping through the pixels?

Could some one more alert than me demonstrate their maths & geometry prowess please?

_______EDIT___________

Thanks Kris, this was confusing me :

[x; -a/bx-c/b]=[0; -c/b]-1/b[-b; a]x.

Now I see it is just splitting (mainly the y component) the vector into two which combine to yield the same result. Got the old partial fractions brain cell excited for a minute then :)

_______EDIT_________

Jason Moore, thanks for the inspiration, here is what I am doing, graphically,

I hope that is clearer.

____EDIT________

So I could reasonably expect to take a line at right angles to my sampled line and run it from the centre but how to tell when they touch?

I think Kris's page of equations is the way to go. If you're all telling me it is a two step process. It is just two simultaneous equations now, so I may not need Kris's derivations.

____EDIT_________

Whether good or bad thing, I don't know, but the beauty of stackoverflow as a search engine has revealed to me several routes of investigation. Chiefly I like the first solution here: Shortest distance between a point and a line segment.

But to prove this to my self I needed the link from matti's solution at the bottom (but one):

http://www.topcoder.com/tc?d1=tutorials&d2=geometry1&module=Static

The derivation is so simple and elegant even I could follow it!

Given http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html

Answer 1

This is a matter of linear projection of a point onto a line, which can be done with some fine vector gymnastics, as elaborated at MathWorld.

The article details how to find the shortest distance from a point to a line, and one of the intermediate steps is finding the perpendicular line from the point x,y to the original line. Intersecting these two lines will give you the point, on the line, closest to x,y.

Edit in response to comment: What equation (2) in the link is doing is transforming the vector into a form reminiscent of y = mx + c, which allows you to quickly and easily read off the gradient, from which the perpendicular gradient can be easily calculated.

Answer 2

I think the quickest way will be a two step process:

1. Assume your line is infinite in length, and find the intersection of your line and its perpendicular bisector through (500,000, 500,000).
2. Make sure that point is actually on your line, else find the closest endpoint.

Kris's post covers step 1 pretty well, all you have to do is add the check for step 2 because you have a line segment and you're golden.

Let point 1 = (x1, y1) and endpoint 2 = (x2, y2). Then the line containing these two points is

y = (y2 - y1)/(x2 - x1) * (x - x1) + y1

and the perp. bisector through (5e5, 5e5) is

y = (x1 - x2)/(y1 - y2) * (x - 5e5) + 5e5

Your point (x,y) is the solution (x,y) to the above two equations (or one of the two endpoints). This might be more straightforward than the mathworld link. Note that this solution fails, however, when your line is either almost vertical or almost horizontal whereas I don't think the mathworld solution style does, though I haven't looked very closely.