Line intersection + I am losing my mind.
Author
Just been trying to write a function to work out the intersection point (if any) of two lines. Went to start typing, and thought to myself "How the hell do I do this?".
Can anyone shed some light on how to do this? I appear to have lost my mind as I would normally be able to write such a function without even thinking...and looking at this has just confused the hell out of me somehow.
Thanks.
Author
Quote:Original post by SiCrane
Well the first question is: how are your representing your lines?
Start and end point vectors.
clicky
Intersection point calculation using the line parametric equation...
(damn...why isnt it working shit....)
If this is in 3D, you can be screwed over by floating point precision (i.e., your lines miss by 10-14 units or something and you'd like to declare that to be a hit).
here's what i use for 2d. If the 2 lines are parallel it returns -1, if they aren't hitting 0, and 1 if they are hitting.
linx and liny are the x and y of the last successful collsion. abs2 is basicly abs() but i've been having problems with it in dev c++.
linx and liny are the x and y of the last successful collsion. abs2 is basicly abs() but i've been having problems with it in dev c++.
float linx,liny;float abs2(float x){ if (x<0) {return -x;} return x;}int LinesCross(float x0,float y0,float x1,float y1,float x2,float y2,float x3,float y3){ float d=(x1-x0)*(y3-y2)-(y1-y0)*(x3-x2); if (abs2(d)<0.001) {return -1;} float AB=((y0-y2)*(x3-x2)-(x0-x2)*(y3-y2))/d; if (AB>0.0 && AB<1.0) { float CD=((y0-y2)*(x1-x0)-(x0-x2)*(y1-y0))/d; if (CD>0.0 && CD<1.0) { linx=x0+AB*(x1-x0); liny=y0+AB*(y1-y0); return 1; } } return 0;}
This may clear up the example.
Pa = P1 + ua ( P2 - P1 )
Pb = P3 + ub ( P4 - P3 )
Where P1, P2, P3, P4, Pa, Pb is a point. The two equation is describing two lines. Looking at the first equation. P2-P1 is a vector. P1 is a point on the line. And ua is commently call t. I call it here t1. So a line can be describe as a vector pointing in the line direction times a free variable t1 and added it with a point on the line. This is where you get Pa. The same goes for Pb.
Also the example doesnt mention that P1 = (x1, y1) and P2 = (x2,y2) etc. This will make the formulas below more clear.
x1 + ua (x2 - x1) = x3 + ub (x4 - x3)
and
y1 + ua (y2 - y1) = y3 + ub (y4 - y3)
so he calcute ua and ub (t1 and t2).
after that you get the intersection by using either ua or ub (t1 or t2) here he uses ua
x = x1 + ua (x2 - x1)
y = y1 + ua (y2 - y1)
where Pa = (x,y). The above formula can be written as Pa=P1+ua(P2-P1) as his top formula.
hope I didnt confuse it more.
Pa = P1 + ua ( P2 - P1 )
Pb = P3 + ub ( P4 - P3 )
Where P1, P2, P3, P4, Pa, Pb is a point. The two equation is describing two lines. Looking at the first equation. P2-P1 is a vector. P1 is a point on the line. And ua is commently call t. I call it here t1. So a line can be describe as a vector pointing in the line direction times a free variable t1 and added it with a point on the line. This is where you get Pa. The same goes for Pb.
Also the example doesnt mention that P1 = (x1, y1) and P2 = (x2,y2) etc. This will make the formulas below more clear.
x1 + ua (x2 - x1) = x3 + ub (x4 - x3)
and
y1 + ua (y2 - y1) = y3 + ub (y4 - y3)
so he calcute ua and ub (t1 and t2).
after that you get the intersection by using either ua or ub (t1 or t2) here he uses ua
x = x1 + ua (x2 - x1)
y = y1 + ua (y2 - y1)
where Pa = (x,y). The above formula can be written as Pa=P1+ua(P2-P1) as his top formula.
hope I didnt confuse it more.
In the 3d case, there are 3 cases:
1) The lines intersect.
2) The lines are parallel
3) The lines are not coplanar (i.e. all four of your points have to be in the same plane).
First, you need to test for case 3, then 2, and if it's not either of those, then they intersect, and you can find the point of intersection as per Zyberant's post.
The test for coplanarness is that the cross product (since it's perpendicular to both vectors and the unit perpendicular of a plane uniquely determines the plane) of the vectors from one point to another two is parallel to a similar cross product that involves the other point. (i.e. if you use P2-P1 and P3-P1 for the first cross product, then you need to have P4-P3 and P1-P3 or (P3-P4 and P1-P4, or whatever)).
In symbols:
Then to test for parallelness, just use:
Finally, if the lines are not parallel but are coplanar, they intersect, and the point of intersection can be found with regular algebra, using the line equation:
r(t) = r1 + t*r2
where r is your line, r1 is a vector from the origin to a point on the line, and r2 is a vector in the direction of your line.
Intersection will be where your lines meet (i.e. the point is in both lines), so it is where your line equations are equal:
line1(t) = line2(u)
I think you can figure it out from there.
[edit] Whoops. Just noticed you're working on the 2d case. In two dimensions, there are only the two cases (parallel or intersecting). The test for parallel is the same.
The vital piece of information you're looking for is that line1(t) == line2(u). Then you take the t and u that you discover and plug them into their respective equations to derive the point.
1) The lines intersect.
2) The lines are parallel
3) The lines are not coplanar (i.e. all four of your points have to be in the same plane).
First, you need to test for case 3, then 2, and if it's not either of those, then they intersect, and you can find the point of intersection as per Zyberant's post.
The test for coplanarness is that the cross product (since it's perpendicular to both vectors and the unit perpendicular of a plane uniquely determines the plane) of the vectors from one point to another two is parallel to a similar cross product that involves the other point. (i.e. if you use P2-P1 and P3-P1 for the first cross product, then you need to have P4-P3 and P1-P3 or (P3-P4 and P1-P4, or whatever)).
In symbols:
let r1 = (P2 - P1)let r2 = (P3 - P1)let r3 = (P4 - P1)if (r1 x r2)/|r1 x r2| == (r1 x r3)/|r1 x r3| then lines are coplanar.Then to test for parallelness, just use:
let r1 = (P2 - P1)let r2 = (P4 - P3)if r1/|r1| == r2/|r2| then lines are parallel.Finally, if the lines are not parallel but are coplanar, they intersect, and the point of intersection can be found with regular algebra, using the line equation:
r(t) = r1 + t*r2
where r is your line, r1 is a vector from the origin to a point on the line, and r2 is a vector in the direction of your line.
Intersection will be where your lines meet (i.e. the point is in both lines), so it is where your line equations are equal:
line1(t) = line2(u)
I think you can figure it out from there.
[edit] Whoops. Just noticed you're working on the 2d case. In two dimensions, there are only the two cases (parallel or intersecting). The test for parallel is the same.
The vital piece of information you're looking for is that line1(t) == line2(u). Then you take the t and u that you discover and plug them into their respective equations to derive the point.
Quote:Original post by FlarelockeIMO this is not the best way to approach the 3D case, for various reasons. The more common solution is to find the closest pair of points between the lines and test the squared distance between them against some tolerance. If an intersection point is required, it can then be computed as the average of the two points.
In the 3d case, there are 3 cases:
1) The lines intersect.
2) The lines are parallel
3) The lines are not coplanar (i.e. all four of your points have to be in the same plane).
First, you need to test for case 3, then 2, and if it's not either of those, then they intersect, and you can find the point of intersection as per Zyberant's post.
The test for coplanarness is that the cross product (since it's perpendicular to both vectors and the unit perpendicular of a plane uniquely determines the plane) of the vectors from one point to another two is parallel to a similar cross product that involves the other point. (i.e. if you use P2-P1 and P3-P1 for the first cross product, then you need to have P4-P3 and P1-P3 or (P3-P4 and P1-P4, or whatever)).
In symbols:let r1 = (P2 - P1)let r2 = (P3 - P1)let r3 = (P4 - P1)if (r1 x r2)/|r1 x r2| == (r1 x r3)/|r1 x r3| then lines are coplanar.
Then to test for parallelness, just use:let r1 = (P2 - P1)let r2 = (P4 - P3)if r1/|r1| == r2/|r2| then lines are parallel.
Finally, if the lines are not parallel but are coplanar, they intersect, and the point of intersection can be found with regular algebra, using the line equation:
r(t) = r1 + t*r2
where r is your line, r1 is a vector from the origin to a point on the line, and r2 is a vector in the direction of your line.
Intersection will be where your lines meet (i.e. the point is in both lines), so it is where your line equations are equal:
line1(t) = line2(u)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
