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

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

Мой пример

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

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

Вот мой 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);

}

Спасибо


javascript curve-fitting mathematical-optimization best-fit-curve
person piggyback    schedule 02.06.2013    source источник
comment
Просто идея: я хотел бы сначала заполнить пробелы в красной кривой с помощью простой интерполяции. Тогда ваш алгоритм должен работать и для левой части рисунка.   -  person ojdo    schedule 21.08.2013

Ответы (1)


arrow_upward
2
arrow_downward

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

S0=SumOverAllT(x0(t)-x(t))^2 + (y0(t) - y(t))^2

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

S1=SumOverAllT(x1(t)-x(t))^2 + (y1(t) - y(t))^2

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

S=S0+S1

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

x(t)=ax+bx*t+cx*t^2+dx*t^3....

y(t)=ay+by*t+cy*t^2+dy*t^3....

Затем вы рассчитаете

dS/dax, 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 - таким образом, у вас есть еще один параметр и еще одно уравнение.

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

Также поищите в интернете:

  • Подгонка кривой
  • Сплайн-аппроксимация

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

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

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

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

x0(t)=a0x + b0x*(t - t0) + c0x*(t-t0)^2 + d0x*(t - t0)^3....

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

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

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

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

x0(t)

y0(t)

x1(t)

y1(t)

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

x(t)=(x0(t) + (x1(t)-x0(t))/2

y(t)=(y0(t) + (y1(t)-y0(t))/2

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

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

person Community    schedule 03.11.2013