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.

  • $\begingroup$ 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 $\endgroup$ – Karolis Juodelė Jun 8 '12 at 13:14
  • $\begingroup$ I've posted to SO - someone suggested posting it here, though I already had! $\endgroup$ – Alex Chamberlain Jun 8 '12 at 13:25
  • $\begingroup$ 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? $\endgroup$ – Karolis Juodelė Jun 8 '12 at 15:09
  • $\begingroup$ 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. $\endgroup$ – Alex Chamberlain Jun 8 '12 at 15:30

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.