Wednesday 25 July 2012

Line Intersection – y = mx + c

So, a twitter conversation started up with Dave Voyles, he wanted to be able to find the exact point that two rectangles collided with each other, some suggestions got thrown about, but I thought one way to do it would be to use the line equation,

image

This equation is used to represent a line, the x and y co-ords are the possible points along this line, m in the gradient or slope of the line and the c is where the line crosses through the y axis on a graph and is known as the y intercept.

So I thought, you could build 4 of these lines from your rectangles, then using this equation you can find exactly where the line(s) intersect.

I am not going to cover all the math here, but what I am doing here is first finding the slope and y intercept of the two lines, we then see if both lines are vertical or horizontal, if both lines are then it’s pretty simple to solve, if not, then we have to re calculate the lope and the y intercept.

That done we can then check to see if our two equations add up,so I solve for y in both cases, if they are equal, then we just need to make sure that our x value lies on both the lines based on the line min and max values….and, well that’s about it.

As I have said before, I am probably sub GCSE math, so a lot of this could well be all bum, but it works, please point and laugh out loud at my crap math but please give your reasons for pointing and laughing, that way we all learn from my mistakes :)

I wrote this class a long time ago to, and had to dig the source out from my HDD to post it here.

Here are some pics of the code in action, we have 2 lines, first image is with no intersection

image

I can then rotate the green line round so that it intersects, here are a few images of the lines intersecting, the red dot (if you can see it) is the exact point of intersection.

image

image

image

I made a mod to my original code so if the lines are both vertical or both horizontal it gets an intersection point based on the two inner points and puts it in the middle, like this

image

And  this

image

You can download the sample code for this here.

You can control the green line with the arrow keys to move it about, the keys Q and Z to scale it’s length, as well as E and C to rotate it.

For more help and better explanation of the y = mx + c equation, google it, there are loads of math resources out there.

3 comments:

  1. oo, different approach to the one I'd take (as math makes my head hurt) which would be to do a Rectangle.Intersect to find the area of intersection (also as a rectangle) then a Ray.Intersect from the centre of Rectangle 1 to the centre of the result of the first intersection. *scratches head* I think. (Wah! Now my head hurts)

    ReplyDelete
    Replies
    1. I think that would work fine, but would only be of use for axis aligned checks. I might be wrong, I guess you need to test test it out :)

      Delete
  2. Yup, would only work for axis aligned stuff as rectangle has no concept of a rotation. You could also do an easy out and wrap a sphere round each rectangle first and check for overlap before you continue. Also you 'should' handle the case where there are multiple nearest points of intersection and where one rectangle is contained by another..... ;)

    m<

    ReplyDelete