View Full Version : Line-Line intersection
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.
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)
11-10-2002, 09: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.
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).
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.
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?
11-12-2002, 12: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'
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
11-12-2002, 12:51 AM
from Robert Sedgewick's algorithms:
int ccw(point p0, point p1, point p2)
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) | | (dy1*dy2 < 0))
if((dx1*dx1+dy1*dy1) < (dx2*dx2+dy2*dy2))
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 )
Thanks for answering, but...
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.
As far as I can see that will only tell me if they intersect not where they do, or am i wrong?
11-12-2002, 09: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)
double numer,denom, mua, mub;
E_Vertex pa, pb;
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)
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);
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,
11-13-2002, 12: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)
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,
(note the algebra may not be 100% corrrect)
Hey, thanks fringe, I will try it later.
It seems that your function only works if they are not "co-plana"? Parallell.
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?
Powered by vBulletin® Version 4.2.3 Copyright © 2017 vBulletin Solutions, Inc. All rights reserved.