Hausdorff凸多边形之间的距离

Question

我有兴趣计算由顶点定义的2个多边形（特别是几乎为矩形的四边形）之间的Hausdorff距离。它们可能重叠。 （A，B）= \ max（d（A，B），d（B，A））$其中$ d $是Hausdorff半度量 $ d（A，B）= （a，b）$中的A，B，B，D，

如果给定$ 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 _我到B的Hausdorff距离是sqrt(2)，而是从A到B的距离为0。

UPDATE：有关顶点的权利要求不能立即明显，因此我将绘制一个证明在任何有限数量的维度上都是好的。我试图证明的结果是，在计算d(A, B)中的两个多边形和B凸时，只需找到从顶点A到B的顶点的距离即可。 （B中的最近点可能不是顶点，但A中的最远点之一必须是顶点。）

由于二者都是有限闭合形状，所以它们是紧凑的。从紧凑性来看，必须存在p中的A，尽可能远离B。从紧凑性来看，B中必须存在q的点，该点尽可能接近A。

仅当A和B是相同的多边形时，此距离为0，在这种情况下，我们很清楚在顶点A处实现了该距离。因此，不失一般性，我们可以假设从p到q有正距离。

绘制垂直于从p到q的行的q的平面（更高维度，某种超平面）。 B中的任意一点能穿过这架飞机吗？那么如果有一个，例如r，那么从q到r的线段上的每个点必须在B中，因为B是凸的。但很容易证明，该线段上的点必须比q更接近p，这与q的定义相矛盾。因此B无法穿越这架飞机。

显然p不能是内部点，因为如果是，则沿射线继续从q到p，你会发现在A是从B是有界的背后，矛盾的p定义的平面更远点。如果p是A的顶点，那么结果是平凡的。因此，唯一有趣的情况是p位于A的边界上，但不是顶点。

如果是，那么p在表面上。如果该表面不平行于我们构造的平面，则沿着该表面行进将很容易，远离我们所在的面后面的B平面，并且找到距离B远的点比p更远。因此该表面必须平行于该平面。由于A是有限的，因此该表面必须在某个顶点终止。这些顶点距离该平面的距离与p相同，因此距离B至少与p差不多。因此，存在至少一个顶点A，尽可能远离B。

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

（我离开构造一对多边形与q不是一个顶点作为一个有趣的练习留给读者。）