Hi. I need some help: I need to check if a line intersects another line. However, there are some special things about my algorithm: I have some arbitray line and need to check it against two lines and see which one it collides with. I am guarateed that my arbitray line will intersect with one and only one of the two lines. Also, of the two lines, one is always horizontal and one is always vertical. Also, the horizontal and vertical line will always form the corner of a square. So here is what I have so far: 1. Check the start and end point of the arbitray line and if they are both within the vertical boundaries of the vertical line, then it must intersect the vertical line and not the horizontal line. 2. Same check as #1 except on the x axis and against the horizontal line. 3. Here is where I am stuck. Anyone have any ideas here on how to find out which line (vertical or horizontal) my arbitray line intersects with? One more thing, once I find which line (vertical or horizontal) my arbitray line intersects with, I can very easily find the exact intersection, so don''t worry about that. I just need to figure out how to tell which line I have intersected with. Any help is greatly appreciated! Thanks!

k.... not sure exactly what you''re trying to do... but in general... mathamagically... to determine the x value where two unbounded lines intersect... I''ll do the math here since I can''t find the book where its writen down

for the first line   y=m1x+b1for the second line   y=m2x+b2when both lines intersect the x and y values for both equations will be equal... so  m1x+b1=m2x+b2then solving for x we get   m1x-m2x=b2-b1   (m1-m2)x=b2-b1   x=(b2-b1)/(m1-m2) 

using that and your lines you already have you should be able to figure out which line(s) it instersects with and where it does intersect with them...

http://astronomy.swin.edu.au/~pbourke/geometry/lineline3d/

// return: 0 if parallel; 1 if coincident; 2 if generic
int LineLineClosestPoints3d (D3DVECTOR *pA,D3DVECTOR *pB,D3DVECTOR a,D3DVECTOR a2,D3DVECTOR b,D3DVECTOR b2)
{
D3DVECTOR Cdir;
Plane_Struct Ac, Bc;

Cdir = CrossProduct(a2-a,b2-b);

if ( Magnitude(Cdir)==0)
{
*pA = a; // all points are closest
*pB = b;
return 0; // degenerate: lines parallel
}

Ac.ComputePlane(a,a2,a+Cdir);//compute a plane from 3 vector
Bc.ComputePlane(b,b2,b+Cdir);

*pA = Bc.LineIntersect(a,a2);//return plane-line intersect point
*pB = Ac.LineIntersect(b,b2);

return 1;
}


[edited by - Fantasio on February 17, 2003 9:41:37 PM]

in 2D, lines will always intersect unless they''re parallel.
in 3D, you''d have to solve the three linear equations to see if they intersect.

quote:

---

Original post by bpj1138
in 2D, lines will always intersect unless they''re parallel.
in 3D, you''d have to solve the three linear equations to see if they intersect.

---

Actually, in 3D, lines will only intersect if they are coplanar, which reduces the problem to 2 dimensions even for 3D lines (since you can create a 2D coordinate system in the common plane and then solve the 2D intersection problem), .

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Awsome! Thanks guys.

quote:

---

Original post by grhodes_at_work
Actually, in 3D, lines will only intersect if they are coplanar, which reduces the problem to 2 dimensions even for 3D lines (since you can create a 2D coordinate system in the common plane and then solve the 2D intersection problem), .

---

How do you know if they are coplanar or not? AFAIK, You have to find their normal using the cross product, which is itself the determinant of a 3x3 matrix, so you might as well solve the three linear equations directly...

First line:

x = x0 + at
y = y0 + bt
z = z0 + ct

Second line

x = x1 + ds
y = y1 + es
z = z1 + fs

From the x equations:
x0 + at = x1 + ds
=> s = (x0 + at - x1) / d

By replacing s into the other equations ("y = y" and "z = z"), you can find t. If the t that you find with the y equation is the same as the t from the z equations, there is an intersection.

Cédric

quote:

---

Original post by cedricl
How do you know if they are coplanar or not? AFAIK, You have to find their normal using the cross product, which is itself the determinant of a 3x3 matrix, so you might as well solve the three linear equations directly...

---

You are correct to say that to explicitly find if the two lines are coplanar requires finding a cross product; however, you actually do not have to test to see if they are coplanar directly. In fact, you don''t want to because you''ll end up dealing with more special cases (is n.x = 0, or n.y = 0, etc.). if you work out the math (hand waving), you can actually derive a 2x2 problem for the general 3D case, and there is a closed form solution to the 2x2 problem that is quite simple and fast. (There''s added logic if you want to check to see if to finite-length line segments intersect, but for infinite lines its very simple.) Now, to annoy you or anger, you I will not be posting this solution. For two reasons. One, I just don''t have time to dig it out (even answering the occasional post is sometimes requiring time I don''t have). And, second, the solution is published in a chapter I wrote for "Game Programming Gems 2," along with working source code and a full derivation. If you have a copy of the book, see that chapter. If you do not have the book, either buy a copy (I''ll get about 1 penny in royalties, yeah!) or skim the chapter at your local bookstore if you can (Borders and Barnes & Noble typically stock this book).

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Well, the derivation I gave looks pretty fast to me... I wish that I had the time to tackle your problem, but there is some special relativity waiting for me on my desk...

Maybe next summer

Cédric