Line - Rectangle collision

[NGM88]

Searching through the forums I found a function that checks whether two lines collide. Originally written by a member of these forums, Disch, here's a slightly altered version that I use in my project:

float PerpDot(const sf::Vector2f& a, const sf::Vector2f& b) { return (a.y*b.x) - (a.x*b.y); }

bool LineCollision(const sf::Vector2f& A1, const sf::Vector2f& A2, const sf::Vector2f& B1, const sf::Vector2f& B2, sf::Vector2f* out)
{
        sf::Vector2f a(A2 - A1);
        sf::Vector2f b(B2 - B1);
        sf::Vector2f c(B2 - A2);

        float f = PerpDot(a, b);

        // lines are parallel
        if (!f) { return false; }

        float aa = PerpDot(a, c);
        float bb = PerpDot(b, c);

        std::cout << bb << std::endl;

        if (f < 0)
        {
                if (aa > 0)     return false;
                if (bb > 0)     return false;
                if (aa < f)     return false;
                if (bb < f)     return false;
        }
        else
        {
                if (aa < 0)     return false;
                if (bb < 0)     return false;
                if (aa > f)     return false;
                if (bb > f)     return false;
        }

        if (out) { *out = b * (1.0f - (aa / f)) + B1; } // assigns the point of intersection
       
        return true;
}
 

I have a request, since I am mathematically impaired  , could someone tell me how to change this function so that it checks whether a line intersects a rectangle instead? Currently I convert my rectangle shapes to 4 lines and check each line with the function, but I imagine there must be an easier way to do it?

[Elias Daler]

Checking 4 line/line intersections is a pretty cheap way of doing things and it's one of the easiest and cleanest ways to do line/rect intersection, especially if you need to know intersection points. If you only need return true/false, then you can use this code I've written at some point of time:

bool segmentIntersectsRectangle(const sf::FloatRect& rect,
    const sf::Vector2f& a_p1, const sf::Vector2f& a_p2)
{
    // Find min and max X for the segment
    auto minX = std::min(a_p1.x, a_p2.x);
    auto maxX = std::max(a_p1.x, a_p2.x);

    // Find the intersection of the segment's and rectangle's x-projections
    if (maxX > rect.left + rect.width) {
        maxX = rect.left + rect.width;
    }

    if (minX < rect.left) {
        minX = rect.left;
    }

    // If Y-projections do not intersect then there's no intersection
    if (minX > maxX) { return false; }

    // Find corresponding min and max Y for min and max X we found before
    auto minY = a_p1.y;
    auto maxY = a_p2.y;

    auto dx = a_p2.x - a_p1.x;
    if (std::abs(dx) > NORMAL_TOLERANCE) {
        auto k = (a_p2.y - a_p1.y) / dx;
        auto b = a_p1.y - k * a_p1.x;
        minY = k * minX + b;
        maxY = k * maxX + b;
    }

    if (minY > maxY) {
        std::swap(minY, maxY);
    }

    // Find the intersection of the segment's and rectangle's y-projections
    if (maxY > rect.top + rect.height) {
        maxY = rect.top + rect.height;
    }

    if (minY < rect.top) {
        minY = rect.top;
    }

    // If Y-projections do not intersect then there's no intersection
    if (minY > maxY) { return false; }
    return true;
}

[NGM88]

Thank you very much for responding. What is "NORMAL_TOLERANCE" ?

[Elias Daler]

Oh, sorry, I forgot to edit it out. It's a very small constant, something like "epsilon" which is used as a guard so that you don't get too big quantities when dividing by it. Just set it at something like "0.0000001f"

[NGM88]

Thanks again!

[Elias Daler]

You're welcome.