Fitting a curve to some segment of another curve

Question

Maybe I should ask this in Mathoverflow but here it goes:

I have 2 data sets (sets of x and y coordinates) with different number of elements. I have to find the best match between them by stretching one of the data sets (multiplying all x with a factor of m and all y with a factor of n) and moving it around (adding p and q to all x and y respectively).

Basically these 2 sets represent different curves and i have to fit curve B (which has less elements) to some segment of curve A (which has many more elements).

How can I find the values m, n, p, and q for the closest match?

Answers can be pseudo code, C, Java or Python. Thanks.

Answer 1

Following is a solution for finding values m, n, p and q when after transforming the first curve it matches exactly with a part of the second curve:

Basically, we have to solve the following matrix equation:

[m n][x y]' + [p q]' = [X Y]' ...... (1)

where [x y]' and [X Y]' are the coordinates of first and second curves respectively. Let's assume first curve has total l number of coordinates and second curve has total h number of coordinates.

(1) implies, 
[mx+p ny+1]' = [X Y]'

i.e we have to solve:

mx_1+p = X_k, mx_2+p = X_{k+1}, ..., mx_l+p = X_{k+l-1}
ny_1+q = Y_k, ny_2+q = Y_{k+1}, ..., ny_l+q = Y_{k+l-1}

where k+l-1 <= h-l

We can solve it in the following naive way:

for (i=1 to h-l){
    (m,p) = SOLVE(x1, X_i, x2, X_{i+1})// 2 unknowns, 2 equations
    (n,q) = SOLVE(y1, Y_i, y2, Y_{i+1})// 2 unknowns, 2 equations
    for (j=3 to l){
        if(m*x[j]+p != m*X[i+2]+p)break;//value of m, p found from 1st 2 doesn't work for rest
        if(n*y[j]+q != n*Y[i+2]+q)break;//value of n, q found from 1st 2 doesn't work for rest
    }
    if(j==l){//match found
        return i;//returns the smallest index of 2nd curves' coordinates where we found a match
    }
 }
 return -1;//no match found

I am not sure if there can be an optimized version of this.