Jump to content
  • Advertisement

Archived

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

Axiverse

Calculating nearest point from a point & line

This topic is 5320 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

How do you find the nearest point on a line from another point. From what i think, the line connecting the source point to the nearedt point on the line should be perpendicular...

Share this post


Link to post
Share on other sites
Advertisement
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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!