Point on a line nearest to another line
Author
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( );
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...
).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...
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.
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]
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]
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.
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
Ok, yeah, the statement was correct. I ignored the shortest part and I forgot that the zero vector is orthogonal to everything.
Author
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( );
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( );
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.
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.
Author
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( );
~CGameProgrammer( );
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
