矩形之间的曼哈顿距离

Question

我有一组矩形，我需要计算它们之间的曼哈顿距离。我已经尝试过实现它，但是代码崩溃了，效果不佳。

也许有人可以帮助我提供一些可用于计算两个矩形之间的距离的智能（高效）公式？

示例：

A和B之间的距离是直线1的长度。 A 和 C 之间的距离是直线的长度 2。等等

我用python来实现一切。如果已经存在一个函数（例如在 scipy 中）并且有人知道它，那也很好。

谢谢

Answer 1

我建议，您使用矩形的中心点和矩形宽度来计算距离。您主要必须弄清楚矩形的哪些角（边）用于计算。其他一切都很简单。一个简单的例子：

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

@LynxLike 的解决方案似乎不起作用，所以我正在 post 使用另一个解决方案。此 post 末尾的测试用例是简化的分段距离，其中每个用例的答案都是显而易见的，而之前的解决方案失败了一些。

总的来说，虽然问题看起来很复杂，但您可以将问题分成x-segments和y-segments，分别计算，对两个轴使用相同的算法，从而简化问题。一个解决方案应该适用于矩形和线段。

对于 dx，您计算右侧矩形（或线段）的 x 坐标是否大于左侧矩形的 x 坐标和宽度之和。如果是正数，说明有距离；否则，它要么接触、重叠（在 x-axis 中），要么 rects 的相对位置被翻转。基本上，除非 rects 有一定距离，否则您将得到 0 或负结果，您可以使用 max 函数轻松将其裁剪为 0。您不需要检查哪个矩形是哪一侧；您可以再次使用 max() 同时检查这两种情况。

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

这是一个完整的解决方案，它基于@LynxLike 的 Rect class 并修复了原始条件语句失败的地方！谢谢！

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

矩形之间的曼哈顿距离

Manhatten distance between rectangles

python

distance

rectangles