# Match two Polylines [closed] As per Image, for a Given polyline P which consists of set of Points {(px1, py2), (px2, py2)}, i want to find to which polyline M1, M2, M3 , it matches the best.

Output : M3 Polyline.

Please provide how to find out this?

## closed as off-topic by Marzio De Biasi, R B, Tsuyoshi Ito, domotorp, Kristoffer Arnsfelt HansenNov 1 '14 at 18:28

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – domotorp, Kristoffer Arnsfelt Hansen
If this question can be reworded to fit the rules in the help center, please edit the question.

• You're not asking an algorithms question as much as a modelling one. In other words, what you're really asking (I think) is: What is a good way to measure the similarity between two polygonal chains ? Is that accurate ? – Suresh Venkat Jun 6 '14 at 12:47
• yes.. i want to compare one polygonal line to another one.. so how can i do this? – Prince Jun 9 '14 at 5:41
• Are you given the $M_i$ in advance, with $P$ being a query ? – Suresh Venkat Jun 9 '14 at 8:34
• Yes.. M1 = {(m1x1,m1y1) , (m1x2,m1y2) ...} , M2 = {(m2x1,m2y1) , (m2x2,m2y2) ...} & M3 = {(m3x1,m3y1) , (m3x2,m3y2) ...} – Prince Jun 9 '14 at 10:43
• btw, while the question is not very precisely stated, it's under the category of "modeling" questions that we do accept here at Theoretical Computer Science, so I don't think the downvotes are warranted. – Suresh Venkat Jun 9 '14 at 11:00

• The Fréchet distance is extensively studied in computational geometry. If you think of the point on one curve as a dog and the point on the other as a man holding the dog's leash, then the Frechet distance is the shortest leash length required when both man and dog are walking along the curves at arbitrary speeds. It's a metric (satisfies triangle inequality) and for two curves can be computed in worst case $O(n^2)$ time (modulo log factors) if $n$ is the size of each curve, and can be approximated under a number of realistic assumptions much faster than that.