Подгонка кривой к некоторому сегменту другой кривой

Question

Может быть, я должен спросить об этом в Mathoverflow, но здесь это идет:

У меня есть 2 набора данных (наборы координат х и у) с разным количеством элементов. Я должен найти лучшее соответствие между ними, растягивая один из наборов данных (умножая все x с множителем m и все y с коэффициентом n) и перемещая его (добавляя p и q ко всем x и y соответственно),

В основном эти 2 набора представляют разные кривые, и я должен подогнать кривую B (в которой меньше элементов) к некоторому сегменту кривой A (в которой гораздо больше элементов).

Как я могу найти значения m, n, p и q для наиболее близкого соответствия?

Ответами могут быть псевдокод, C, Java или Python. Благодарю.

Answer 1

Ниже приводится решение для нахождения значений m, n, p и q, когда после преобразования первой кривой оно точно совпадает с частью второй кривой:

В основном, мы должны решить следующее матричное уравнение:

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

где [x y]'и [X Y]' - координаты первой и второй кривых соответственно. Предположим, что первая кривая имеет общее число координат l, а вторая кривая имеет общее количество координат h.

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

т.е. мы должны решить:

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

Мы можем решить это следующим наивным способом:

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

Я не уверен, может ли быть оптимизированная версия этого.