7
$\begingroup$

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

$\endgroup$

3 Answers 3

6
$\begingroup$

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.).


$\endgroup$
2
  • 1
    $\begingroup$ Quite interesting, thanks. I found several related publications by H. Alt & al. $\endgroup$
    – user16034
    Jan 2, 2016 at 20:46
  • $\begingroup$ Have you found a solution to this? $\endgroup$
    – vinni
    Jun 6, 2019 at 9:54
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Indeed RANSAC is an option. I have enough with just a similarity transform. $\endgroup$
    – user16034
    Jan 3, 2016 at 14:47
0
$\begingroup$

An interesting application of partial polygon matching is symmetry detection in building footprints

enter image description here

$\endgroup$
1
  • $\begingroup$ As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Apr 6 at 11:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.