Лучший путь между двумя кривыми

Question

Моя цель состоит в том, чтобы найти гладкую линию наилучшего соответствия между этими двумя круговыми фигурами. Есть ли какой-нибудь алгоритм, который мне кажется, который может найти набор точек (или кривых) между двумя строками, подобными этому примеру?

Алгоритм я до сих пор занимает внутреннюю часть и для каждой точки находит ближайший, однако это не работает, потому что (смотрите в первом повороте).

(Красный внутренняя часть, зеленый внешняя часть, синий оптимизированная точек я нашел)

Вот мой jsfiddle: http://jsfiddle.net/STLuG/

Это алгоритм:

for (i = 0; i < coords[0].length; i++) { 
    var currentI = coords[0][i]; 
    j = 0; 
    var currentJ = coords[0][j]; 

    currentDist = dist(currentI,currentJ); 
    for (j=1; j < coords[1].length; j++) { 
    possibleJ = coords[1][j]; 
    possibleDist = dist(currentI, possibleJ); 
    if (possibleDist < currentDist) { 
     currentJ = possibleJ; 
     currentDist = possibleDist; 
    } else { 

    } 
    } 


    b_context.fillRect(
    (currentI.x+currentJ.x)/2+maxX, 
    (currentI.y+currentJ.y)/2+maxY, 
    1, 1); 

} 

Спасибо

Answer 1

Я бы попробовал алгоритм наименьших квадратов. У вас есть несколько точек: y0 и x0 и y1 и x1 для первой и второй кривых соответственно. Вы хотите найти кривую y (t) и x (t), которая является гладкой и промежуточной между двумя заданными кривыми. Таким образом, существует расстояние между первой кривой (x0 (t), y0 (t)) до вашей расчетной кривой (x (t), y (t)):

S0 = SumOverAllT (x0 (t) -x (т))^2 + (у0 (т) - у (т))^2

То же самое для второй кривой:

S1 = SumOverAllT (x1 (т) -x (т))^2 + (y1 (т) - у (т))^2

сумма обоих сумм:

S = S0 + S1

У вас будет набор параметров, которые вы хотите определить. . если вы используете многочлены:

х (Т) = ах + вх * т + сх * т^2 + дх * т^3 ....

у (Т) = ау + на * т + су * т^2 + ду * т^3 ....

Вы рассчитает

Ds/Дакс Ds/DBX, Ds/DCX, ....

для всех параметров для расчета

и установите эти производные на ноль:

Ds/DAX == 0 Ds/DBX == 0 ....

Это даст вам набор линейных уравнений, которые могут быть атакованы с помощью алгоритма гаусс или любым другим способом, чтобы решить систему линейные уравнения.

Если вы используете полиномы, может случиться так, что кривая, рассчитанная, сильно колеблется. В этом случае я бы предложил попытаться минимизировать интеграл квадрата второй производной:

I = интеграл ((d^2x/dt^2)^2 + (d^2y/dt^2)^2, dt)

Вы должны были бы рассчитать дифференциал I по сравнению с некоторыми дополнительными параметрами, которые вы не использовали для вышеописанной системы уравнений - добавление параметра rx и вычисление dI/drx == 0 - таким образом, у вас есть еще один параметр и еще одно уравнение.

Любой, у кого есть PHD по математике, пожалуйста, посоветуйте мне любую глупость, о которой я говорил выше.

поиск Также в интернете для:

• Кривой фитинг приближение
• сплайна

Лучше было бы использовать сплайны - кусочно-непрерывные полиномы, так что

• 0 производная
• первая производная
• вторая производная

непрерывно. Посмотрите или купите цифровые рецепты, чтобы найти код, который делает именно это.

Для приближения сплайнами вы бы иметь набор полиномов:

x0 (т) = a0x + B0x * (т - t0) + c0x * (т-t0)^2 + d0x * (т - t0)^3 ....

x1 (t) = a1x + b1x * (t-t0) + c1x * (t-t0)^2 + d1x * (t - t0)^3 ....

Каждый многочлен использовался только для покрытия соответствия t = t0..t1 между двумя заданными точками.

Затем вы добавляли уравнения, чтобы убедиться, что значения, первая и вторая производные идентичны для двух соседних полиномов. И положим производную 2 для первого и последнего многочлена нулю.

Потенциально можно вычислить две шлицы - один для каждого из двух кривых входных у вас есть:

x0 (т)

y0 (т)

x1 (т)

y1 (т)

И тогда вы могли бы получить в середину двух сплайнов:

х (т) = (х0 (т) + (x1 (т) -x0 (T))/2

у (г) = (у0 (т) + (у1 (т) - у0 (т))/2

убедиться в том, что расстояние между любыми заданными кривыми и вы в результате чего кривая никогда не равна нулю, так что они не пересекаются друг с другом

Чтобы убедиться, что ваш рассчитанная линия не пересекает одну из заданных линий, вы можете свести к минимуму (сумма (1/(x0-x)^2)) + сумма (сумма (1/(x1-x)^2)))