# Matching points between 2 polygons

Given 2 polygons in a plane:

$A : ( (xa_1,ya_1), (xa_2,ya_2), ... (xa_n,ya_n) )$

$B : ( (xb_1,yb_1), (xb_2,yb_2), ... (xb_m,yb_m) )$

Is there a polynomial algorithm to compute a matching $M$ between the points in A and B, such that:

1. If $(xa_i,ya_i)$ is matched to $(xb_p,yb_p)$ and $(xa_k,ya_k)$ is matched to $(xb_r,yb_r)$, then for $i<j<k$ and $p<q<r$, $(xa_j,ya_j)$ is matched to $(xb_q,yb_q)$.
2. For $M:\{(i_1,j_1),(i_2,j_2)...\}$ and $|M|=min(n,m)$, $\Sigma_{k=1}^{|M|} distance((xa_{i_k},ya_{i_k}),(xb_{j_k},yb_{j_k}))$ is minimized.
• You define two polygons, but match polylines. It seems to me that your polylines should be allowed to go around polygons, like in cyclical order. Can you please clarify that? May 20 '17 at 16:11
• Yes, i want to describe it like that but can not find the exact wording. But either one is okay for my application actually. May 21 '17 at 19:23

## 1 Answer

This is a large topic, often called "geometric shape matching." Here is one survey that can lead to many specific algorithms:

H. Alt and L. J. Guibas. Discrete geometric shapes: Matching, interpolation, and approximation. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 121–153. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000. doi:10.1016/B978-044482537-7/50004-8

If you have difficulty accessing that chapter, an earlier draft of the survey is here: PDF download.