A convenient method that tells you if a rectangle is intersecting a line

Shared Code
#1

Hey!

I recently needed a method that…well, the title says it all. This method takes the x, y, width and height values of a rectangle, and the two endpoints of a line, and returns true if the line intersects the rectangle range at all.

Here ya go :slight_smile:


public static boolean rectangleIntersectsLine(double x, double y, int w, int h, double lx1, double ly1, double lx2, double ly2) {
    //determine values to be used in the equation for the line
    double m = (ly2-ly1)/(lx2-lx1);
    double p = lx1, q = ly1; //p = the offset from left side of screen, q = offset from bottom
    //if point l2 is closer to x = 0 than l1, set p and q to lx2's coordinates
    if (lx2 < lx1) {
        p = lx2;
        q = ly2;
    }
    //test if both end points of line are on left side, right, top, or bottom
    //if any is true, then the line does not intersect
    boolean on_left = (lx1 < x && lx2 < x), on_right = (lx1 > x+w && lx2 > x+w), 
            on_top = (ly1 < y && ly2 < y), on_bottom = (ly1 > y+h && ly2 > y+h); 
    if (!on_left && !on_right && !on_top && !on_bottom) {
        if (((y < (m*(x-p)+q)) && (y+h > (m*(x-p)+q)))
                || ((y < (m*(x+w-p)+q)) && (y+h > (m*(x+w-p)+q)))) { //if left side or right side of rectangle intersects line
            return true;
        } 
        if ((x < (((y-q)/m)+p) && x+w > (((y-q)/m)+p))
            || (x < (((y+h-m)/q)+p) && x+w > (((y+h-q)/m)+p))) { //if top side or bottom side of rectangle intersects line
            return true;
        }
    }
    return false;
}
#2

There’s also the stdlib Rectangle2D’s implementation:

public boolean intersectsLine(double x1, double y1, double x2, double y2) {
    int out1, out2;
    if ((out2 = outcode(x2, y2)) == 0) {
        return true;
    }
    while ((out1 = outcode(x1, y1)) != 0) {
        if ((out1 & out2) != 0) {
            return false;
        }
        if ((out1 & (OUT_LEFT | OUT_RIGHT)) != 0) {
            double x = getX();
            if ((out1 & OUT_RIGHT) != 0) {
                x += getWidth();
            }
            y1 = y1 + (x - x1) * (y2 - y1) / (x2 - x1);
            x1 = x;
        } else {
            double y = getY();
            if ((out1 & OUT_BOTTOM) != 0) {
                y += getHeight();
            }
            x1 = x1 + (y - y1) * (x2 - x1) / (y2 - y1);
            y1 = y;
        }
    }
    return true;
}

I guess I never realized the complexity of rect-line intersection testing.

#3

Well, it’s not too bad. Essentially, I just find the equation of the line, check to make sure the end points of the line are not both on one side, then find x/y values of the line at certain points on the rectangle. For example, if the y value at the x position of the left side is in between the rectangle’s highest and lowest y value, then the line intersects.

#4

Well yeah, it’s not too bad but relative to other simple intersection tests it requires a fair bit of code.

#5

Apologies if I’m missing something or misinterpreting your code, but it seems there are a couple potential issues there. First, this:

double m = (ly2-ly1)/(lx2-lx1);

May fail if the line is vertical or nearly vertical. For this reason, the slope form for lines is hardly every used in collision detection code. In general, representations that are invariant under rotation should be preferred.

Also, I think there may be some cases for which the function may not return the correct result, but I’d have to look at it a bit more carefully to be sure.

In any case, if you just need a boolean result, you don’t need to do quite that much work. The separating axis test for a line segment and a box is simple and robust, and will handle all cases correctly. (Your code starts out as the SAT, but then instead of testing the axis parallel to the line normal, performs edge intersection tests instead.)

#6

Assuming you’re going to test more than one…you don’t do it this way.

#7

This may be my 39 degree fever speaking, but damn are you annoying. At least clarify what the hell you mean.

#8

Thanks. Google ray-slope.