Approximate Matching of Polygonal Shapes

Helmut Alt, Bernd Behrends, Johannes Blömer Institut für Informatik Freie Universität Berlin e-mail: Report B 93-10 July 93

Get the report here or by anonymous ftp: 
File:   pub/reports/
For two given simple polygons $P,Q$ the problem is to determine a rigid motion $I$ of $Q$ giving the best possible match between $P$ and $Q$, i.e.\ minimizing the Hausdorff-distance between $P$ and $I(Q)$. Faster algorithms as the one for the general problem are obtained for special cases, namely that $I$ is restricted to translations or even to translations only in one specified direction. It turns out that determining pseudo-optimal solutions, i.e.\ ones that differ from the optimum by just a constant factor can be done much more efficiently than determining optimal solutions. In the most general case the algorithm for the pseudo-optimal solution is based on the surprising fact that for the optimal possible match between $P$ and an image $I(Q)$ of $Q$ the distance between the centroids of the edges of the convex hulls of $P$ and $I(Q)$ is a constant multiple of the Hausdorff-distance between $P$ and $I(Q)$. It is also shown that the Hausdorff-distance between two polygons can be determined in time $O(n\log n)$, where $n$ is the total number of vertices.