Line intersection + I am losing my mind.

Well the first question is: how are your representing your lines?

linear algebra?

a11*x+a12*y = c1
a21*x+a22*y = c2

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++.

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.

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)

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 Flarelocke 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)

IMO 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.

Quote:

Original post by jyk IMO 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.

I take it you mean

min {|line2(t) - line1(u)|^2; t,u ← ℜ} < ε

Yeah, that works too. It still requires a parallel test, but you can do without the coplanar test and it doesn't run into floating point errors. It's harder to explain, though.