Line Segment Intersection October 7, 2008
Posted by Jesse in : Game Development , trackbackUpdate: 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:
- I couldn’t get the Latex plugin for wordpress to work the way I wanted, so I used texify.com to generate these spiffy images.
- The line drawing code in the sample comes from the demos that are included with Farseer Physics.
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
Can you rework ProcessIntersection function to work in 3D? Thanks.
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 🙁 )
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. 🙂
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.
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.
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?
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.
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.
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
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.
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!
[…] – 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 […]