Take the 2-minute tour ×

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. example figure

share|improve this question
Please specify how the objects are specified - are you given the coordinates of the corners? Also, what happens if the square overlaps the triangle but no corners are inside the triangle - is that considered "inside"? –  Bitwise Sep 15 '12 at 20:45
given the (x,y) coordinates of each vertex in a triangle and squares (or in worst scenario, can be calculated). overlaps. hm.:'-( . . .i never thought of that one, but that would be considered inside. –  r m Sep 16 '12 at 22:59
add comment

6 Answers

Since you asked about matlab, an because other answers explained the direct approach, I will mention some available solutions. You might want to take a look at polyxpoly (if you have the Mapping Toolbox). It can handle more general cases. Otherwise, there is a bunch of contributions on the File Exchange, see e.g. Curve Intersect 2. Polygon_Intersection on the other hand returns the overlapping regions, not just intersection points.

share|improve this answer
add comment

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.

share|improve this answer
When I say 'sign' of the cross product, naturally I mean that your 2D co-ords are actually (x,y,0), and you are looking at the sign of the z-value after. To handle every other case, it might be easiest to just check whether any of the square edges cross the triangle edges. –  paddy Sep 16 '12 at 22:22
would this cater for an overlap as well? –  r m Sep 16 '12 at 23:05
The method in my answer will tell you if the square is entirely inside the triangle. The method in my comment (about bisecting edges) will tell you if the square intersects the triangle (hence overlapping). The case not handled, of course is where the triangle is completely inside the square. You might need to clarify your problem further. What other types of triangle-square intersections are classed as 'inside'? –  paddy Sep 16 '12 at 23:25
hi paddy, currently i'm working on a simplifying assumption that a triangle would always be bigger than squares, hence cases are square being completely inside and square that overlaps or has a corner inside. –  r m Sep 16 '12 at 23:53
This fails even for simple cases. Did you actually test it? –  hirschhornsalz Sep 18 '12 at 22:20
show 6 more comments

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;
        d = false;

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.

share|improve this answer
add comment

What you are actually trying to do is determine whether the square is linearly separable from the triangle, i.e. if there is a line you that separates the two objects. If such a line exists, then they do not intersect. There are several algorithms to test linear separability. The upside is that they are general so it will work with other polygons. The downside is that because of their generality they might not use specific characteristics of your problem to simplify the solution.

share|improve this answer
add comment

Maybe this can give an idea.

enter image description here

Create the triangle image with 0-1 values (this is the hard part); then for each square, create its 0-1 image, which is very simple; add both images, and calculate the values at different triangle or square coordinates. You can even calculate the area of the overlapping region.

share|improve this answer
add comment

Novice here. One idea that comes to mind is as follows. This may not be efficient but it is fairly simple.

1) Calculate the 4 corners of your square.

2) Select a direction that each corner/point will "walk" along. Basically choose a vector direction for that point.

3) Have those points "walk" along the vector and see if it interests with the boundaries of the triangle.

4) If a point's walking vector intersects an odd number of times that means it is inside. If it intersects an even number of times that means it is outside. Remember 0 counts as even.

5) Special cases must be made if you actually walk along an edge of the triangle. This can be avoided in most cases though by just selecting a different direction.

share|improve this answer
add comment

Your Answer


