Approximate Matching of Polygonal Shapes 


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

Get the report here or by anonymous ftp: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-93-10.ps.gz
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.