Approximate matching of polygonal shapes (extended abstract)

Abstract

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 ejjiciently than determining op-timal solutions. In the most general case the algorithm for the pseudo-optimal solution is based on the quite sur-prising fact that for the optimal possible match between P and an image I(Q) of Q the distance between the cen-troids 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 simple polygons can be determined in time O(n log n], where n is the total number of vertices.