1

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.

Alex Chamberlain
  • 111
  • 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 08 '12 at 13:14
  • I've posted to SO - someone suggested posting it here, though I already had! – Alex Chamberlain Jun 08 '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 08 '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 08 '12 at 15:30

1 Answers1

1

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$.

Karolis Juodelė
  • 9,702
  • 1
  • 25
  • 39