CODEWITHSUNDEEP
algorithm
Sibbs Gambling
Sibbs Gambling

Reputation: 20355

How to know one curve belongs to another?

I have my curve A and my curve B who is actually part of curve A. Now I wish for an algorithm that can identify this belongingness.

A curve here is defined as a series of 2D-(x, y) points. The x value does not mean too much to the belongingness determination. So we are free to left/right shift the curves, if that helps. What matters most is the shape and then the y value. (That is, the curve may also be moved up/down, but only when necessary)

I have tried searching this on Google, but ended up with no useful information on this. I don't even know the keywords for this problem. Could anyone direct me on this?

P.S. I know (I think so) about Dynamic Time Warping (DTW). AFAIK it identifies two similar curves of different lengths, but not points out the belongingness.

Upvotes: 1

Views: 72

Answers (1)

Beta
Beta

Reputation: 99094

If the curve can be translated (i.e. moved without rotation) then what does not change is the difference between adjacent points. So instead of a list of N points pk = (xk, yk), we have a list of N-1 vectors dk = (xk+1-xk, yk+1-yk). Now all we have to do is check whether the B list is contained in the A list, which is trivial.

Upvotes: 4

Related Questions