Manhatten distance between rectangles

Question

I have a set of rectangles and i need to calculate the manhatten distance between them. I already tried to implement it, but the code blow up and did not work well.

Maybe someone could help me with some smart (and efficient) formulas which could be used to calculate the distance between two rectangles?

Examples:

The distance between A and B is the length of the line 1. The distance between A and C is the length of the line 2. etc.

I use python to implement everything. If already a function exists (e.g. in scipy) and someone knows it, this would also be great.

Thank you

Answer 1

I suggest, you work with the central points of rectangles and rectangle widths to compute the distances. You mainly have to figure out which corners (edges) of rectangles to use for computation. everything else is simple. A quick example:

class Rect:
    def __init__(self,cpt,w,h):
        self.x = cpt[0]
        self.y = cpt[1]
        self.w = w
        self.h = h

    def dist(self,other):
        #overlaps in x or y:
        if abs(self.x - other.x) <= (self.w + other.w):
            dx = 0;
        else:
            dx = abs(self.x - other.x) - (self.w + other.w)
        #
        if abs(self.y - other.y) <= (self.h + other.h):
            dy = 0;
        else:
            dy = abs(self.y - other.y) - (self.h + other.h)
        return dx + dy

#example:
A = Rect((0,0),2,1)
B = Rect((4,5),1,2)
C = Rect((-1,-5),1,1)

print(A.dist(C))
print(A.dist(B))
print(B.dist(C))

Answer 2

A solution by @LynxLike does not seem to work so I am posting another solution. The test cases at the end of this post are simplified segments distances, where the answer of each case is obvious and the previous solution fails some.

In general, while the problem looks complicated, you can simplify it by dividing the problem into x-segments and y-segments and computing separately, by using the same algorithm for both axis. A solution should work both for rectangles and line segments.

For dx, you compute if the x coordinate of the right rect (or line seg) is larger than the sum of the left rect's x coord and width. If it's positive, that means there is a distance; otherwise, it's either touching, overlapping (in x-axis), or rects' relative position is flipped. Basically, unless rects have some distance you will get 0 or negative results which you can easily clip to 0 using a max function. You do not need to check which rect is which side; you can again use max() to check both situations at the same time.

# assuming other is on the right
d_case1 = max(other.x - (self.x+self.w), 0)
# assuming self is on the right
d_case2 = max(self.x - (other.x+other.w), 0)
# checking if any distance has positive
dx = max(d_case1, d_case2)

Here is a complete solution, which is based on @LynxLike 's Rect class and fixes where the original conditional statements failed! Thanks!

class Rect:
    def __init__(self, cpt, w, h):
        self.x = cpt[0]
        self.y = cpt[1]
        self.w = w
        self.h = h

    def dist(self, other):
        dx = max(max(other.x - (self.x+self.w), 0),
                 max(self.x - (other.x+other.w), 0))
        dy = max(max(other.y - (self.y+self.h), 0),
                 max(self.y - (other.y+other.h), 0))
        return dx + dy

# Case1: 1 distance apart
A = Rect((1,0),3,0)  #| ---
B = Rect((5,0),3,0)  #|     ---
assert A.dist(B) == 1
assert B.dist(A) == 1

# Case2: touching
A = Rect((1,0),4,0)  #| ----
B = Rect((5,0),3,0)  #|     ---
assert A.dist(B) == 0
assert B.dist(A) == 0

# Case3: intersects
A = Rect((1,0),5,0)  #| -----
B = Rect((5,0),3,0)  #|     ---
assert A.dist(B) == 0
assert B.dist(A) == 0

# Case4: 1 distance apart in negative domain
A = Rect((-1,0),3,0)  #      -|-- 
B = Rect((-5,0),3,0)  #  ---
assert A.dist(B) == 1
assert B.dist(A) == 1