Polygon Matching and Indexing Under Affine Transformations
share
Given a collection {Z_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.
READ FULL TEXT