Hausdorff Distance Between Convex Polygons

Question

I'm interested in calculating the Hausdorff Distance between 2 polygons (specifically quadrilaterals which are almost rectangles) defined by their vertices. They may overlap.

Recall $d_H(A,B) = \max(d(A,B), d(B,A))$ where $d$ is the Hausdorff semi-metric $d(A,B) = \sup_{a\in A}\inf_{b\in B}d(a,b)$.

Is it true that, given a finite disjoint covering of $A$, ${A_i}$, $d(A,B)=\max{d(A_i,B)}$? A corollary of which is that $d(A,B)=d(A\setminus B,B)$.

I have found a paper by Atallah 1 (PDF). I'm interested in working in Python and would be open to any preprogrammed solutions.

Answer 1

In the case of convex polygons, d(A, B) is the maximum of the distances from vertices of A to any point in B. Therefore the Hausdorff distance is not too hard to calculate if you can calculate the distance from an arbitrary point to a convex polygon.

To calculate the distance from a point to a convex polygon you first have to test whether the point is inside the polygon (if so the distance is 0), and then if it is not find the minimum distance to any of the bounding line segments.

The answer to your other query is no. As an example let A and B both be the same 2x2 square centered at the origin. Partition A into 4 1x1 squares. The Hausdorff distance from each A_i to B is sqrt(2), but the distance from A to B is 0.

UPDATE: The claim about the vertices is not immediately obvious, therefore I'll sketch a proof that is good in any finite number of dimensions. The result I am trying to prove is that in calculating d(A, B) with both polygons and B convex, it suffices to find the distances from the vertices of A to B. (The closest point in B might not be a vertex, but one of the farthest points in A must be a vertex.)

Since both are finite closed shapes, they are compact. From compactness, there must exist a point p in A that is as far as possible from B. From compactness, there must exist a point q in B that is as close as possible to A.

This distance is 0 only if A and B are the same polygon, in which case it is clear that we achieve that distance at a vertex of A. So without loss of generality we may assume that there is a positive distance from p to q.

Draw the plane (in higher dimensions, some sort of hyperplane) touching q that is perpendicular to the line from p to q. Can any point in B cross this plane? Well if there was one, say r, then every point on the line segment from q to r must be in B because B is convex. But it is easy to show that there must be a point on this line segment that is closer to p than q is, contradicting the definition of q. Therefore B cannot cross this plane.

Clearly p cannot be an interior point, because if it was, then continue along the ray from q to p and you find points in A that are farther from the plane that B is bounded behind, contradicting the definition of p. If p is a vertex of A, then the result is trivially true. Therefore the only interesting case is if p is on a boundary of A but is not a vertex.

If so, then p is on a surface. If that surface were not parallel to the plane we constructed, it would be easy to travel along that surface, away from the plane we have bounded B behind, and find points farther away from B than p. Therefore that surface must be parallel to that plane. Since A is finite, that surface must terminate in vertices somewhere. Those vertices are the same distance from that plane as p, and therefore are at least as far from B as p. Therefore there exists at least one vertex of A that is as far as possible from B.

That is why it sufficed to find the maximum of the distances from the vertices of the polygons to the other polygon.

(I leave constructing a pair of polygons with q not a vertex as a fun exercise for the reader.)