凸多边形之间的Hausdorff距离

Question

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

回想一下$d_H（A，B）=\max（d（A，B），d（B，A））$，其中$d$是Hausdorff半度量 $d（A，B）=\sup{A\在A}\inf{B\在B}d（A，B）$中。在

给定$a$，${a_i}$，$d（a，B）=\max{d（a_i，B）}$的有限不相交覆盖是真的吗？其推论是$d（A，B）=d（A\set减去B，B）$。在

我找到了一篇阿塔拉的论文。我对在Python中工作很感兴趣，愿意接受任何预先编程的解决方案。在

Answer 1

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

要计算一个点到凸多边形的距离，首先必须测试该点是否在多边形内部（如果是，则该距离为0），然后如果没有找到到任何边界线段的最小距离。在

让答案和另一个答案都在原点上。把A分成4个1x1的正方形。从每个A_i到B的Hausdorff距离是sqrt(2)，但是从A到B的距离是0。在

更新：关于顶点的声明并不立即显而易见，因此我将勾勒出一个在任何有限维数下都是好的证明。我试图证明的结果是，在计算既有多边形又有B的{}时，找到{}顶点到{}的距离就足够了。{{cda>中最靠近的一个点不能是cd2中最远的一个点

因为它们都是有限的形状，所以都是紧致的。从紧性看，A中必须存在一个离B尽可能远的点{}。从紧性看，B中必须存在一个尽可能接近A的点{}。在

只有当A和B是同一个多边形时，这个距离才是0，在这种情况下，很明显我们在A的顶点处达到了这个距离。因此，在不丧失一般性的前提下，我们可以假设p到{}之间存在一个正距离。在

画一个与q相接触的平面（在更高的维度中，某种超平面）垂直于p到{}的直线。B中的任何一点都能穿过这个平面吗？如果有一个，比如r，那么从q到{}的线段上的每一个点都必须在B内，因为B是凸的。但是很容易证明这条线段上一定有一个点比q更接近p，这与{}的定义相矛盾。因此B不能穿过这个平面。在

很明显，p不可能是一个内部点，因为如果是这样，那么沿着光线从q到{}继续，你会发现{}中的点与{}后面有界的平面较远，这与{}的定义相矛盾。如果p是A的一个顶点，则结果通常为真。因此，唯一有趣的情况是p在A的边界上，而不是顶点。在

如果是这样，那么p在一个曲面上。如果该曲面与我们构建的平面不平行，则很容易沿着该曲面移动，远离我们在其后面限定的平面B，并找到距离B比p更远的点。所以这个表面必须和那个平面平行。由于A是有限的，该曲面必须在某个顶点处终止。这些顶点与该平面的距离与p相同，因此与B的距离至少与p相同。因此，A的至少一个顶点离B越远越好。在

这就是为什么找到从多边形顶点到另一个多边形的最大距离就足够了。在

（我把构造一对没有顶点的多边形留给读者作为一个有趣的练习。）