Hausdorff distance

Definition

Let's formally define the Hausdorff distance.

Here is the definition of the directed Hausdorff distance between two sets of points. It is defined as the maximum distance of a point in one set to the closest point in the other set. It makes more sense seeing it as math :

Hausdorff equation Where d(a,b) is the Euclidian distance between two points.

To make it more general, we can define the undirected Hausdorff distance, which is the maximum between the two directed Hausdorff distances.

Hausdorff equation

Algorithms

Brute force

A simple brute force algorithm for that would look something like this :

Figure 3 :    A nice animation taken from here showing the calculation of Hausdorff distance between two shapes.

Complexity

To find the directed distance, such an algorithm runs in O(nm)+O(n)=O(nm). That needs to be performed two times to get the undirected distance.

ATALLAH algorithm

In 1983, Mikhail J. Atallah proposed an algorithm for convex shapes that runs in linear time : O(n+m).

The proof is based on 3 lemmas :

  • Lemma 1 : Let d(x, y) = D(A, B), where x is a point of A and y is a point of B. Then
    • (i) the perpendicular to xy at x is a supporting line of A, and A is on the same side as B relative to that supporting line, and
    • (ii) the perpendicular to xy at y is a supporting line of B, and x and B are on different sides relative to that line.
  • Lemma 2 : There is a vertex x of A such that the distance from x to B is equal to D(A, B).
  • Lemma 3 : The scan σ changes direction exactly twice.

    • The scan is performed in that way : for a vertex vk of A, we draw a line vk yk (yk is either a vertex of B or a point on an edge of B perpendicular to the edge). If the next point vk+1 is to the left of vk yk, we scan B counterclockwise, otherwise we scan it clockwise. Because the shape is convex, the 3rd lemma makes sense. The idea of the algo resides on that last lemma. It guarantees that the repetitive execution of Step 2 will not cause polygon B to be ‘scanned’ more than twice.

The algo

Step 1. Computer do and find y. (this can clearly be done in O(m) time). Set D(A, B) + d, and k + 0.

Step 2 (finding yk + , ) Case 1. vk+, is to the left of ykvk: Search for yk + 1 by ‘scanning’ polygon B counterclockwise, starting at y,., until one of the following two conditions is satisfied: (i) The edge of B being considered (call it w,w,+,) is such that the foot (call it z) of the perpendicular from vk+, to WOWS+1 is between wq and w,+,. In this case set yk+ , + z. (ii) The vertex of B being considered (call it w4) is such that the perpendicular to vL+,wq at ws is a supporting line of B. In this case set Ykt, ‘WC,. Case 2. vk+, is to the right of ykvk: This case is similar to Case 1, except that the search for yk + , is done by ‘scanning’ polygon B clockwise, starting at yk. Case 3. vk+, is on ykvk (but not necessarily between yk and vk): Set yk+, + yk.

Step 3. Set D(A, B) +max{D(A, B), d(vk+,, Ye+,)} and k + k + 1 mod n. If k f 0, then go to Step 2, otherwise stop.