как сравнить две кривые (массивы точек)

Question

у меня есть 2 массива точек (x, y), с этими точками я могу нарисовать 2 кривые.

У кого-нибудь есть идеи, как рассчитать, как эти кривые похожи?

Answer 1

Вы всегда можете рассчитать площадь между этими двумя кривыми. (Это немного проще, если конечные точки совпадают.) Кривые похожи, если площадь мала, и не очень похожи, если площадь не мала.

Обратите внимание, что я не определил «маленький». Это было преднамеренно. Опять же, вы не определили «подобное».

Редактировать
Иногда площадь не самый лучший показатель. Например, рассмотрим функцию f (x) = 0 и f (x) = 1e6 * sin (x). Если диапазон x является некоторым целым кратным 2 * pi, область между этими кривыми равна нулю. Функция, которая колеблется между плюсом и минусом миллиона, не является хорошим приближением f (x) = 0.

Необходим лучший показатель. Вот пара. Примечание: здесь я предполагаю, что значения x идентичны в двух наборах; единственное, что отличается, это значения y.

1. Сумма квадратов. Для каждого значения x вычислите delta_y _i = y _{1, i} - y _{2, i} и накопите delta_y _i ² . Этот показатель является основой для оптимизации наименьших квадратов, где целью является минимизация суммы квадратов ошибок. Это широко используемый подход, потому что часто его довольно легко реализовать.

2. Максимальное отклонение. Найдите abs_delta_y _i = | y _{1, i} - y _{2, i} | который максимизирует | y _{1, i} - y _{2, i} | для всех значений х. Этот показатель является основой для многих реализаций функций в математической библиотеке, где целью является минимизация максимальной ошибки. Эти реализации математической библиотеки являются приблизительными значениями истинной функции. Как потребитель такого приближения, меня, как правило, больше заботит худшее, что может сделать приближение с моим приложением, чем то, как это приближение будет вести себя в среднем.

Answer 2

Возможно, вы захотите использовать Динамическое искажение времени (DTW) или Расстояние Фреше .

Динамическая деформация времени

Динамическая деформация времени суммирует разницу по всей кривой всего .Он может обрабатывать два массива разных размеров.Вот фрагмент из Wikipedia о том, как может выглядеть код.Это решение использует двумерный массив.Стоимость будет расстоянием между двумя точками.Конечное значение массива DTW [n, m] содержит совокупное расстояние.

int DTWDistance(s: array [1..n], t: array [1..m]) {
    DTW := array [0..n, 0..m]

    for i := 1 to n
        DTW[i, 0] := infinity
    for i := 1 to m
        DTW[0, i] := infinity
    DTW[0, 0] := 0

    for i := 1 to n
        for j := 1 to m
            cost:= d(s[i], t[j])
            DTW[i, j] := cost + minimum(DTW[i-1, j  ],    // insertion
                                        DTW[i  , j-1],    // deletion
                                        DTW[i-1, j-1])    // match

    return DTW[n, m]
}

DTW аналогично ответу Якопсона.

Расстояние Фреше

Расстояние Фреше вычисляетсамое дальнее, что кривые разделяются.Это означает, что все остальные точки на кривой ближе друг к другу, чем это расстояние.Этот подход обычно представлен с собакой и владельцем, как показано здесь: Пример расстояния Фреше .

В зависимости от ваших массивов, вы можете сравнить расстояние между точками и использовать максимум.

Answer 3

Я предполагаю, что Кривая - это массив двухмерных точек над действительными числами, размер массива равен N, поэтому я называю p[i] i -ую точку кривой; i идет от 0 до N-1.

Я также предполагаю, что две кривые имеют одинаковый размер и что имеет смысл «сравнить» i -ую точку первой кривой с i -ой точкой второй кривой.

Я звоню Delta, действительное число, результат сравнения двух кривых.

Delta может быть вычислено следующим образом:

Delta = 0;
for( i = 0; i < N; i++ ) {
   Delta = Delta + distance(p[i],q[i]);
}

, где p - точки от первой кривой, а q - точки от второй кривой.

Теперь вам нужно выбрать подходящую distance функцию в зависимости от вашей проблемы: функция имеет две точки в качестве аргумента и возвращает действительное число.

Например, distance может быть обычным расстоянием двух точек на плоскости (теорема Пифагора и http://en.wikipedia.org/wiki/Euclidean_distance).

Пример метода в C ++:

#include <numeric>
#include <vector>
#include <cmath>
#include <iostream>
#include <functional>
#include <stdexcept>

typedef double Real_t;

class Point
{
public:
    Point(){}
    Point(std::initializer_list<Real_t> args):x(args.begin()[0]),y(args.begin()[1]){}
    Point( const Real_t& xx, const Real_t& yy ):x(xx),y(yy){}
    Real_t x,y;
};

typedef std::vector< Point > Curve;

Real_t point_distance( const Point& a, const Point& b )
{
    return hypot(a.x-b.x,a.y-b.y);
}

Real_t curve_distance( const Curve& c1, const Curve& c2 )
{
    if ( c1.size() != c2.size() ) throw std::invalid_argument("size mismatch");
    return std::inner_product( c1.begin(), c1.end(), c2.begin(), Real_t(0), std::plus< Real_t >(), point_distance );
}

int main(int,char**)
{
    Curve c1{{0,0},
             {1,1},
             {2,4},
             {3,9}};

    Curve c2{{0.1,-0.1},
             {1.1,0.9},
             {2.1,3.9},
             {3.1,8.9}};

    std::cout << curve_distance(c1,c2) << "\n";

    return 0;
}

Если ваши две кривые имеют разный размер, вам нужно подумать, как расширить предыдущий метод, например, вы можете уменьшить размер самой длинной кривой с помощью подходящего алгоритма (например, Ramer – Douglas– Алгоритм Peucker может быть отправной точкой), чтобы он соответствовал размеру самой короткой кривой.

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