我有兴趣计算由它们的顶点定义的 2 个多边形（特别是几乎是矩形的四边形）之间的 Hausdorff 距离。它们可能重叠。
回想一下 $d_H(A,B) = \max(d(A,B), d(B,A))$ 其中 $d$ 是 Hausdorff 半度量 $d(A,B) = \sup_{a\在 A}\inf_{b\in B}d(a,b)$。
给定 $A$, ${A_i}$, $d(A,B)=\max{d(A_i,B)}$ 的有限不相交覆盖，是真的吗？其推论是 $d(A,B)=d(A\setminus B,B)$。
我找到了 Atallah 1 (PDF)的一篇论文。我对使用 Python 工作很感兴趣，并且愿意接受任何预编程的解决方案。
在凸多边形的情况下，是从 的顶点到 中任意点d(A, B)的距离的最大值。因此，如果您可以计算任意点到凸多边形的距离，则豪斯多夫距离并不难计算。AB
要计算从一个点到凸多边形的距离，您首先必须测试该点是否在多边形内（如果是，则距离为 0），然后如果不是，则找到到任何边界线段的最小距离。
您的另一个问题的答案是否定的。例如，让 A 和 B 都是以原点为中心的同一个 2x2 正方形。将 A 划分为 4 个 1x1 方格。每个 A i到 B的 Hausdorff 距离为sqrt(2)，但 A 到 B 的距离为 0。
更新：关于顶点的声明并不是很明显，因此我将绘制一个在任何有限维数上都很好的证明。我试图证明的结果是，在计算d(A, B)多边形和B凸面时，只要找到到 的顶点的距离就足够A了B。（最近的点B可能不是顶点，但最远的点之一A必须是顶点。）
由于两者都是有限的封闭形状，因此它们是紧凑的。从紧致性来看，必然存在一个点p，A即尽可能远离B。从紧致性来看，必然存在一个点q，B它尽可能地接近于A。
仅当A和B是同一个多边形时，该距离才为 0，在这种情况下，很明显我们在 的顶点处实现了该距离A。因此，在不失一般性的情况下，我们可以假设从p到有一个正距离q。
画出与从到q的线垂直的平面（在更高维度上，某种超平面）。任何一点都可以穿过这个平面吗？好吧，如果有一个，比如说，那么从到的线段上的每个点都必须在其中，因为是凸的。但是很容易证明，这条线段上一定有一个点比is 更接近，这与 的定义相矛盾。因此不能越过这个位面。pqBrqrBBpqqB
显然p不可能是内点，因为如果是内点，那么继续沿着从q到的射线p，你会发现其中的点离后面有界A的平面更远，这与 的定义相矛盾。如果是 的一个顶点，则结果为真。因此，唯一有趣的情况是 if在边界上但不是顶点。BppApA
如果是这样，那么p是在表面上。如果该表面不平行于我们构建的平面，则很容易沿着该表面行进，远离我们在后面界定的平面，并找到距离比B更远的点。因此，该表面必须平行于该平面。由于是有限的，因此该曲面必须在某个顶点处终止。这些顶点与该平面的距离与 相同，因此至少与 一样远。因此，至少存在一个离 尽可能远的顶点。BpApBpAB
这就是为什么找到从多边形的顶点到另一个多边形的距离的最大值就足够了。
（我把构建一对q没有顶点的多边形作为一个有趣的练习留给读者。）