jump to navigation

Line Segment Intersection October 7, 2008

Posted by Jesse in : Game Development , trackback

Update: I’ve written a new article that handles this a bit differently.

Earlier today, somebody in #xna asked how to find the intersection of two line segments.  This is something that comes up pretty regularly, so I happened to have the answer handy.

Notes:

First, we need two line segments, which are defined by their endpoints.


Notice that if you put in zero for U, you’ll get the start point, if you put in one, you’ll get the end point.

The point of intersection would be where they are equal.

Since we need this in terms of x and y, we can rewrite that last equation as the following two:

We can use those to solve for U.

Notice that the denominator on both of those equations is the same. Solve for that first, if it is zero, then the lines are parallel and we’re done. (If both numerators are also zero, then the two line segments are coincident.)

Since these equations treat the lines as infinitely long lines instead of line segments we want, there is guaranteed to be an intersection point if the lines aren’t parallel. To determine if it happens in the segments we’ve specified, we need to see if U is between zero and one. Verify that both of these are true:

If we’ve gotten this far, then our line segments intersect, and we just need to find the point at which they do and then we’re done.

I’ve also put together a very simple sample project to demonstrate this. It draws two line segments, with small red circles indicating the end points. A yellow circle will show where the segments intersect if they do. If they are coincident, a green circle will indicate that.


Here’s the sample. You’ll need Visual C# 2005 and XNA Game Studio 2.0. Leave comments or email me with any questions.

Comments»

1. Veli - October 23, 2008

Can you rework ProcessIntersection function to work in 3D? Thanks.

2. Simon (Darkside) Jackson - November 12, 2008

Great stuff, it always amazes me how you transform the mathematical notation into actual code in C#.
Always a lot easier to read for math noobs like myself (I’ve forgotten most of my math from school, so many years ago 🙁 )

3. Ryan - December 16, 2008

I have a question. Why do you use

if (Math.Abs(denominator) <= 0.00001f)

instead of

if (Math.Abs(denominator) == 0f)? A tolerance of somekind?

Great post, by the way. 🙂

4. Jesse - December 16, 2008

That’s exactly right. When dealing with floating point numbers, you have to recognize that they have limited precision. The denominator is created by subtracting and multiplying eight floating point numbers, so instead of testing to see if it’s exactly zero, we just test if it’s pretty close.

5. Ryan - December 16, 2008

Thanks for the quick reply, Jesse. I’m a Computer Science student majoring in Games, and consider myself a hobbyist as well.

I might be starting my own blog soon, and would love if we could be link buddies. Love your blog.

6. Jesse - December 16, 2008

Hit me with the URL when you get your blog up. I’m up to about six million game development blogs that I follow, but always looking for more. I don’t know what I’d do without RSS. 🙂

What sort of stuff are you working on/with?

7. Ryan - December 17, 2008

I’m trying a very simple Breakout clone using XNA at the moment. It will be my first ever full game. 🙂

XNA is fantastic but eventually I want to start working with C++ and DirectX.

8. TyphoidHippo - May 23, 2009

This is the only place on the entire internet I could find an understandable, and useful example of how to do this. I’m actually using C++ and OpenGL at the moment, but the clear and concise logic in your XNA/C# code translated with ease. Thanks so much for sharing this, seriously – I was about to pull my friggin hair out.

9. Tobias Wehrum - February 23, 2010

First of all, thank you for your code and the explaination! It was very helpful.

This being said, there is one problem with it: When two line segments are coincident, but don’t overlap, your code says they intersect anyway.
This is also described (with a provided solution) at http://stackoverflow.com/questions/2255842/detecting-coincident-part-of-two-line-segments-in-c

10. Jesse - February 23, 2010

Tobias, thanks for commenting. I’m glad it was helpful.

It appears you’re correct, that’s definitely a flaw in my code. I’ll write an update when I get a chance.

11. Rustum Scammell - October 11, 2011

Jesse, this is great stuff. Combined with the separating axis theorem, it’s the beginning’s of a good collision detection and response system. I’d like to make a small correction to the math above. The factor (x1-x3) in the final solution for Ua and Ub, should be (x3-x1). Cheers!

12. C# performance tuning, part 2. Collisions explained | Why u no code?! - May 24, 2014

[…] – I’ve just found this algorithm somewhere on the internet (to be exact – here: http://thirdpartyninjas.com/blog/2008/10/07/line-segment-intersection/), as I didn’t want to bother to much with maths here and get to code. Tests I wrote proved to […]

13. What's the easiest method to gain $53691 a month: https://get-2-btc-per-day.blogspot.no?s=07 - November 21, 2019

Invest $ 6415 and get $ 6665 every month: https://ss-d-ff.blogspot.se?vb=83

14. Invest in mining ?r?pt??urren?y $ 5000 on?e and get p?ssive income of $ 70000 ??r m?nth: http://vuacbqf.wildwestcoders.com/1f5e16877 - April 17, 2020

??SY S??E?? ??RNINGS ON T?E INT?RN?? from $8794 ??r w?e?: http://esrfg.sitebuilerguide.com/a1df669