Checking if any of corners of a rectangle is inside other rectangle

Question

I'm having a mathematical issue.

I have no issue checking if one rectangle is within bounds of the other when they both (or one of them) have no angle and fit the grid perfectly.. but once I change angle of both of them, it all goes downhill.

Here's what I mean - the one to the right works flawlessly, but the ones to the left not so much:

A general thought: Could you rotate both rectangles by some amount such that one of them becomes aligned with the grid? — Tim Biegeleisen, May 30 '16 at 00:52
@TimBiegeleisen technically yes, but then it won't be colliding - look at the purple rectangle to the left, if I rotated it so it's totally flat towards grid lines - it would no more be colliding. — , May 30 '16 at 00:57
If you need to check any intersection (not only `corner inside' case), consider separating axes method http://www.geometrictools.com/Documentation/MethodOfSeparatingAxes.pdf — MBo, May 30 '16 at 07:11

samgak · Answer 1 · 2016-05-30T23:15:47.593

It's possible to do this without using either rotations (which means calling trig functions) or normalizing vectors (which requires a sqrt).

Suppose your rectangle is defined by points a, b, c, d in clockwise order. A point is inside the rectangle if it is on the righthand side of each of the vectors ab, bc, cd and da.

You can test point p against vector ab by taking the dot product of the vector ap with a vector perpendicular to ab, which you can get just by swapping the x and y and flipping one of the signs. The sign of the dot product tells you what side of the vector you are on.

If the signs are all positive then the point is inside the rectangle. You don't need to normalize because you are only checking the sign, not the magnitude.

float pointToVector(Vec2 p, Vec2 a, Vec2 b)
{
    Vec2 n = new Vec2(b.y - a.y, a.x - b.x); // no need to normalize

    return n.dot(p - a);
}

bool pointInRect(Vec2 p, Vec2 a, Vec2 b, Vec2 c, Vec2 d)
{
    return (pointToVector(p, a, b) > 0) && // can short-circuit
       (pointToVector(p, b, c) > 0) &&
       (pointToVector(p, c, d) > 0) &&
       (pointToVector(p, d, a) > 0));
}

Note that this is actually an arbitrary point-in-4-sided-convex-polygon test. You could optimize it for rectangles by taking advantage of the fact that ab and cd are parallel, as are bc and da, so you can reuse the perpendicular vectors but reverse the sign of the check. That makes the code a little more complicated however. Also, the above assumes a co-ordinate system with y increasing going up. If not then change the the comparisons to < or define the rectangle in anti-clockwise order.

score 0 · Answer 2 · edited May 23 '17 at 11:44

0

You can rotate both rectangles such that one becomes aligned with the grid. First, calculate the degree of rotation for both rectangles:

angle = arc tan(ength of long side / length of short side)
        arc tan(11 / 7)
      = 57.5 degrees

Now you know that the green triangle is 57.5 degrees counter-clockwise from its long side being parallel to the x axis. So you can rotate both rectangles by 57.5 degrees clockwise to get a configuration which you can handle. Please see here for how to do this.

edited May 23 '17 at 11:44

Community

1
1

answered May 30 '16 at 01:04

Tim Biegeleisen

502,043
27
286
360

I know what the angles of these rectangles are and I can easily rotate their vectors around grid but that's not the point on what I'm trying to do. – May 30 '16 at 01:05
I thought you are trying to determine whether one rectangle overlaps with another, and that you can do this when one rectangle be aligned with an axis, but not if both be unaligned. My solution gives you a workaround. – Tim Biegeleisen May 30 '16 at 01:08
Is there a solution that doesn't involve rotating rectangles at all? All of these rectangles have corners, corners are points - finding these points within bounds shouldn't be as hard? – May 30 '16 at 01:09
It is hard if the rectangle be rotated. If you want to keep your current simple approach of detecting overlap then rotation is an easy way to do that. – Tim Biegeleisen May 30 '16 at 01:16

score 0 · Answer 3 · answered May 30 '16 at 01:56

I recommend just using Tim's answer and not be so wussy about rotation. However in case you really are too OCD for that, you could try the following vector-based method.

Since the sides of the rectangle are perpendicular, you can use them as a (orthogonal) coordinate system.