Back to index

easystroke  0.5.5.1
stroke.c
Go to the documentation of this file.
00001 /*
00002  * Copyright (c) 2009, Thomas Jaeger <ThJaeger@gmail.com>
00003  *
00004  * Permission to use, copy, modify, and/or distribute this software for any
00005  * purpose with or without fee is hereby granted, provided that the above
00006  * copyright notice and this permission notice appear in all copies.
00007  *
00008  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
00009  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
00010  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
00011  * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
00012  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
00013  * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
00014  * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
00015  */
00016 
00017 #define _GNU_SOURCE
00018 
00019 #include "stroke.h"
00020 #include <stdlib.h>
00021 #include <assert.h>
00022 #include <math.h>
00023 #include <stdbool.h>
00024 
00025 const double stroke_infinity = 0.2;
00026 #define EPS 0.000001
00027 
00028 struct point {
00029        double x;
00030        double y;
00031        double t;
00032        double dt;
00033        double alpha;
00034 };
00035 
00036 struct _stroke_t {
00037        int n;
00038        int capacity;
00039        struct point *p;
00040 };
00041 
00042 stroke_t *stroke_alloc(int n) {
00043        assert(n > 0);
00044        stroke_t *s = malloc(sizeof(stroke_t));
00045        s->n = 0;
00046        s->capacity = n;
00047        s->p = calloc(n, sizeof(struct point));
00048        return s;
00049 }
00050 
00051 void stroke_add_point(stroke_t *s, double x, double y) {
00052        assert(s->capacity > s->n);
00053        s->p[s->n].x = x;
00054        s->p[s->n].y = y;
00055        s->n++;
00056 }
00057 
00058 inline static double angle_difference(double alpha, double beta) {
00059        // return 1.0 - cos((alpha - beta) * M_PI);
00060        double d = alpha - beta;
00061        if (d < -1.0)
00062               d += 2.0;
00063        else if (d > 1.0)
00064               d -= 2.0;
00065        return d;
00066 }
00067 
00068 void stroke_finish(stroke_t *s) {
00069        assert(s->capacity > 0);
00070        s->capacity = -1;
00071 
00072        int n = s->n - 1;
00073        double total = 0.0;
00074        s->p[0].t = 0.0;
00075        for (int i = 0; i < n; i++) {
00076               total += hypot(s->p[i+1].x - s->p[i].x, s->p[i+1].y - s->p[i].y);
00077               s->p[i+1].t = total;
00078        }
00079        for (int i = 0; i <= n; i++)
00080               s->p[i].t /= total;
00081        double minX = s->p[0].x, minY = s->p[0].y, maxX = minX, maxY = minY;
00082        for (int i = 1; i <= n; i++) {
00083               if (s->p[i].x < minX) minX = s->p[i].x;
00084               if (s->p[i].x > maxX) maxX = s->p[i].x;
00085               if (s->p[i].y < minY) minY = s->p[i].y;
00086               if (s->p[i].y > maxY) maxY = s->p[i].y;
00087        }
00088        double scaleX = maxX - minX;
00089        double scaleY = maxY - minY;
00090        double scale = (scaleX > scaleY) ? scaleX : scaleY;
00091        if (scale < 0.001) scale = 1;
00092        for (int i = 0; i <= n; i++) {
00093               s->p[i].x = (s->p[i].x-(minX+maxX)/2)/scale + 0.5;
00094               s->p[i].y = (s->p[i].y-(minY+maxY)/2)/scale + 0.5;
00095        }
00096 
00097        for (int i = 0; i < n; i++) {
00098               s->p[i].dt = s->p[i+1].t - s->p[i].t;
00099               s->p[i].alpha = atan2(s->p[i+1].y - s->p[i].y, s->p[i+1].x - s->p[i].x)/M_PI;
00100        }
00101 
00102 }
00103 
00104 void stroke_free(stroke_t *s) {
00105        if (s)
00106               free(s->p);
00107        free(s);
00108 }
00109 
00110 int stroke_get_size(const stroke_t *s) { return s->n; }
00111 
00112 void stroke_get_point(const stroke_t *s, int n, double *x, double *y) {
00113        assert(n < s->n);
00114        if (x)
00115               *x = s->p[n].x;
00116        if (y)
00117               *y = s->p[n].y;
00118 }
00119 
00120 double stroke_get_time(const stroke_t *s, int n) {
00121        assert(n < s->n);
00122        return s->p[n].t;
00123 }
00124 
00125 double stroke_get_angle(const stroke_t *s, int n) {
00126        assert(n+1 < s->n);
00127        return s->p[n].alpha;
00128 }
00129 
00130 inline static double sqr(double x) { return x*x; }
00131 
00132 double stroke_angle_difference(const stroke_t *a, const stroke_t *b, int i, int j) {
00133        return fabs(angle_difference(stroke_get_angle(a, i), stroke_get_angle(b, j)));
00134 }
00135 
00136 /* To compare two gestures, we use dynamic programming to minimize (an
00137  * approximation) of the integral over square of the angle difference among
00138  * (roughly) all reparametrizations whose slope is always between 1/2 and 2.
00139  */
00140 double stroke_compare(const stroke_t *a, const stroke_t *b, int *path_x, int *path_y) {
00141        int m = a->n - 1;
00142        int n = b->n - 1;
00143 
00144        double dist[m+1][n+1];
00145        int prev_x[m+1][n+1];
00146        int prev_y[m+1][n+1];
00147        for (int i = 0; i < m; i++)
00148               for (int j = 0; j < n; j++)
00149                      dist[i][j] = stroke_infinity;
00150        dist[m][n] = stroke_infinity;
00151        dist[0][0] = 0.0;
00152 
00153        for (int x = 0; x < m; x++) {
00154               for (int y = 0; y < n; y++) {
00155                      if (dist[x][y] >= stroke_infinity)
00156                             continue;
00157                      double tx  = a->p[x].t;
00158                      double ty  = b->p[y].t;
00159                      int max_x = x;
00160                      int max_y = y;
00161                      int k = 0;
00162 
00163                      inline void step(int x2, int y2) {
00164                             double dtx = a->p[x2].t - tx;
00165                             double dty = b->p[y2].t - ty;
00166                             if (dtx >= dty * 2.2 || dty >= dtx * 2.2 || dtx < EPS || dty < EPS)
00167                                    return;
00168                             k++;
00169 
00170                             double d = 0.0;
00171                             int i = x, j = y;
00172                             double next_tx = (a->p[i+1].t - tx) / dtx;
00173                             double next_ty = (b->p[j+1].t - ty) / dty;
00174                             double cur_t = 0.0;
00175 
00176                             for (;;) {
00177                                    double ad = sqr(angle_difference(a->p[i].alpha, b->p[j].alpha));
00178                                    double next_t = next_tx < next_ty ? next_tx : next_ty;
00179                                    bool done = next_t >= 1.0 - EPS;
00180                                    if (done)
00181                                           next_t = 1.0;
00182                                    d += (next_t - cur_t)*ad;
00183                                    if (done)
00184                                           break;
00185                                    cur_t = next_t;
00186                                    if (next_tx < next_ty)
00187                                           next_tx = (a->p[++i+1].t - tx) / dtx;
00188                                    else
00189                                           next_ty = (b->p[++j+1].t - ty) / dty;
00190                             }
00191                             double new_dist = dist[x][y] + d * (dtx + dty);
00192                             if (new_dist != new_dist) abort();
00193 
00194                             if (new_dist >= dist[x2][y2])
00195                                    return;
00196 
00197                             prev_x[x2][y2] = x;
00198                             prev_y[x2][y2] = y;
00199                             dist[x2][y2] = new_dist;
00200                      }
00201 
00202                      while (k < 4) {
00203                             if (a->p[max_x+1].t - tx > b->p[max_y+1].t - ty) {
00204                                    max_y++;
00205                                    if (max_y == n) {
00206                                           step(m, n);
00207                                           break;
00208                                    }
00209                                    for (int x2 = x+1; x2 <= max_x; x2++)
00210                                           step(x2, max_y);
00211                             } else {
00212                                    max_x++;
00213                                    if (max_x == m) {
00214                                           step(m, n);
00215                                           break;
00216                                    }
00217                                    for (int y2 = y+1; y2 <= max_y; y2++)
00218                                           step(max_x, y2);
00219                             }
00220                      }
00221               }
00222        }
00223        double cost = dist[m][n];
00224        if (path_x && path_y) {
00225               if (cost < stroke_infinity) {
00226                      int x = m;
00227                      int y = n;
00228                      int k = 0;
00229                      while (x || y) {
00230                             int old_x = x;
00231                             x = prev_x[x][y];
00232                             y = prev_y[old_x][y];
00233                             path_x[k] = x;
00234                             path_y[k] = y;
00235                             k++;
00236                      }
00237               } else {
00238                      path_x[0] = 0;
00239                      path_y[0] = 0;
00240               }
00241        }
00242        return cost;
00243 }