PDA

View Full Version : Line-Line intersection



11-09-2002, 11:58 PM
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

11-10-2002, 02:06 AM
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
11-10-2002, 10:34 AM
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.

http://freak32.dyndns.org/illustration1.jpg
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).

11-11-2002, 03:45 AM
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

11-11-2002, 09:17 AM
just make 2 parametric equasions for the lines, then solve for t.

11-11-2002, 08:25 PM
Didnt I just say I didnt know how to?

You seems to know so maybe you can help me?

/tx

neilw
11-12-2002, 01:30 AM
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 http://www.opengl.org/discussion_boards/ubb/biggrin.gif

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

neilw

urban debugger
11-12-2002, 01:51 AM
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 )
}

11-12-2002, 08:01 AM
Hey,

Thanks for answering, but...

neilw;

I can figure out so far http://www.opengl.org/discussion_boards/ubb/smile.gif
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
11-12-2002, 10:06 AM
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

fringe
11-13-2002, 01:13 AM
You should try the maths for yourself esp. because I have probably made a mistake but here goes.

OK starting from the abovepost:

x=(1-t)x1 + t.x2
y=(1-t)y1 + t.y2

and the same with primes on for x' and y'
(dot is multiply)
we need x=x'
x1 - t.x1 + t.x2 = x1' - t'.x1' + t'.x2'
rearrange to make t the subject
t.(x2-x1) +x1 = x1' + t'.(x2'-x1')
t= ((x1'-x1) + t'.(x2' - x1')) / (x2-x1)

OK now do the same for y=y'
t=((y1'-y1) + t'.(y2' - y1')) / (y2-y1)

now since both equations equal t then they must equal each other so:
((x1'-x1) + t'.(x2' - x1')) / (x2-x1) = ((y1'-y1) + t'.(y2' - y1')) / (y2-y1)

We now rearrange to find t':
t'.(x2' - x1')/ (x2-x1) -t'.(y2' - y1') / (y2-y1) = (y1'-y1)/ (y2-y1) - (x1'-x1)/ (x2-x1)
SO
t' ((x2' - x1')/ (x2-x1) - (y2' - y1') / (y2-y1)) = (y1'-y1)/ (y2-y1) - (x1'-x1)/ (x2-x1)
Giving t'= ((y1'-y1)/ (y2-y1) - (x1'-x1)/ (x2-x1)) / ((x2' - x1')/ (x2-x1) - (y2' - y1') / (y2-y1))

We now take this and substitute it in for x' and y' which gives us the point of intersection
x'= x1' + t'(x2'-x1')

and the same for y'

Hope this helps,

fringe

(note the algebra may not be 100% corrrect)

11-13-2002, 07:11 AM
Hey, thanks fringe, I will try it later.

EPHERE:

It seems that your function only works if they are not "co-plana"? Parallell.

ie;

2 lines
a1 = (0, 0, 0)
a2 = (0, 10, 0)

b1 = (10, 0, 0)
b2 = (-10 10, 0)

Trying the function with your code this works fine, I get the intersection point.

But, in my case they are always coplanar.
so 2 lines like:

a1 = (0, 0, 0)
a2 = (0, 10, 0)

b1 = (0, 5, 0)
b2 = (0, 20, 0)

doesnt seems to work, i always get the error vector returned..

You know why?

tx.