Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

chris1234

intersecting lines

This topic is 6080 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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)

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!