Menu
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!
905
Combine the two rectangles into one large rectangle. Subtract from the large rectangle the first rectangle and the second rectangle. 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.
The distance between two points using coordinates can be given as, d = √[(x2 x 2 − x1 x 1 )2 + (y2 y 2 − y1 y 1 )2], where (x1,y1 x 1 , y 1 ) and (x2,y2 x 2 , y 2 ) are the coordinates of the two points.
The 2D distance formula gives the shortest distance between two points in a two-dimensional plane. The formula says the distance between two points (x1,y1) ( x 1 , y 1 ) , and (x2,y2) ( x 2 , y 2 ) is D=√(x2−x1)2+(y2−y1)2 D = ( x 2 − x 1 ) 2 + ( y 2 − y 1 ) 2 .
This length can be computed with the help of Pythagora's theorem: dist = sqrt((x2-x1)^2 + (y2-y1)^2) . This is known as the Euclidian distance between the points.
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(x1, y1) and (x1b, y1b) (x2, y2) and (x2b, y2b)
188
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).
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 ).
38
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
