Simplest/efficient way of checking if a square falls inside a triangle

Question

I'm just wondering if there is any simple/efficient way to check if square falls inside a triangle. or at least one corner falls inside or some overlaps. e.g. considering the figure below, I should be able to tell that the 3 squares fall inside. i.e. square 1 is obviously inside, one corner of square 2 is inside, and 3 overlaps.

Answer 1

Consider your triangle as three vectors all in a fixed rotation order: A->B, B->C and C->A

Now, consider for each triangle vertex you have four vector from that vertex to each square vertex. You compute the cross-product between each triangle edge-vector and each triangle-square vector (12 in total). If the cross-products are all the same sign (or zero), your square is inside.

Conceptually you are trying to determine whether the square vertices are on the left or right side of your line. You don't actually care whether it's left or right, or whether you're in clockwise or anticlockwise order... Only that the square vertices are on the same side of all the triangle vectors.

Answer 2

I'm checking out this nice tutorial. It explains how to test if a point is inside a triangle using various techniques. It seems it would help when a square corner falls inside.

And I liked the Barycentric technique, here I re-implemented it for matlab:

function d = isinside(p,a,b,c)

    % Test if a point p(x,y) is inside a triangle
    % with vertices a(x,y), b(x,y) and c(x,y)

    v0 = c - a;
    v1 = b - a;
    v2 = p - a;

    A = [dot(v0,v0) dot(v1,v0);dot(v0,v1) dot(v1,v1)];
    b = [dot(v2,v0); dot(v2,v1)];

    x  = A\b;

    % Check if point is in triangle
    if (x(1) > 0) && (x(2) > 0) && (sum(x) < 1)
        d = true;
    else
        d = false;
    end

Then I would test each vertex of the square, and if it happens one of them falls inside I would return. Quite lot of computation but it worths a try.

For an overlap, I would test for intersections, as discussed in this thread, for every combination of lines from both a triangle and a square.