Hi, for my simple collision detection routine I need a way to find out if two lines intersect..so I hope anyone can tell me how to find out if 2 lines intersect.... Chris

Equation of a line:

Ax + By + C = 0

Or

f(t) = o + td

Sorry I didn''t have time to go more into detail.

y=mx+c = equation of a line (2d)

m=gradient
c=constant

let x be equal for both lines, if y''s are also same then the
lines intersect. Run through possible values of X.

Only method that springs to mind, although I''m sure there is a quicker way using good math.

,Jay

HI!
well, I guess you can come up with a solution which fits best your needs if you study a little bit of algebra geometry (or whatever you call it, I''m Brazilian so I don''t know the name for this in enlglish... but it''s the geometry that uses algebra to define lines circles, etc... that''s what the other posts are giving you, the equation of a line, but I guess it''s useless if you don''t understand anything about this kind of geometry....).

You may find information on this "kind" of geometry on highschool math books (at least here in brazil we learn it at highschool)... after you understand it you will be able to write your colision detection between two lines.... just keep in mind that you won''t be dealing (i guess) with the whole line (which is endless) but rather a small part of it....


I''d like to give you some code but it would take a time I don''t have right now.......

good luck!

In 3d you can test for intersection by calculating the perpendicular distance between the two lines.

Using vectors is easiest, r=r0 + mt, for both lines - r0 is a vector from the origin to a point on the line, t is a vector parallel to the line and m is a scalar value that locates how far along the line the point r is.

The maths to work out the minimum distance between two lines is pretty easy (if I remember back to first year uni! ).
You find the mimimum distance by differentiating d(distance) / d(location of point along line)

**The minimum occurs at a point where a vector joining the two lines is at 90 degrees to both lines.**

When you have the min distance check if it equals zero - if it does then the lines intersect!

Warnings: the methods fail if the two lines are parallel and on top of each other (ie they are the same line).

In 2d the method would fail if the lines were parallel (they would never intersect)

foamer

quote:

---

Original post by foamer
In 2d the method would fail if the lines were parallel (they would never intersect)

---

This was going to be my first comment. In 2d, for 2 lines to intersect their slopes/gradients must not be the same. If they are not the same, then they intersect somewhere. If you use floating point gradients, then be careful in testing for equality; if the two gradients fall within a given tolerance, you can consider them equal and assume the lines don''t intersect within a reasonable distance.

[ GDNet Start Here | GDNet Search Tool | GDNet FAQ | MS RTFM [MSDN] | SGI STL Docs | Google! ]
Thanks to Kylotan for the idea!

That isn''t necessarily true in collision detection. Just because you are driving the same direction down the road as the car in front of you doesn''t mean you don''t have to worry about running into them. If cars on parallel and anti-parallel paths could not collide the world would be a much safer place.

y1 = ax + b
y2 = cx + d

to see if they intersect make them equal

ax + b = cx + d
ax + (b - d) = cx
(b - d) = (c - a)x

x = (b-d) / (c-a)

The lines should intersect at x

Go on an Intense Rampage

am i missing something?

y1=m1*x1+n1
y2=m2*x2+n2

if ( m1==m2 ) lines collide
if ( m1!=m2 ) lines don''t collide

Also, if you store your lines as 2 points, then find m by:

m=(x1-y1)/(x2-y2)