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

27,548

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

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

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

Solution 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

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

Share:
27,548

Related videos on Youtube

Philipp Lenssen
Author by

Philipp Lenssen

Dev at Anyland &amp; Manyland

Updated on July 09, 2022

Comments

  • Philipp Lenssen
    Philipp Lenssen over 1 year

    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!

  • Philipp Lenssen
    Philipp Lenssen over 12 years
    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.
  • Roy T.
    Roy T. over 12 years
    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.
  • Michael
    Michael over 6 years
    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?
  • Maxim
    Maxim over 6 years
    Yes, that's right. I have included this in the code since this case doesn't hurt. Thank you
  • OK.
    OK. about 6 years
    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.
  • M Katz
    M Katz about 6 years
    @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.
  • Darkproduct
    Darkproduct about 5 years
    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.
  • Suma
    Suma about 5 years
    The formulate is unclear to me. How to you compute ^2 of vector? Did you mean a dot product with itself?
  • Felix K.
    Felix K. about 5 years
    @Suma It's the exponent operator ( alias power 2 ) for each of the numbers in the vector.
  • Suma
    Suma about 5 years
    How are vector components summed so that Sqrt returns a scalar distance? (I do not know lua, perhaps this is a basic knowledge).
  • Felix K.
    Felix K. about 5 years
    @Suma 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)).
  • user19283043
    user19283043 over 3 years
    @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?
  • Felix K.
    Felix K. about 3 years
    @user19283043 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.
  • oarfish
    oarfish about 2 years
    This also seems to ignore the rotation of the rectangles.