CODEWITHSUNDEEP
matlabmathgeometry
rethabile
rethabile

Reputation: 3198

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

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

Upvotes: 5

Views: 1786

Answers (6)

angainor
angainor

Reputation: 11810

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.

Upvotes: 0

paddy
paddy

Reputation: 63481

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.

Upvotes: 4

rethabile
rethabile

Reputation: 3198

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.

Upvotes: 2

Bitwise
Bitwise

Reputation: 7805

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.

Upvotes: 0

Serg
Serg

Reputation: 14118

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.

Upvotes: 1

TyrZaraki
TyrZaraki

Reputation: 33

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.

Upvotes: 1

Related Questions