line-rectangle collision detection

Question

I have one line (two point (x,y) (x1,y1)) and a rectangle with focus point (rx,ry). I need help to find out collision point between line and rectangle, an example in C++ will be help.

Answer 1

I don't see how you can represent a rectangle with just a "focus point". You'll need either the two corner points or one corner point with a width/height/rotation set of data.

However, once you have a rectangle, I would simply break it down into four lines and do the intercept checks between each of those four lines and the line you want to check against.

Doing a search on SO for "line intersection" turns up numerous questions, including this one, which seems promising. In fact, searching for "line rectangle intersection" gives you this one, which seems to be exactly what you're after.

Answer 2

Theres a lot of information out there about interectioning shapes. http://www.geometrictools.com/LibFoundation/Intersection/Intersection.html is probably a very good starting spot. In fact it contains C++ code for line-rectangle intersection. And its by Dave Eberly who is fairly well known in the computer graphics world.

Having said that what I'd do if I needed my own algorithm is something like this:

1. Find the equation of the line containing the line-segment as a x + b y - 1 = 0;
2. evaluate f(x) = a x + b y - 1 for each vertex of the rectangle
3. If all corners are > 0 or all are < 0 you have no possible intersection.
4. Intersections can only occur on edges with one vertex having f(x)>0 and the other having f(x)< 0. So perform a line-segment to line-segment intersection with all such edges and the original line-segment.

This should work for arbitrary polygons. And so rotated rectangles wont be a problem.

If you need to speed things up a bit you can improve the rejection criteria in 3, by using axis-aligned bounding rectangles for the line segment and the rectangle.