Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Are you looking for a Python library which implements this algorithm, or do you want to write it yourself? Either way, consider posting in – 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

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

share|cite|improve this answer
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:… – 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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