How to calculate distance between two rectangles? (Context: a game in Lua.)

Question

Given two rectangles with x, y, width, height in pixels and a rotation value in degrees -- how do I calculate the closest distance of their outlines toward each other?

Background: In a game written in Lua I'm randomly generating maps, but want to ensure certain rectangles aren't too close to each other -- this is needed because maps become unsolvable if the rectangles get into certain close-distance position, as a ball needs to pass between them. Speed isn't a huge issue as I don't have many rectangles and the map is just generated once per level. Previous links I found on StackOverflow are this and this

Many thanks in advance!

Nikos

The second link you posted has the exact answer you're looking for. In particular this link: cgm.cs.mcgill.ca/~orm/mind2p.html. The extra details in your question about Lua / pixels are just noise. – Aparicio

possible duplicate of What is the quickest way to find the shortest cartesian distance between two polygons – Aparicio

Similar question: How do you detect where two line segments intersect? – Blockage

Answer 1

Not in Lua, a Python code based on M Katz's suggestion:

def rect_distance((x1, y1, x1b, y1b), (x2, y2, x2b, y2b)):
    left = x2b < x1
    right = x1b < x2
    bottom = y2b < y1
    top = y1b < y2
    if top and left:
        return dist((x1, y1b), (x2b, y2))
    elif left and bottom:
        return dist((x1, y1), (x2b, y2b))
    elif bottom and right:
        return dist((x1b, y1), (x2, y2b))
    elif right and top:
        return dist((x1b, y1b), (x2, y2))
    elif left:
        return x1 - x2b
    elif right:
        return x2 - x1b
    elif bottom:
        return y1 - y2b
    elif top:
        return y2 - y1b
    else:             # rectangles intersect
        return 0.

where

• dist is the euclidean distance between points
• rect. 1 is formed by points (x1, y1) and (x1b, y1b)
• rect. 2 is formed by points (x2, y2) and (x2b, y2b)

Fite

Am I right, that the last (missing) else case would cover the intersection case? So I could return 0 here, if I consider that the correct value for intersecting rectangles? – Confess

Yes, that's right. I have included this in the code since this case doesn't hurt. Thank you – Fite

This solution doesn't account for the rotation of the rectangles. Let's say there is on rectangle top left and the second is tilted, then the second point for the calculation should not be one of the corners. – Bugbee

Answer 2

Edit: As OK points out, this solution assumes all the rectangles are upright. To make it work for rotated rectangles as the OP asks you'd also have to compute the distance from the corners of each rectangle to the closest side of the other rectangle. But you can avoid doing that computation in most cases if the point is above or below both end points of the line segment, and to the left or right of both line segments (in telephone positions 1, 3, 7, or 9 with respect to the line segment).

Agnius's answer relies on a DistanceBetweenLineSegments() function. Here is a case analysis that does not:

(1) Check if the rects intersect. If so, the distance between them is 0.
(2) If not, think of r2 as the center of a telephone key pad, #5.
(3) r1 may be fully in one of the extreme quadrants (#1, #3, #7, or #9). If so
    the distance is the distance from one rect corner to another (e.g., if r1 is
    in quadrant #1, the distance is the distance from the lower-right corner of
    r1 to the upper-left corner of r2).
(4) Otherwise r1 is to the left, right, above, or below r2 and the distance is
    the distance between the relevant sides (e.g., if r1 is above, the distance
    is the distance between r1's low y and r2's high y).

Helfand

This misses the aspect of rotation, e.g. if r1 is rotated in a way that the shortest connection to the upper-left corner of r2 starts on a line of r1 instead of a corner. – Stefaniestefano

@OK, you are right. I missed that the OP included that the rectangles can be rotated. I jumped to the idea that the rectangles were not rotated, since it's such a common problem to solve. – Helfand

I came here looking for the solution for the rectangles not being rotated, so thankyou :) – Epigeal

Answer 3

Actually there is a fast mathematical solution.

Length(Max((0, 0), Abs(Center - otherCenter) - (Extent + otherExtent)))

Where Center = ((Maximum - Minimum) / 2) + Minimum and Extent = (Maximum - Minimum) / 2. Basically the code above zero's axis which are overlapping and therefore the distance is always correct.

It's preferable to keep the rectangle in this format as it's preferable in many situations ( a.e. rotations are much easier ).

Pharmacopsychosis

The formulate is unclear to me. How to you compute ^2 of vector? Did you mean a dot product with itself? – Kilovoltampere

@Kilovoltampere It's the exponent operator ( alias power 2 ) for each of the numbers in the vector. – Pharmacopsychosis

How are vector components summed so that Sqrt returns a scalar distance? (I do not know lua, perhaps this is a basic knowledge). – Kilovoltampere

@Kilovoltampere Sorry i was confused because i wrote this piece of code a long time ago. Max((0, 0), Abs(Center - otherCenter) - (Extent + otherExtent)) calculates the distance per component. You then basically calculate the length of the vector which is Sqrt((x * x) + (y * y)). – Pharmacopsychosis

@FelixK. Could you give me an example of this formula? I don't understand the maximum and minimum here. For example, if we have two points, (3,4) and (6,1), and assume the extents are 2 and 4, respectively, then how do we calculate the length? – Windlass

@Windlass Sorry for the late response. Minimum is the minimum value on x and y axis, for example (-2,-2), and the maximum would be (3,2), the Extend in this case would be (2.5,2). Length is described in the comment above. – Pharmacopsychosis

This also seems to ignore the rotation of the rectangles. – Pe

@Pe You are right don't know why i did not consider it when writing, however i think the use is pretty good for non rotating rectangles. – Pharmacopsychosis

Answer 4

Pseudo-code:

distance_between_rectangles = some_scary_big_number;
For each edge1 in Rectangle1:
    For each edge2 in Rectangle2:
        distance = calculate shortest distance between edge1 and edge2
        if (distance < distance_between_rectangles)
            distance_between_rectangles = distance

Zymolysis

Answer 5

There are many algorithms to solve this and Agnius algorithm works fine. However I prefer the below since it seems more intuitive (you can do it on a piece of paper) and they don't rely on finding the smallest distance between lines but rather the distance between a point and a line.

The hard part is implementing the mathematical functions to find the distance between a line and a point, and to find if a point is facing a line. You can solve all this with simple trigonometry though. I have below the methodologies to do this.

For polygons (triangles, rectangles, hexagons, etc.) in arbitrary angles

1. If polygons overlap, return 0
2. Draw a line between the centres of the two polygons.
3. Choose the intersecting edge from each polygon. (Here we reduce the problem)
4. Find the smallest distance from these two edges. (You could just loop through each 4 points and look for the smallest distance to the edge of the other shape).

These algorithms work as long as any two edges of the shape don't create angles more than 180 degrees. The reason is that if something is above 180 degrees then it means that the some corners are inflated inside, like in a star.

Smallest distance between an edge and a point

1. If point is not facing the face, then return the smallest of the two distances between the point and the edge cornerns.
2. Draw a triangle from the three points (edge's points plus the solo point).
3. We can easily get the distances between the three drawn lines with Pythagorean Theorem.
4. Get the area of the triangle with Heron's formula.
5. Calculate the height now with Area = 12⋅base⋅height with base being the edge's length.

Check to see if a point faces an edge

As before you make a triangle from an edge and a point. Now using the Cosine law you can find all the angles with just knowing the edge distances. As long as each angle from the edge to the point is below 90 degrees, the point is facing the edge.

I have an implementation in Python for all this here if you are interested.

Unstrap

Answer 6

My approach to solving the problem:

1. Combine the two rectangles into one large rectangle
2. Subtract from the large rectangle the first rectangle and the second rectangle
3. What is left after the subtraction is a rectangle between the two rectangles, the diagonal of this rectangle is the distance between the two rectangles.

Here is an example in C#

public static double GetRectDistance(this System.Drawing.Rectangle rect1, System.Drawing.Rectangle rect2)
{
    if (rect1.IntersectsWith(rect2))
    {
        return 0;
    }

    var rectUnion = System.Drawing.Rectangle.Union(rect1, rect2);
    rectUnion.Width -= rect1.Width + rect2.Width;
    rectUnion.Width = Math.Max(0, rectUnion.Width);

    rectUnion.Height -= rect1.Height + rect2.Height;
    rectUnion.Height = Math.Max(0, rectUnion.Height);

    return rectUnion.Diagonal();
}

public static double Diagonal(this System.Drawing.Rectangle rect)
{
    return Math.Sqrt(rect.Height * rect.Height + rect.Width * rect.Width);
}

Garwood

Answer 7

This question depends on what kind of distance. Do you want, distance of centers, distance of edges or distance of closest corners?

I assume you mean the last one. If the X and Y values indicate the center of the rectangle then you can find each the corners by applying this trick

//Pseudo code
Vector2 BottomLeftCorner = new Vector2(width / 2, heigth / 2);
BottomLeftCorner = BottomLeftCorner * Matrix.CreateRotation(MathHelper.ToRadians(degrees));
//If LUA has no built in Vector/Matrix calculus search for "rotate Vector" on the web.
//this helps: http://www.kirupa.com/forum/archive/index.php/t-12181.html

BottomLeftCorner += new Vector2(X, Y); //add the origin so that we have to world position.

Do this for all corners of all rectangles, then just loop over all corners and calculate the distance (just abs(v1 - v2)).

I hope this helps you

Benzofuran

Thank you Roy. To clarify, I meant the distance between the outline of each rectangle, not the closest corners -- my goal is to know whether or not a ball of a specific given radius may still fit between the two rectangles at any point between them. Imagine the two rectangles to be stones (both rotated randomly, but never zero rotation), and the world having gravity -- I want to find out whether there is a theoretical chance that the ball, falling down from above, may get stuck between the two stones. – Nikos

Well, hmm that is a lot harder to calculate, I'll upvote this question, I'm curious if someone has a nice algorithm for this, it should be there. – Benzofuran

Answer 8

I just wrote the code for that in n-dimensions. I couldn't find a general solution easily.

// considering a rectangle object that contains two points (min and max)
double distance(const rectangle& a, const rectangle& b) const {
    // whatever type you are using for points
    point_type closest_point;
    for (size_t i = 0; i < b.dimensions(); ++i) {
        closest_point[i] = b.min[i] > a.min[i] ? a.max[i] : a.min[i];
    }
    // use usual euclidian distance here
    return distance(a, closest_point);
}

For calculating the distance between a rectangle and a point you can:

double distance(const rectangle& a, const point_type& p) const {
    double dist = 0.0;
    for (size_t i = 0; i < dimensions(); ++i) {
        double di = std::max(std::max(a.min[i] - p[i], p[i] - a.max[i]), 0.0);
        dist += di * di;
    }
    return sqrt(dist);
}

If you want to rotate one of the rectangles, you need to rotate the coordinate system.

If you want to rotate both rectangles, you can rotate the coordinate system for rectangle a. Then we have to change this line:

closest_point[i] = b.min[i] > a.min[i] ? a.max[i] : a.min[i];

because this considers there is only one candidate as the closest vertex in b. You have to change it to check the distance to all vertexes in b. It's always one of the vertexes.

See: https://i.sstatic.net/EKJmr.png

Ornate

Answer 9

Please check this for Java, it has the constraint all rectangles are parallel, it returns 0 for all intersecting rectangles:

   public static double findClosest(Rectangle rec1, Rectangle rec2) {
      double x1, x2, y1, y2;
      double w, h;
      if (rec1.x > rec2.x) {
         x1 = rec2.x; w = rec2.width; x2 = rec1.x;
      } else {
         x1 = rec1.x; w = rec1.width; x2 = rec2.x;
      }
      if (rec1.y > rec2.y) {
         y1 = rec2.y; h = rec2.height; y2 = rec1.y;
      } else {
         y1 = rec1.y; h = rec1.height; y2 = rec2.y;
      }
      double a = Math.max(0, x2 - x1 - w);
      double b = Math.max(0, y2 - y1 - h);
      return Math.sqrt(a*a+b*b);
   }

Orgel

Answer 10

Another solution, which calculates a number of points on the rectangle and choses the pair with the smallest distance.

Pros: works for all polygons.

Cons: a little bit less accurate and slower.

import numpy as np
import math

POINTS_PER_LINE = 100

# get points on polygon outer lines
# format of polygons: ((x1, y1), (x2, y2), ...)
def get_points_on_polygon(poly, points_per_line=POINTS_PER_LINE):

    all_res = []

    for i in range(len(poly)):

        a = poly[i]

        if i == 0:
            b = poly[-1]

        else:
            b = poly[i-1]

        res = list(np.linspace(a, b, points_per_line))

        all_res += res

    return all_res



# compute minimum distance between two polygons
# format of polygons: ((x1, y1), (x2, y2), ...)
def min_poly_distance(poly1, poly2, points_per_line=POINTS_PER_LINE):

    poly1_points = get_points_on_polygon(poly1, points_per_line=points_per_line)

    poly2_points = get_points_on_polygon(poly2, points_per_line=points_per_line)

    distance = min([math.sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2) for a in poly1_points for b in poly2_points])

    # slower
    # distance = min([np.linalg.norm(a - b) for a in poly1_points for b in poly2_points])

    return distance

Hohenstaufen