Archived

This topic is now archived and is closed to further replies.

Calculating nearest point from a point & line

This topic is 5011 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Say the line is defined by two points A and B and the third point (the one which you want to find the closest point on the line to) is C.

Construct a vector:
Vc = C-A

and another vector:
Vl = B-A

Then project Vc onto Vl. So the final answer is:

closest point = ((dot(Vc, Vl) * Vl) / |Vl|) + A

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
say you have a line 2x+y=3 and a point (2,3). the first thing you need to do is find the equation of the line that is perpendicular to the line give. in this case the perpendicular line is x-2y=-3. now just plug your point in to create a new line and you get x-2y=-4. find the point of intersection of the original line and the created perpendicular line and you get an answer of (2/5,11/5). hope this helps and hope i did it correctly.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Heres how to think about this, but easier to discuss in if instead of a line in 2D, you consider a plane in 3D.


The plane has a surface perpendicular (aka normal) and it is pretty obvious that a point (P1) not on the plane is closest along the (possibly opposite) direction of this normal. That is, if you were to draw a ray from the point (P1) to the closet spot on the plane (P2) the rays direction vector would precisely match the angle of the surface normal.

Once you''ve reduced the problem to this concept, you see that all you are doing is intersection a ray (with the origin of P1 and an angle matching the surface normal of the plane) with the plane itself.

Back to the 2D case, the line has perpendicular precisely 90 degrees from its direction.. the task is to intersect a ray starting at the point (P1) with a direction equal (or opposite) to the perpendicular of the line with the line itself..

So get on google and search for ''line intersection''

Share this post


Link to post
Share on other sites
Sounds complex...

I''ve come up with this:

Function lineDot(ByVal line1 As Vector3, ByVal line2 As Vector3, ByVal point As Vector3) As Vector3
Dim v As Vector3 = Vector3.Subtract(line1, line2)
Dim m As Matrix = Matrix.RotationAxis(v, System.Math.PI)
Dim p As Vector4 = Vector3.Transform(point, m)
Return New Vector3((p.X + point.X) / 2 + line2.X, (p.Y + point.Y) / 2 + line2.Y, (p.Z + point.Z) / 2 + line2.Z)
End Function

from the limited testing i''ve done it works, but could it be faster with quaternions? (I don''t know how to use quaternons)

it simply rotates the point around the line at 90 degrees and averages the two: (it works)

plz put any ideas to optimize this...

Share this post


Link to post
Share on other sites
If you want an optimal method, take another look at my original post. It’s really not that complicated.

Constructing a rotation matrix as you’ve done is going to be relatively expensive (use of trig functions).

I’ll state it one more time in the syntax I think you’re using (Visual Basic?):

Dim Vline as Vector3 = Vector3.Subtract(line1, line2);
Dim Vpoint as Vector3 = Vector3.Subtract(point, line2);
Vline = Vector3.Normalize(Vline);
return line2 + Vector3.DotProduct(Vline, Vpoint) * Vline;

or an even slightly more efficient method that removes the square root incurred by the normalize function:

Dim Vline as Vector3 = Vector3.Subtract(line1, line2);
Dim Vpoint as Vector3 = Vector3.Subtract(point, line2);
return line2 + Vector3.DotProduct(Vline, Vpoint) * Vline / Vector3.DotProduct(Vline, Vline);

Share this post


Link to post
Share on other sites
well, i''m waiting to c#, but for right now i''m still using vb and vb doesn''t support overloaded opperators...

so tour return makes no sence to the compiler (or me)

coule you tell me whar each symbol is?
:
Vector.Dot(Vector3, Vector3) returns a single which cannot be multiplied by a vector3 (is this scale?)

Vector3 can''t be added to a single

nor division

Share this post


Link to post
Share on other sites
I think you’ll find c# a very friendly language to work in.
Here are the symbols I used:
+ Add
* Multiply
/ Divide

Vector3.Dot() returns the dot product of two vectors which is a scalar.
Multiplying (or dividing) a vector with a scalar means multiplying each component of the vector with the scalar and the result is a vector.

Share this post


Link to post
Share on other sites
An easy to visualize way of doing it is this without having to think in angles..

I am assuming you mean segment instead of line. The line is made up of 2 points. pointA and pointB. The point you are testing we''ll call pointC.

Pretend the line is the normal to a plane (normalize it to). First, lets get rid of the D in the plane equation by subtracting pointB from pointC.

Now we have a point and a plane at the origin. A dot product with the normal and the point will give you the distance the point is from the plane.

Since you know the distance now, you can start at pointB and just drive in the direction of the normal that distance. Where you end up will be the nearest point to pointC.

or in pseudo code.

normal=normalize(pointA-pointB);
tempPoint=pointC-pointB;
dist=dot(normal,tempPoint);
nearest=pointB+dist*normal;

you can also do this without normalizing, but that''ll hide some of the intuitiveness.

Share this post


Link to post
Share on other sites