Jump to content
  • Advertisement

Archived

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

CGameProgrammer

Point on a line nearest to another line

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

Yet another math-related question from me. I''m making great progress with my collision, the only thing remaining is edges. For this I need to find the point on a line nearest to another line. I already have the formula for the distance between them, if the website was correct then it is this: CrossProduct = LineA.Direction cross LineB.Direction; if( CrossProduct != vector(0,0,0) ) return (LineA.Endpoint - LineB.Endpoint) dot CrossProduct; else // They are parallel return LineA.Distance( LineB.Endpoint ); That last bit calls the function that finds the distance from a line to a point. Anyway now I need to find the point on LineA that is nearest to LineB. If I have this point then I will be set because I can use my line-point equations with it. ~CGameProgrammer( );

Share this post


Link to post
Share on other sites
Advertisement
Well, I have an idea. You know how if you want to project a 3D point into 2D you simply "eliminate" one of the axis? Let''s apply that concept to our lines. In effect, by removing the Z, you are also saying that there exists a point (0,0,Z) (Z being any non-zero number) where the observer is, and he is facing towards (0,0,0), and we are projecting the points/lines to his view. If we apply this same concept to our lines, then we could project them to 2D based on an imaginary observer, find the intersection there, and then translate that point back into 3D for both lines, and that would correspond to the closest points for both lines (at least, if my theory is correct ).

So for our lines, let''s say that they produce cross-product (X,Y,Z). Now let''s say that there''s an observer at that point, and he''s looking towards the origin. We can project the lines into his view, but instead of just hacking the Z, we have to use some projection math. I''m not an expert on that, so you''d have to go looking around.

Tell me if you get anywhere with this I really just thought of it...

Share this post


Link to post
Share on other sites
Well, in the parallel case it is any point. What the first part does is find the distance between two planes. If it is non-zero then the lines are skew, i.e. the lines are in differant planes. As near as I can tell you have to project one line into the plane of the other line and then find the point of intersection. The CrossProduct is a vector normal to both planes so you simply use it to translate one of the end points.

Share this post


Link to post
Share on other sites
A Google search would surely return good results for this.

I think that I have a reasonably good method. Given two lines A and B,

1. The shortest distance between line A and line B is along the vector perpendicular to both of these lines.

N = VectorA X VectorB

2. Make a plane that contains any point on the line B, and whose normal is N X VectorB

3. Intersect this plane with line A. This point should be the closest point to line B

It should work...

Cédric

[edited by - cedricl on November 3, 2002 3:03:32 PM]

Share this post


Link to post
Share on other sites
A vector perpendicular to two non-parallel lines in the same plane is orthogonal to the plane they are in. I''m not arguing with the method, just the first statement.

Share this post


Link to post
Share on other sites
quote:
Original post by LilBudyWizer
A vector perpendicular to two non-parallel lines in the same plane is orthogonal to the plane they are in.

Yes... If the two lines are in the same plane, then their distance is 0, so they are separated by the vector 0 * N.

To find the distance between two lines, the usual technique is to use the vector perpendicular to both lines

N = Va X Vb

And to project the vector between any point on A, and any point on B onto it.

r = Pb - Pa

d = r . N / |N|

At least, that''s what I remember. So the vector N, perpendicular to both lines, is the direction one should take to get to line B if he was on the point closest to it, on line A. Does that make sense?

Cédric

Share this post


Link to post
Share on other sites
Thanks for the replies... I haven''t tested those suggestions yet but someone told me this should work:

CrossProduct = LineA.Direction cross LineB.Direction;
Length = (((LineB.Position - LineA.Position) cross LineB.Direction) dot CrossProduct) / (CrossProduct dot CrossProduct);
NearestPoint = LineA.Position + (LineA.Direction * Length);

Is that right? I''m working on implementing it, haven''t tested it yet, so I''m just asking here.

~CGameProgrammer( );

Share this post


Link to post
Share on other sites
I haven''t read anything except the title, but what I am to understand is that you want the point on a line closest to another point. So that means you have to measure the distance between 2 points twice.
deltax = x2-x1
deltay = y2-y1
deltax= deltax*deltax;
deltay= deltay*deltay;
dist = sqrt(deltax+deltay);

do this twice, one for the point on one side and another for a point on the other side. Whichever has the least distance wins.

Hope that helps and I haven''t restated something sum1 else said.

Share this post


Link to post
Share on other sites
No. I already knew how to find the point on a line nearest to another point. But finding the point on a line closest to another line is different. Plus I''m dealing with 3D stuff.

~CGameProgrammer( );

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!