• Advertisement

Archived

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

intersecting lines

This topic is 5807 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
quote:
Original post by wolfman8k
if ( m1==m2 ) lines collide
if ( m1!=m2 ) lines don''t collide

if(m1 == m2), lines are parallel
if(m1 == -m2), lines are perpendicular
if(m1 != m2), lines intersect

If you consider "collision" to mean "lie exactly upon each other," then you''re right. If you take it to mean "have some point in common," then you''re wrong.

[ 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
quote:
Original post by Oluseyi
if(m1 == -m2), lines are perpendicular



if(m1 * m2 == -1), lines are perpendicular.

Share this post


Link to post
Share on other sites
well thanks for the replies...it''s obviously that the formula y = mx + c is ''best'' to be used...I implemented it yesterday...but it really didn''t work too well no collision when lines collided and a collision at times when they weren''t even near eachother...I used this formula to find if two lines of two rotated rectangular boxes collided with eachother or not, but I found a better approach on the www...now I just have to hope that I''ll get it working.

Chris

Share this post


Link to post
Share on other sites

  • Advertisement