查找网格上两点之间的距离

Question

我正在计算两点之间的距离，给定 departure = [x,y] 和 destination = [x,y]。对于 x 或 y，一个总是浮点数，另一个是整数，所以它总是在一条线上。您必须留在网格线上才能到达目的地点，并且没有设置增量。我还没有看到任何其他关于在处理整数和浮点数混合的网格上查找距离的帖子，所以我在这里。

这是我的代码：

def perfectCity(departure, destination):
    return abs(destination[0]-departure[0]) + abs(destination[1]-departure[1])

一个例子是 departure = [0.4, 1] 和 destination = [0.9, 3]，它应该等于 2.7，但我得到 2.5

例如，您从 [0.4, 1] 到 [1, 1] 再到 [1, 3] 再到 [0.9, 3] 总差为 2.7。这就像计算曼哈顿距离，但不是从格点开始和结束，您可以 and/or 在一个街区的中途结束。

Answer 1

这不是 int 和 float 的混合，可能您遇到了浮点错误。 floats 不准确，它们是近似值，因此可以 "off" 少量。

您可以使用 decimal 模块提供的 Decimal 对象来准确处理浮点值。这是一个例子：

>>> 1.1 + 2.2        # will produce small error
3.3000000000000003
>>> from decimal import Decimal
>>> Decimal('1.1') + Decimal('2.2')
Decimal('3.3')

最终结果仍为"off"，但使用Decimal将有助于避免累积舍入误差：

>>> 3.3 - (1.1 + 2.2)
-4.440892098500626e-16
>>> Decimal(3.3) - (Decimal(1.1) + Decimal(2.2))
Decimal('-4.440892098500250464677810669E-16')
>>> Decimal('3.3') - (Decimal('1.1') + Decimal('2.2'))
Decimal('0.0')

Answer 2

当您查看不同的组合时，似乎朴素的曼哈顿距离会起作用，除了当您的路径呈现 "C" 形状（如中给出的这个例子）。当且仅当您的两个浮点数都是 x 坐标或 y 坐标和具有相同的整数部分时，才会发生这种情况。

尝试可能如下所示：

def minimum_distance(p1, p2):

    i1, i2 = int(p1[0]), int(p2[0])

    # if both x-coordinates are floats and they have the same integer part
    if i1 != p1[0] and i2 != p2[0] and i1 == i2:

        # find the decimal parts
        d1, d2 = p1[0] - i1, p2[0] - i2

        # find the smaller "C"
        x = min(d1 + d2, (1-d1) + (1-d2))

        # add the y distance to the "C" distance
        return abs(p1[1] - p2[1]) + x

    # repeat with the "y-coordinates are floats" case
    i1, i2 = int(p1[1]), int(p2[1])
    if i1 != p1[1] and i2 != p2[1] and i1 == i2:
        d1, d2 = p1[1] - i1, p2[1] - i2
        y = min(d1 + d2, (1-d1) + (1-d2))
        return abs(p1[0] - p2[0]) + y

    # simple case, return the Manhattan distance
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])


print(minimum_distance([0.4, 1], [0.9, 3]))
# 2.7

Answer 3

从每栋房子乘坐短途出租车到一个角落。您有两种方法可以这样做。然后——在由此产生的弯道之间乘坐远程出租车。有 2x2 = 4 种可能性，具体取决于所经过的角。取最小值：

from math import ceil,floor

#as a helper function, vanilla taxicab:

def t(p,q):
    x,y = p
    z,w = q
    return abs(x-z)+abs(y-w)

#find the two corners closest to a point:

def corners(p):
    x,y = p
    if isinstance(x,float):
        return [(floor(x),y),(ceil(x),y)]
    else:
        return [(x,floor(y)), (x,ceil(y))]

#combine these:   

def dist(p,q):
    return min(t(p,c) + t(c,d) + t(d,q)  for c in corners(p) for d in corners(q))

例如，

>>> dist((.4,1),(.9,3))
2.7

查找网格上两点之间的距离

Find distance between 2 points on grid

python

algorithm

distance