豪斯多夫距离（集合之间的距离度量）
Hausdorff距离
写在前面的翻译来源：翻译源
介绍
在数学中，Hausdorff距离或Hausdorff度量，也称为Pompeiu-Hausdorff距离，是度量空间中两个子集之间的距离。它将度量空间的非空子集本身转化为度量空间。
非正式地说，如果一个集合的每个点都接近另一个集合的某个点，那么两个集合在Hausdorff距离上是接近的。Hausdorff距离是指对手在两组中的一组中选择一个点，然后必须从那里到达另一组的最长距离。换句话说，它是从一个集合中的一个点到另一个集合中最近的点的所有距离中最大的一个。
基本定义
以费利克斯·豪斯多夫（Felix Hausdorff，1868-1942）命名，Hausdorff distance是“一个集合到另一个集合中最近点的最大距离”[Rote91]。更正式地说，从集合A到集合B的Hausdorff距离是一个极大极小函数，定义为有向Hausdorff距离函数：公式2：
其中A和B分别是集合A和B的点，d（A，B）是这些点之间的任何度量；为简单起见，我们将d（A，B）作为A和B之间的欧几里得距离。如果A和B是两组点，暴力算法是：
Brute force algorithm :
- h = 0
- 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 = shortes
过程如下图：
需要注意的是Hausdorff距离是定向的（我们也可以说是不对称的），这意味着大多数时候h（A，B）不等于h（B，A）。对于图3的示例，该一般条件也成立，即h（A，B）=d（a1，b1），而h（B，A）=d（b2，a1）。这种不对称性是极大极小函数的一个性质，而极小极小函数是对称的。
Hausdorff距离的一个更一般的定义是：公式3：
它定义了A和B之间的Hausdorff距离，而公式2适用于A到B的Hausdorff距离（也称为定向Hausdorff距离）。两个距离h（A，B）和h（B，A）有时被称为A到B的向前和向后Hausdorff距离。虽然这个术语在作者中还不稳定，但在讨论Hausdorff距离时，通常是指等式3。除非另有说明，从现在起，我们在说“Hausdorff distance”时也将参考公式3。
多边形Hausdorff距离
如果集合A和B由直线或多边形组成，而不是由单个点组成，则H（A，B）适用于这些直线或多边形的所有定义点，而不仅仅是它们的顶点。暴力算法已经不能用于计算这些集合之间的Hausdorff距离，因为它们涉及到无限多个点。
对于多边形，Hausdorff距离给出了一个有趣的度量它们之间的相互接近性，它表示一个多边形的任意点到另一个多边形之间的最大距离。优于最短距离，它只应用于每个多边形的一个点，而不考虑多边形的所有其他点。
假设
我们假设多边形A和B是简单的凸多边形；多边形A和B彼此不相交，即：-它们不相交；-没有多边形包含另一个。
对于多边形Hausdorff距离：
Algorithm for computing h(A, B) :
- From a1, find the closest point b1 and compute d1 = d ( a1, b1 )
- h(A, B) = d1
- 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 }