Polygon Matching and Indexing Under Affine Transformations

Abstract

Given a collection _1,Z_2,,Z_m\ of n-sided polygons in the plane and a query polygon W we give algorithms to find all Z_ such that W=f(Z_) with f an unknown similarity transformation in time independent of the size of the collection. If f is a known affine transformation, we show how to find all Z_ such that W=f(Z_) in O(n+(m)) time. For a pair W,W^ of polygons we can find all the pairs Z_,Z_^ such that W=f(Z_) and W^=f(Z_^) for an unknown affine transformation f in O(m+n) time. For the case of triangles we also give bounds for the problem of matching triangles with variable vertices, which is equivalent to affine matching triangles in noisy conditions.

Tasks

Reproductions