constrained dtw

dtw.c

typedef struct point{
  double x;
  double y;
} point;

double get_distance(const point a, const point b)
{
    double xdiff = a.x - b.x;
    double ydiff = a.y - b.y;
    return xdiff*xdiff + ydiff*ydiff;
}

double dtw(const point *a, int lena, const point *b, int lenb)
{
    double    tmpDistance, accumulatedDistance = 0.0;
    double  * d; // distance matrix
    int       i, j;
    int       w = max(lena, lenb); // unconstrained

    // Initialize distance matrix
    d = (double *)malloc(lena * lenb * sizeof(double));
    fill_n(d, lena*lenb, 1e10);

    d[0] = get_distance(a[0], b[0]);

    // fill in the distance matrix using dynamic programming
    for (i = 1; i < lena; i++)
    {
        for (j = max(1, i-w); j <= min(lenb-1, i+w); j++)
        {
            tmpDistance = fmin(fmin(d[(i-1)*lenb + j], d[(i-1)*lenb + j-1]), d[i*lenb + j-1]);
            d[i*lenb + j] = tmpDistance + get_distance(a[i], b[j]);
        }
    }
    accumulatedDistance = d[(lena - 1)*lenb + lenb - 1];

    free(d);

    return sqrt(accumulatedDistance);
}