python - 凸多边形之间的 Hausdorff 距离

Question

我对计算由顶点定义的 2 个多边形(特别是几乎是矩形的四边形)之间的 Hausdorff 距离很感兴趣。它们可能会重叠。

回想 $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 工作很感兴趣，愿意接受任何预编程的解决方案。

Answer 1

在凸多边形的情况下，d(A, B)是与 A 的顶点的距离的最大值到 B 中的任何一点.因此，如果可以计算任意点到凸多边形的距离，Hausdorff 距离就不难计算了。

要计算从一个点到凸多边形的距离，您首先必须测试该点是否在多边形内部(如果是，则距离为 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 时此距离为 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 而不是顶点的多边形作为读者的有趣练习。)