# Hausdorff Distance Between Convex Polygons

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.

-
Are you looking for a Python library which implements this algorithm, or do you want to write it yourself? Either way, consider posting in stackoverflow.com – Karolis Juodelė Jun 8 '12 at 13:14
I've posted to SO - someone suggested posting it here, though I already had! – Alex Chamberlain Jun 8 '12 at 13:25
The problem might be that you have two questions here - one about theory and one about its application. Regardless, could you clarify what you are looking for? – Karolis Juodelė Jun 8 '12 at 15:09
I have an algorithm outputting a few almost rectangles, many of which are nearly the same - the vertices are +-5 pixels. I wish to cluster these similar rectangles and thought Hausdorff Distance is the best way to do it. – Alex Chamberlain Jun 8 '12 at 15:30

## 1 Answer

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

Yes, if $\cup A_i = A$. This follows from transitivity of comparison operators. It does not matter how you divide your points, $\max\{\sup A, \sup B\} = \sup A \cup B$.

-
Thanks, that means I can use an algorithm for (almost) disjoint polygons. – Alex Chamberlain Jun 8 '12 at 13:26
This is wrong. See the answer on: stackoverflow.com/questions/10947366/… – Alex Chamberlain Jun 12 '12 at 15:25
This is not wrong. This difference is that you asked about $d$, while the stack overflow reply is referring to $d_H$. – Karolis Juodelė Jun 12 '12 at 17:10
Apologies. You are correct. – Alex Chamberlain Jun 12 '12 at 17:29