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

Ответ 1

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

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

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

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

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

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

Ответ 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 похож на ответ Жапсона.

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

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

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

Ответ 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).

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

#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;
}

Если ваши две кривые имеют разный размер, вам нужно подумать о том, как расширить предыдущий метод, например, вы можете уменьшить размер самой длинной кривой с помощью подходящего алгоритма (например, алгоритм Рамера-Дугласа-Пиккера может быть отправной точкой), чтобы соответствовать его размеру самой короткой кривой.

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