Line-Line intersection

Hey,

How can you tell if 2 lines overlaps eachother?

I have 4 points L1_1 L1_2 and L2_1 L2_2
which represents these 2 lines

And I know that they are in a straight line,
(Same direction and on the same plane)

So they can acually only be moving in 1D if you know what i mean.

Ive hurd that if you set them equal and solve for it you get the intersection point, but i dont get it.

Please help.

/regards P

Its actually for my Triangle VS Triangle intersection code i need this,

When the triangles crosses eachother planes I find the intersection lines of each triangle.

Now I just need to find out if these two lines overlaps eachother and where they do.

(btw, its 3D)

Thanks

[mm_freak]

You need collision detection, don't you? Here's my theoretical solution: Rotate all points of the two lines around, let's say, L1_1, so that the line (L1_1,L1_2) is horizontal, then you can easily (without an equation) calculate the parameter for the other line. I've tried it on a paper (it works), but never made code out of it. As soon as I've got things to work, I'll post it.


If you just need to know, _if_ there is a collision, just check, if the _new_ y coordinates of L2_1 and L2_2 are one <= y(L1_1) and the other >= y(L1_1).

Hi,

Thanks for the reply, but i think its easier then that, even tho I cant figure it out.

When two triangles collide their intersections are parallell to eachother
(co-planar?) which means that they are in the same direction, on the same plane, and also in a straight line. atleast one Line is facing the other.

So to figure out if they do collide you can create some IF statements to see if they intersects eachother. But that will not look to good I think, so perhaps theres a better solution for it. And I also need the Point of Intersection (or line segment of intersection)

for example. If my two lines are represented by 4 Points
A, B, C, D

Linesegment 1 = A to B
Linesegment 2 = C to D

Somewhere I saw that you could set them equal like:

A + T(B-A) = C + T(D-C)

And solve for T. But ive no idea how to.

/P

just make 2 parametric equasions for the lines, then solve for t.

Didnt I just say I didnt know how to?

You seems to know so maybe you can help me?

/tx

[neilw]

ok here goes -

you have two points per line so contruct two parametric equations

line 1- with points x1,y1 and x2,y2
x = (1-t)x1 + t*x2
y = (1-t)y1 + t*y2

line 2- with points x3,y3 and x4,y4
x' = (1-t')x3 + t'*x4
y' = (1-t')y4 + t'*y4


where t and t' are variables

now the point of intersection is where
x = x'
and
y = y'

so rearrange equations and solve simultaneously to find x and y

hope that a) helps b) works
been a while since i did that kinda maths

neilw

[urban debugger]

from Robert Sedgewick's algorithms:

int ccw(point p0, point p1, point p2)
{
int dx1,dy1,dy2;
dx1= p1.x - p0.x;
dy1= p1.y - p0.y;

dx2= p2.x - p0.x;
dy2= p2.y - p0.y;

if(dx1 * dy2 > dy1*dx2) return +1;
if(dx1 * dy2 < dy1*dx2) return -1;

if((dx1*dx2 < 0) &#0124; &#0124; (dy1*dy2 < 0))
return -1;
if((dx1*dx1+dy1*dy1) < (dx2*dx2+dy2*dy2))
return +1;

return 0;
}


int intersect(line l1, line l2)
{
return( (ccw(l1.p1, l1.p2, l2.p1)
*ccw(l1.p1, l1.p2, l2.p2)) <=0 )
&&((ccw(l2.p1, l2.p2, l1.p1)
*ccw(l2.p1, l2.p2, l1.p2)) <=0 )
}

Hey,

Thanks for answering, but...

neilw;

I can figure out so far
But how on earth can you solve it? Thats the question.

urban debugger:

As far as I can see that will only tell me if they intersect not where they do, or am i wrong?

/ tx.

[EPHERE]

This is a failsafe code, I use it all the time

E_Vertex is a structure with x,y,z coords
E_Line is a structure with two E_Vertex structures (for two points that define the line)

EPS is an epsilon value for the lowest non-zero real value (just do something like #define EPS 0.000000001)

///////////////////////////////////////////
E_Vertex TwoLine(E_Line a, E_Line b)
{
E_Vertex p13,p43,p21;
double d1343,d4321,d1321,d4343,d2121;
double numer,denom, mua, mub;
E_Vertex pa, pb;
E_Vertex error;
error.x=error.y=error.z=-0.69f;

p13.x = a.a.x - b.a.x;
p13.y = a.a.y - b.a.y;
p13.z = a.a.z - b.a.z;
p43.x = b.b.x - b.a.x;
p43.y = b.b.y - b.a.y;
p43.z = b.b.z - b.a.z;
// if (abs((int)(p43.x)) < EPS && abs((int)(p43.y)) < EPS && abs((int)(p43.z)) < EPS)
// return error;
p21.x = a.b.x - a.a.x;
p21.y = a.b.y - a.a.y;
p21.z = a.b.z - a.a.z;
// if (abs((int)(p21.x)) < EPS && abs((int)(p21.y)) < EPS && abs((int)(p21.z)) < EPS)
// return error;

d1343 = p13.x * p43.x + p13.y * p43.y + p13.z * p43.z;
d4321 = p43.x * p21.x + p43.y * p21.y + p43.z * p21.z;
d1321 = p13.x * p21.x + p13.y * p21.y + p13.z * p21.z;
d4343 = p43.x * p43.x + p43.y * p43.y + p43.z * p43.z;
d2121 = p21.x * p21.x + p21.y * p21.y + p21.z * p21.z;

denom = d2121 * d4343 - d4321 * d4321;
if (denom == 0)
return error;
numer = d1343 * d4321 - d1321 * d4343;

mua = numer / denom;
mub = (d1343 + d4321 * (mua)) / d4343;

pa.x = (GLfloat)(a.a.x + mua * p21.x);
pa.y = (GLfloat)(a.a.y + mua * p21.y);
pa.z = (GLfloat)(a.a.z + mua * p21.z);
pb.x = (GLfloat)(b.a.x + mub * p43.x);
pb.y = (GLfloat)(b.a.y + mub * p43.y);
pb.z = (GLfloat)(b.a.z + mub * p43.z);

if (pa.Dist(pb)<0.3f)
return(pa);
else
return error;
}
/////////////////////////////////////////

Returns the point of intersection E_Vertex structure if lines intersect and an error E_Vertex structure (-0.69,-0.69,-0.69) is they don't... you can modify it to return a boolean.

pa.Dist(pb)<0.3f tests the closest distance between the two lines. In this case if the distance is less than 0.3f then the lines intersect, otherwise they don't.


Hope this helps,
good luck