I am looking for fast procedures for polygon matching, i.e. checking polygon similarity under different transforms

  • translation only,
  • translation + rotation,
  • translation + scaling,
  • translation + rotation + scaling (= similarity).

The matching can be partial, meaning that there can be a good match on a significant fraction of the outline (say > 70%), and complete mismatch elsewhere.

The number of vertices is reasonable (say N<50).

In a variant of the problem, you need to compare two polygons. In another variant, you compare one polygon to a series of polygons, with preprocessing of the single polygon allowed. In a third variant, preprocessing is allowed on all polygons.

Are you aware of solutions to this problem ?

enter image description here


There is quite a bit of work on this important problem. Some of the most insightful work is by Helmut Alt and collaborators. He wrote a survey in 2009:

Helmut Alt. "The computational geometry of comparing shapes." Efficient Algorithms. Springer Berlin Heidelberg, 2009. 235-248. (Springer link.)

Image from Helmut Alt & Leonidas J. Guibas. "Discrete geometric shapes: Matching, interpolation, and approximation." Handbook of computational geometry 1 (1999): 121-153.).

  • 1
    $\begingroup$ Quite interesting, thanks. I found several related publications by H. Alt & al. $\endgroup$ – Yves Daoust Jan 2 '16 at 20:46

One reasonable approach is to use RANSAC to find a homography that causes many points to be aligned (or approximately aligned). You'd apply this procedure to align the set of vertices of the first polygon with the set of vertices of the second polygon.

The homography captures translation, rotation, and scaling, so it allows correcting for all of them. RANSAC allows for a subset of the points to match (the points that are approximately aligned are called inliers; the others are outliers), and tries to find a homography that (firstly) maximizes the number of points that are approximately aligned and (secondly) among all such homographies, causes the aligned points to be as closely aligned as possible.

  • $\begingroup$ Indeed RANSAC is an option. I have enough with just a similarity transform. $\endgroup$ – Yves Daoust Jan 3 '16 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.