How to calculate distance between two rectangles?

问题:

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!

回答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)

回答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).

回答3:

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

回答4:

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 ).

回答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.

回答6:

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

回答7:

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);
   }