Jump to content
  • Advertisement
Sign in to follow this  
ScottH87

2D Collision Detection Ray/Line Segment

This topic is 3344 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, I'm trying to right an algorithm for 2D collision detection between a ray from a character and a line segment representing a wall. Specifically, I need to determine whether they do infact intersect or not and also the point where they intersect. I'm a little rusty on the maths side of things and can't seem to nail this at all. Can anyone give me a quick run down on how to get what I'm looking for? Cheers

Share this post


Link to post
Share on other sites
Advertisement
There's a ton of information on the web about this, but it shouldn't be too hard so I'll just give you some help.

For now, pretend it's (non-segment) line-versus-line. Each line can bey expressed as y = m1 * x + b1 and y = m2 * x + b2. The lines intersect if there is an x such that their y values are equal, that is:
m1 * x + b1 = m2 * x + b2

Solve for x.

Then, determine whether that point is in the ray and the segment. Some x value will give the starting point of the ray. Any x value "before" that one won't be on the ray, so it wouldn't be a collision. The line segment yields two x values, one for each point. Only x's between those two values will yield an intersection.

Now, all you have to do is handle the case where one or both is vertical, where m would have to be infinite.

If that's not enough, just google for ray-line segment intersection, and you'll probably find a better solution than this one anyways.

Share this post


Link to post
Share on other sites
You define a front and back side to each line segment. For example I usually use the right side as front, when looking from the first endpoint towards the second endpoint along the line between them. You can the get the line on the form ax + by = c. If you have a coordinate system where increasing X is right, and increasing Y is up, then you set a = y2 - y1, and b = x1 - x2, for a line from (x1, y2) to (x2, y2). Then you set c = a * x1 + b * y1, which will be exactly the same value as c = a * x2 + b * y2, or for any ax * by where (x, y) is on the line.
The great thing about this representation is that if you calculate ax + by - c for any point (x, y), you get a value larger than 0 if it's in front of the line, below 0 if it's behind the line, and 0 if it's on the line. If you do this calculation for the start and end points of a different line, you have a possible intersection if one of them is in front of the first line, while the other is behind it. If that is the case, see if the same holds true for the endpoints of the first line in respect to the second line. If that also holds, then you have an intersection.
You can then get the intersection point as follows:

distance(point, line) = point.x*line.a + point.y*line.b - line.c

intersection = point1 + (point2 - point1) * distance(point1, line) / (distance(point1, line) - distance(point2, line))

Share this post


Link to post
Share on other sites
Quote:
Original post by Ezbez
For now, pretend it's (non-segment) line-versus-line. Each line can bey expressed as y = m1 * x + b1 and y = m2 * x + b2. The lines intersect if there is an x such that their y values are equal, that is:
m1 * x + b1 = m2 * x + b2

Solve for x.


I'm not 100% sure on how to go about doing that. Like I said I'm rusty on the maths side of things and I've forgotten how to rearrange that equation so that the unknown (x) is only on one side of the equation rather than both sides.

EDIT: After a bit of jiggery pokery I think I've worked it out. The rearanged equation is x = b1/(m2 - m1) (b2 in my case is always 0)

Thanks for all your help

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!