Hausdorff 距离

当谈论距离时，我们通常指的是最短距离：例如，如果说点 X 距离多边形 P 的距离为 D，我们通常假设 D 是从 X 到 P 的最近点的距离。同样的逻辑也适用于多边形：如果两个多边形 A 和 B 彼此相距一定距离，我们通常将该距离理解为 A 的任何一点和 B 的任何一点之间的最短距离。正式地，这称为极小函数，因为 A 和 B 之间的距离 D 由以下公式给出：

这个等式读起来就像一个计算机程序：“对于 A 的每个点 a，找到它到 B 的任意点 b 的最小距离；最后，保留所有点 a 之间的最小距离”。

多边形之间的距离定义对于某些应用来说可能非常不令人满意；让我们看图 1 的例子。我们可以说，考虑到三角形的最短距离（由红色顶点显示），它们彼此接近。然而，我们自然会认为这些多边形之间的距离很小意味着一个多边形的任何一点都不远离另一个多边形。从这个意义上讲，图 1 中所示的两个多边形并不那么接近，因为它们的最远点（以蓝色显示）实际上可能离另一个多边形非常远。显然，最短距离完全独立于每个多边形的形状。

图 2 给出了另一个示例，其中我们有两个三角形，它们之间的最短距离与图 1 中的相同，但位置不同。很明显，最短距离概念的信息量非常小，因为距离值与前一种情况相比没有变化，而物体确实发生了一些变化。

正如我们将在下一节中看到的那样，尽管Hausdorff距离看起来很复杂，但它确实捕捉到了最短距离忽略的这些细微之处。

1、什么是Hausdorff距离？

Hausdorff距离以费利克斯·豪斯多夫 (1868-1942) 的名字命名，是“一个集合到另一个集合中最近点的最大距离” [Rote91]。更正式地说，从集合 A 到集合 B 的豪斯多夫距离是一个最大最小函数，定义为：

其中 a 和 b 分别是集合 A 和 B 中的点，d(a, b) 是这些点之间的任意度量；为简单起见，我们将 d(a, b) 视为 a 和 b 之间的欧几里得距离。例如，如果 A 和 B 是两组点，则暴力算法如下所示：

1.  h = 0
2.  for every point ai of A,
      2.1  shortest = Inf ;
      2.2  for every point bj of B
                    dij = d (ai , bj )
                    if dij < shortest then
                              shortest = dij
      2.3  if shortest > h then
                    h = shortest

以下是暴力计算过程的图示：

该算法显然在 O(n m) 时间内运行，其中 n 和 m 是每组中的点数。

应该注意的是，Hausdorff距离是有方向的（我们也可以说不对称），这意味着大多数时候 h(A, B) 不等于 h(B, A)。这个一般条件也适用于上面的示例，因为 h(A, B) = d(a1, b1)，而 h(B, A) = d(b2, a1)。这种不对称性是最大最小函数的属性，而最小最小函数是对称的。

Hausdorff距离的更一般定义是：

H (A, B) = max { h (A, B), h (B, A) }

它定义了 A 和 B 之间的Hausdorff距离，而公式 2 适用于从 A 到 B 的豪斯多夫距离（也称为有向Hausdorff距离）。两个距离 h(A, B) 和 h(B, A) 有时被称为 A 到 B 的前向和后向Hausdorff距离。虽然作者之间术语尚未稳定，但上面的公式通常用于谈论豪斯多夫距离。除非另有说明，否则从现在起，我们在说“豪斯多夫距离”时也会引用上面公式。

如果集合 A 和 B 由线或多边形而不是单个点组成，则 H(A, B) 适用于这些线或多边形的所有定义点，而不仅仅是它们的顶点。暴力算法不再适用于计算此类集合之间的豪斯多夫距离，因为它们涉及无限数量的点。

2、多边形的Hausdorff距离

那么，图 1 中的多边形怎么样？请记住，它们的一些点很接近，但不是全部。豪斯多夫距离通过指示一个多边形上任何一点与另一个多边形之间的最大距离，给出了它们相互接近度的有趣度量。比最短距离更好，最短距离仅适用于每个多边形的一个点，而不考虑多边形的所有其他点。

另一个问题是，最短距离对多边形位置的不敏感性。我们看到，这种距离根本不考虑多边形的布置。这里，Hausdorff距离再次具有对位置敏感的优势，如图 5 所示：

3、计算凸多边形之间的Hausdorff距离

在下面的讨论中，我们假设多边形 A 和 B 具有以下事实：

• 多边形 A 和 B 是简单的凸多边形；
• 多边形 A 和 B 彼此不相交，即：a）它们不相交；b）没有多边形包含另一个。

3.1 引理

下一节中解释的算法基于此处介绍的三个几何观察。为了简化文本，我们假设两个点 a 和 b 分别属于多边形 A 和 B，这样：

d (a, b) = h (A, B)

简而言之，a 是多边形 A 相对于多边形 B 的最远点，而 b 是多边形 B 相对于多边形 A 的最近点。

• 引理 1a

在 a 处垂直于 ab 的线是 A 的一条支撑线，并且 A 与 B 相对于该线位于同一侧。

• 引理 1b：

在 b 处垂直于 ab 的线是 B 的一条支撑线，并且 a 和 B 相对于该线位于不同侧。

• 引理 2：

A 有一个顶点 x，使得从 x 到 B 的距离等于 h (A, B)。

• 引理 3：

让 bi 为 B 中距离 A 顶点 a i 最近的点。如果 µ 是从 bi 到 bi+1 的移动方向（顺时针或逆时针），那么，对于穿过 A 所有顶点的完整循环，µ 变化不超过两次。

3.2 算法

本文介绍的算法由 [Atallah83] 提出。其基本策略是依次计算 h(A,B) 和 h(B, A) ；根据引理 2，无需查询起始多边形的每个点，而只需查询其顶点。

该算法使用的一个重要事实是，最近点只能是目标多边形的顶点，或垂直于其一条边的线的脚 z。

这一事实表明，可以使用一个函数来检查可能的最近点是否存在。给定一个源点 a 和一个由点 b1 和顶点 b2 定义的目标边：

函数 z = CheckForClosePoint (a, b1 , b2 )：

• 计算通过 b1 和 b2 的线与通过 a 的垂线相交的位置 z；
• 如果 z 位于 b1 b2 之间，则返回 z；
• 否则，在 b2 处计算与线 ab2 垂直的线 P；
• 如果 P 是 B 的支撑线，则返回 b2；
• 否则返回 NULL。

该函数显然使用引理 1b 来决定 B 的最近点是否可能位于目标边上，即应该靠近 a。它还假设源点 a 和 b2 不位于 b1 处 [b1b2 ] 垂线的不同侧，根据引理 3。

现在我们准备好进行主要算法；假设两个多边形的顶点按逆时针方向枚举：

1.  From a1, find the closest point b1 and compute d1 = d ( a1, b1 )
2.  h(A, B) = d1
3.  for each vertex ai of A,
      3.1  if ai+1 is to the left of aibi
                     find bi+1 , scanning B counterclockwise with CheckForClosePoint from bi
              if ai+1 is to the right of aibi
                     find bi+1 , scanning B clockwise with CheckForClosePoint from bi
              if ai+1 is anywhere on aibi
                      bi+1 = bi
      3.2  Compute di+1 = d (ai+1 , bi+1 )
      3.3  h (A, B) = max { h (A, B), di+1 }

3.3 复杂度

如果多边形 A 和 B 分别有 n 和 m 个顶点，则：

• 步骤 1 显然可以在 O(m) 时间内完成；
• 步骤 2 需要常数时间 O(1) ；
• 步骤 3 将执行 (n-1) 次，即 O(n) ；
• 步骤 3.1 总共不会执行超过 O(2m)。这是引理 3 的结果，它保证多边形 B 不能被扫描超过两次；
• 步骤 3.2 和 3.3 在常数时间内完成 O(1) ；

因此，计算 h(A, B) 的算法需要：

O(m) + O(n) + O(2m) = O(n+m)

为了找到 H(A, B)，该算法需要执行两次；计算豪斯多夫距离的总复杂度保持线性到 O(n+m)。

原文链接：Hausdorff distance between convex polygons

BimAnt翻译整理，转载请标明出处