我有兴趣计算由顶点定义的两个多边形(特别是几乎是矩形的四边形)之间的豪斯多夫距离。它们可能会重叠。
回想一下 $d_H(A,B) =\max(d(A,B), d(B,A))$，其中 $d$ 是 Hausdorff 半度量 $d(A,B) =\sup_{a\in 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)是距 A 顶点的距离的最大值到 B 中的任意点。因此，只要能计算出任意点到凸多边形的距离，豪斯多夫距离就不太难计算。
要计算从一个点到凸多边形的距离，首先必须测试该点是否在多边形内部(如果是，则距离为 0)，然后如果不在，则找到到任何边界的最小距离线段。
您的另一个问题的答案是否定的。举个例子，让 A 和 B 都是同一个以原点为中心的 2x2 正方形。将 A 划分为 4 个 1x1 的正方形。每个 Ai 到 B 的豪斯多夫距离为 sqrt(2) ，但 A 到 B 的距离为 0。
更新:关于顶点的主张并不是立即显而易见的，因此我将草拟一个在任何有限数量的维度上都有效的证明。我试图证明的结果是在计算d(A, B)时具有两个多边形和 B凸，只要找到 A 顶点的距离就足够了至B 。 (B 中最近的点可能不是顶点，但 A 中最远的点之一必须是顶点。)
由于两者都是有限闭合形状，因此它们是紧凑的。从紧性来看，一定存在一个点p在A尽可能远离 B 。从紧性来看，一定存在一个点q在B尽可能接近 A .
仅当 A 时，此距离才为 0和B是相同的多边形，在这种情况下，很明显我们在 A 的顶点达到了这个距离。 。因此，不失一般性，我们可以假设距 p 存在正距离。至q .
绘制接触 q 的平面(在更高维度，某种超平面)垂直于 p 的线至q 。可以任意点B穿越这个位面？如果有的话，比如r ，然后 q 线段上的每个点至r必须位于 B因为B是凸的。但很容易证明，这条线段上一定有一个点更接近 p比q是，与 q 的定义相矛盾。因此B无法穿越这个位面。
显然p不能是内点，因为如果是内点，则继续沿着 q 的射线继续至p您可以在 A 中找到点离飞机较远的 B被限制在后面，与 p 的定义相矛盾。如果p是 A 的顶点，那么结果自然是正确的。因此，唯一有趣的情况是如果 p位于 A 的边界上但不是顶点。
如果是这样，那么p是在一个表面上。如果该表面不平行于我们构建的平面，则很容易沿着该表面移动，远离我们界定的平面 B后面，找到离 B 更远的点比p 。因此该表面必须平行于该平面。自 A是有限的，该曲面必须终止于某处的顶点。这些顶点与该平面的距离与 p 相同。 ，因此至少与 B 一样远如p 。因此 A 至少存在一个顶点尽可能远离 B .
这就是为什么只要找到从多边形顶点到另一个多边形的最大距离就足够了。
(我将构建一对带有q而不是顶点的多边形作为读者的有趣练习。)
关于python - 凸多边形之间的豪斯多夫距离，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10947366/