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?
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this communityAs 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?
There isn't a "standard" answer that everyone uses for this problem. However there are some common measures that have been used. This answer is not complete (that would be too hard to summarize), but googling the relevant terms mentioned here will lead you in the right direction.
In general, you should think of the two polylines you want to compare as curves with a well defined "start" and "end". In that case, the measures I'm describing assume a monotonic continous mapping between the curves (i.e imagine a point on one curve and another point on the other moving in the "forward" direction). The goal is to minimize some property of this mapping.
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.
Dynamic Time Warping is studied extensively in data mining/vision. Here, the goal is to minimize the "average" leash length rather than the maximum. There are fewer guarantees for this measure, but you'll probably find lots of code available for it.