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

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. — rethabile, Sep 16 '12 at 22:59

score 4 · Answer 1 · edited Sep 20 '12 at 10:03

4

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.

edited Sep 20 '12 at 10:03

Gunther Piez

29,760
6
71
103

answered Sep 15 '12 at 22:42

paddy

60,864
6
61
103

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? – rethabile 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. – rethabile Sep 16 '12 at 23:53
In that case I've handled all possible scenarios. An easy test for edge intersection is this: If you have one edge `A->B` and another edge `P->Q` then the edges intersect if `P` and `Q` are on opposite sides of `A->B` AND `A` and `B` are on opposite sides of `P->Q`. So you can use the same cross-product test for everything. In fact, you'll already have done half of these while testing for the square being completely inside. – paddy Sep 17 '12 at 00:25
I think there is a flaw here. I think there are square positions in which the vertices will fall on both sides of the edge extensions. For example, consider a triangle at (0,0) (1,1) (2,0) with a square at (0,3) (2,3) (0,5) (2,5). Am I correct? – Bitwise Sep 18 '12 at 06:53
1

This fails even for simple cases. Did you actually test it? – Gunther Piez Sep 18 '12 at 22:20
@bitwise : If I trace those edges clockwise, every vertex of your square is on the left of the first two edges, and on the right of the last edge. Hence outside. – paddy Sep 18 '12 at 22:35
@hirschhornsalz Show a simple case that fails. – paddy Sep 18 '12 at 22:35
Sorry, I misread triangle-square-vector for edge-square-vector. I think your idea actually works :-) – Gunther Piez Sep 18 '12 at 23:45
This is pretty much the same as how you test for points inside a convex hull, but I've extended it with that simple edge-intersection test that handles shape intersection when all vertices are outside. This idea would work fine for any *convex* polygon - not just triangles. – paddy Sep 20 '12 at 22:28

score 2 · Accepted Answer · edited May 23 '17 at 12:10

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.

score 1 · Answer 3 · answered Sep 15 '12 at 20:40

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.

score 1 · Answer 4 · answered Sep 16 '12 at 15:56

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.

Bitwise · Answer 5 · 2012-09-18T06:44:19.687

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.

score 0 · Answer 6 · answered Sep 20 '12 at 11:54

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.

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

6 Answers6