<p>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. </p>

<p>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. </p>

<ul>
<li><p>The <a href="http://en.wikipedia.org/wiki/Fr%C3%A9chet_distance" rel="nofollow">Fréchet distance</a> is <a href="http://www.staff.science.uu.nl/~driem101/" rel="nofollow">extensively studied</a> 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. </p></li>
<li><p><a href="http://www.cs.ucr.edu/~eamonn/LB_Keogh.htm" rel="nofollow">Dynamic Time Warping</a> 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. </p></li>
</ul>

CC BY-SA 3.0
2014-06-09T10:59:59.440Z
2014-06-09T10:59:59.440Z
Suresh Venkat
<p><img src="https://i.sstatic.net/YI9Mc.png" alt="As per Image For Given Polyline P which consists of set of Points {(px1, py2), (px2, py2)} i want to find to which polylines M1, M2, M3 it best matches."></p>

<p>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.</p>

<p>Output : M3 Polyline.</p>

<p>Please provide how to find out this?</p>

CC BY-SA 3.0
2014-06-06T12:47:25.127Z
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
CC BY-SA 3.0
2014-06-09T05:41:19.860Z
yes.. i want to compare one polygonal line to another one.. so how can i do this?
Prince
CC BY-SA 3.0
2014-06-09T08:34:12.983Z
Are you given the $M_i$ in advance, with $P$ being a query ?
Suresh Venkat
CC BY-SA 3.0
2014-06-09T10:43:10.010Z
Yes.. M1 = {(m1x1,m1y1) , (m1x2,m1y2) ...} , M2 = {(m2x1,m2y1) , (m2x2,m2y2) ...} & M3 = {(m3x1,m3y1) , (m3x2,m3y2) ...}
Prince
CC BY-SA 3.0
2014-06-09T11:00:35.850Z
btw, while the question is not very precisely stated, it's under the category of "modeling" questions that we do accept here at [cstheory.se], so I don't think the downvotes are warranted.
Suresh Venkat
<cg.comp-geom>
Match two Polylines
Prince
# Match two Polylines

(Asked by: username_0 on 2014-06-06)

![As per Image For Given Polyline P which consists of set of Points {(px1, py2), (px2, py2)} i want to find to which polylines M1, M2, M3 it best matches.](https://i.sstatic.net/YI9Mc.png)

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?

**Tags:** cg.comp-geom
> **Comments:**
> **username_1**: 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 ?  
> **username_0**: yes.. i want to compare one polygonal line to another one.. so how can i do this?  
> **username_1**: Are you given the $M_i$ in advance, with $P$ being a query ?  
> **username_0**: Yes.. M1 = {(m1x1,m1y1) , (m1x2,m1y2) ...} , M2 = {(m2x1,m2y1) , (m2x2,m2y2) ...} & M3 = {(m3x1,m3y1) , (m3x2,m3y2) ...}  
> **username_1**: btw, while the question is not very precisely stated, it's under the category of "modeling" questions that we do accept here at [cstheory.se], so I don't think the downvotes are warranted.  

---

## 1 answers

### Answer by username_1 on 2014-06-09. Score: 2 | Accepted answer

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](http://en.wikipedia.org/wiki/Fr%C3%A9chet_distance) is [extensively studied](http://www.staff.science.uu.nl/~driem101/) 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](http://www.cs.ucr.edu/~eamonn/LB_Keogh.htm) 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.


---

