如何检查一个点是否位于（最小）曼哈顿距离线上？

Question

我有一个8x10矩阵，里面有一些方块：

no = [(2,4),(3,4),(6,4),(7,4),(2,5),(3,5),(6,5),(7,5)]

我需要弄清楚两点之间的最短路径（manhattan）是否包含任何块，并围绕它重新布线。在

现在要做到这一点，我试图应用欧几里德距离的逻辑，来看看C是否在A和B之间的直线上，把从A到C的距离加上从C到B的距离，看看它是否等于A到B，但我不相信数学。。。在

^{pr2}$

它为manhattan_dist(((0,1),(0,7)))打印“blocked”，所以我知道我在python中也做了些错事。在

Answer 1

由于缺乏代表性，回答而不是评论（…我是新来的）。
在我看来有点不明确。曼哈顿距离没有一条最短路线……事实上，它有许多最短路径。
所以也许你要澄清你的意思？在

顺便说一句，如果你想知道曼哈顿的任何一条小路是否被堵住了，那就意味着你有一个盒子

min([a, c]) < box[0] < max([a, c]) and min([b, d]) < box[1] < max([b, d])

---

根据评论中的讨论进行编辑：
首先，总是有精确的abs(a-c) + abs(b-d)选择abs(a-c)路径，且曼哈顿距离最小。（对于错误的注释，很抱歉；只是按照问题params，不幸的是缺少乳胶支持）。
如果正确地穿过几何体，所有的最小路径被阻塞是非常棘手的，并且不会很快。我不认为有一种方法可以避免在所有路径中循环，通过将路径排序成层次树并在方块被阻塞时删除完整的分支来获得一些优化。。。在

Answer 2

Now to do this, I was trying to apply the logic that works for euclidean distance that to see if C is on the line between A and B by adding the distance from A to C to the distance from C to B and seeing if it equals A to B

你在这里使用的数学概念叫做“度量”。这只是你已经熟悉的欧几里德距离的一个推广。有关详细信息，请参见the wikipedia article。曼哈顿距离满足公制的所有要求。这意味着您可以确信，如果d(A, B) + d(B, C) = d(A, C)位于A和{}之间的最短路径上。与欧几里德距离不同，从A到{}的路径可能有很多，其中许多路径可能通过{}。在