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 Hansen Nov 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
-
4You'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
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.
