How to check intersection between a line and a rectangle?

Question

The title says it all, Ive been searching around and couldnt find anything that was straight and to the point. How would I take a line with points (x1,y1) & (x2, y2) and check its intersection between a rectangle (xR,yR)? I saw in the Line2D package that there were some intersection methods but not sure how to set it all up. Can someone show me a correct way of setting it up to check for an intersection (collision)?

Yaakov

"Thanks Dan" Don't include sigs. in questions. Collision between Area objects can be done relatively easily. Here is an example. – Pansophy

Warning. Because you can generically use Java's Area class to do collision/intersection detection for almost all Java 2D graphical objects it's tempting to think it can be used for ALL graphical objects. But it can't be – because if you construct an area for a 'line' the area of the line itself begins empty. Hence it's intersection with any other area always returns empty - even if the line crosses into your other area. You have been warned! – Staceestacey

Answer 1

Using the available classes from the 2D Graphics API.

Rectangle r1 = new Rectangle(100, 100, 100, 100);
Line2D l1 = new Line2D.Float(0, 200, 200, 0);
System.out.println("l1.intsects(r1) = " + l1.intersects(r1));

What this doesn't tell you, is where...

Charlettecharley

Thank you, I dont need to know where, just need to know if they do or dont. – Yaakov

Answer 2

A rectangle is 4 lines. You could compute the intersect between your line and the 4 lines of the rectangle.

given the equations of two lines, they would intersect when x and y are equal.

y = m1x + b1 y = m2x + b2

solving the equation you should get:

x = b2 - b1 / (m1 - m2);

Note that if m1 == m2, the lines are parallel and will never intersect, watch out for the divided by 0 in this case.

Then, since you are dealing with segments ratter than infinite lines, check if the intersect falls off within your segments (check if both X and Y are within each segment's boundaries).

Concertina

Thank you :) Ill play around with your answer :) Thanks – Yaakov

It's a little more tricky than this - the y = mx + c representation can't handle vertical lines. – Brusa

Answer 3

Returns null if lines do not intersect. Modified some c code from another response to similar question to make it Java. Haven't bothered to look into how/why it works, but does the job I needed it to.

static Point get_line_intersection(Line2D.Double pLine1, Line2D.Double pLine2)
{
    Point
        result = null;

    double
        s1_x = pLine1.x2 - pLine1.x1,
        s1_y = pLine1.y2 - pLine1.y1,

        s2_x = pLine2.x2 - pLine2.x1,
        s2_y = pLine2.y2 - pLine2.y1,

        s = (-s1_y * (pLine1.x1 - pLine2.x1) + s1_x * (pLine1.y1 - pLine2.y1)) / (-s2_x * s1_y + s1_x * s2_y),
        t = ( s2_x * (pLine1.y1 - pLine2.y1) - s2_y * (pLine1.x1 - pLine2.x1)) / (-s2_x * s1_y + s1_x * s2_y);

    if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
    {
        // Collision detected
        result = new Point(
            (int) (pLine1.x1 + (t * s1_x)),
            (int) (pLine1.y1 + (t * s1_y)));
    }   // end if

    return result;
}

Voyeur

it is line to line intersection, not rectangle to line intersection – Kilt

This is probably the best answer I have found for getting the intersection points. Just test each side of the rectangle. I used this to find the midpoint of the line inside of a rectangle. I was too lazy to figure it out myself. This was an easy solution. Thanks. – Beguine