src/recognize_stroke.c

   1
   2 #include "defs.h"
   3 #include <math.h>
   4
   5 #include "recognize_stroke.h"
   6
   7 float dist(GdkPoint *pt0, GdkPoint *pt1)
   8 {
   9     return sqrt(pow(pt1->x - pt0->x, 2) + pow(pt1->y - pt0->y, 2));
  10 }
  11
  12 static float angle(GdkPoint *pt0, GdkPoint *pt, GdkPoint *pt2)
  13 {
  14     float d0 = dist(pt0, pt);
  15     float d2 = dist(pt, pt2);
  16     float d = dist(pt0, pt2);
  17     return acos((pow(d0, 2) + pow(d2, 2) - pow(d, 2))/(2*d0*d2));
  18 }
  19
  20 gchar get_stroke_char(GdkPoint *p0, GdkPoint *p1)
  21 {
  22     float x = p1->x - p0->x;
  23     float y = p1->y - p0->y;
  24     float a = acos(x/dist(p0, p1));
  25     if(a <= M_PI/8)
  26         return 'F';
  27     if(y < 0)
  28     {
  29         if((M_PI/8 < a) && (a < M_PI/2))
  30             return 'I';
  31     }
  32     else
  33     {
  34         if((5*M_PI/8 < a) && (a < 7*M_PI/8))
  35             return 'A';
  36         if((3*M_PI/8 <= a) && (a <= 5*M_PI/8))
  37             return 'B';
  38         if((M_PI/8 < a) && (a < 3*M_PI/8))
  39             return 'C';
  40     }
  41     return 0;
  42 }
  43
  44 static float find_largest_angle(GList *s, GList **out)
  45 {
  46     float a = 0, a1;
  47     GList *s0, *s1, *s2;
  48     *out = 0;
  49     if(g_list_length(s) < 3)
  50         return 0;
  51     for(s0 = s; s0 != g_list_last(s0); s0 = g_list_next(s0))
  52     {
  53         for(s1 = g_list_next(s0); s1 && (s1 != g_list_last(s1)); s1 = g_list_next(s1))
  54         {
  55             for(s2 = g_list_next(s1); s2 && (s2 != g_list_last(s2)); s2 = g_list_next(s2))
  56             {
  57                 GdkPoint *pt0 = (GdkPoint*)s0->data;
  58                 GdkPoint *pt = (GdkPoint*)s1->data;
  59                 GdkPoint *pt2 = (GdkPoint*)s2->data;
  60                 a1 = angle(pt0, pt, pt2);
  61                 if(a1 > a)
  62                 {
  63                     a = a1;
  64                     *out = s1;
  65                 }
  66             }
  67         }
  68     }
  69     return a;
  70 }
  71
  72 static GList* filter_equal_points(GList *s)
  73 {
  74     GdkPoint *p, *p2;
  75     for(;s != g_list_last(s); s = g_list_next(s))
  76     {
  77         p = (GdkPoint*)s->data;
  78         p2 = (GdkPoint*)g_list_next(s)->data;
  79         if((p->x == p2->x) && (p->y == p2->y))
  80         {
  81             s = g_list_delete_link(s, s);
  82         }
  83     }
  84     return g_list_first(s);
  85 }
  86
  87 /* let A, B, C be consecutive points
  88  * if angle ABC larger then predefined value
  89  * then remove B */
  90 static GList* filter_points_by_angle(GList *s)
  91 {
  92     const float MIN_MAX_ANGLE = 170*M_PI/180;
  93     while(1)
  94     {
  95         if(g_list_length(s) < 3)
  96             return g_list_first(s);
  97         GList *pt = 0;
  98         if(find_largest_angle(s, &pt) > MIN_MAX_ANGLE)
  99             s = g_list_delete_link(s, pt);
 100         else
 101             break;
 102     }
 103     if(g_list_length(s) < 3)
 104         return g_list_first(s);
 105     GdkPoint *p0, *p, *p2;
 106     for(s = g_list_next(s); s != g_list_last(s); s = g_list_next(s))
 107     {
 108         if(g_list_length(s) < 3)
 109             return g_list_first(s);
 110         p0 = (GdkPoint*)g_list_previous(s)->data;
 111         p = (GdkPoint*)s->data;
 112         p2 = (GdkPoint*)g_list_next(s)->data;
 113         gchar ch0 = get_stroke_char(p0, p);
 114         gchar ch1 = get_stroke_char(p, p2);
 115         if(ch0 == ch1)
 116             s = g_list_delete_link(s, s);
 117     }
 118     return g_list_first(s);
 119 }
 120
 121 static float find_average_and_smallest_dist(GList *s, GList **pt0, GList **pt1, float *pdmin)
 122 {
 123     float d = 0, dt, dmin = -1;
 124     int i = 0;
 125     for(; s != g_list_last(s); s = g_list_next(s), i++)
 126     {
 127         GdkPoint *p0 = (GdkPoint*)s->data;
 128         GdkPoint *p1 = (GdkPoint*)g_list_next(s)->data;
 129         dt = dist(p0, p1);
 130         if((dmin < 0) || (dmin > dt))
 131         {
 132             dmin = dt;
 133             *pt0 = s;
 134             *pt1 = g_list_next(s);
 135         }
 136         d += dt;
 137     }
 138     *pdmin = dmin;
 139     return d/i;
 140 }
 141
 142 /* let A, B be consecutive points
 143  * if dist(A,B) less than a certain percentage of average dist
 144  * then remove B */
 145 static GList* filter_points_by_dist(GList *s)
 146 {
 147     const float MAX_MIN_DIST = 0.3;
 148     float d0, dmin;
 149     GList *pt0 = 0, *pt1 = 0;
 150     while(1)
 151     {
 152         if(g_list_length(s) < 3)
 153             return g_list_first(s);
 154         d0 = MAX_MIN_DIST*find_average_and_smallest_dist(s, &pt0, &pt1, &dmin);
 155         if(dmin < d0)
 156         {
 157             GList *del;
 158             if(pt0 == s)
 159                 del = pt1;
 160             else if(pt1 == g_list_last(s))
 161                 del = pt0;
 162             else
 163             {
 164                 GdkPoint *p0 = (GdkPoint*)pt0->data;
 165                 GdkPoint *p01 = (GdkPoint*)g_list_previous(pt0)->data;
 166                 GdkPoint *p1 = (GdkPoint*)pt1->data;
 167                 GdkPoint *p11 = (GdkPoint*)g_list_next(pt1)->data;
 168                 float d0 = dist(p0, p01);
 169                 float d1 = dist(p1, p11);
 170                 if(d0 < d1)
 171                     del = pt0;
 172                 else
 173                     del = pt1;
 174             }
 175             s = g_list_delete_link(s, del);
 176         }
 177         else
 178             break;
 179     }
 180     return s;
 181 }
 182
 183 gchar *get_stroke_str(GList *s)
 184 {
 185     gchar *ret = calloc(g_list_length(s), sizeof(gchar));
 186     gchar prev = -1;
 187     gint len = 0;
 188     for(;s != g_list_last(s); s = g_list_next(s))
 189     {
 190         GdkPoint *p0 = (GdkPoint*)s->data;
 191         GdkPoint *p1 = (GdkPoint*)g_list_next(s)->data;
 192         gchar ch = get_stroke_char(p0, p1);
 193         if(!ch)
 194             continue;
 195         if(ch != prev)
 196         {
 197             if(len)
 198                 ch = g_ascii_tolower(ch);
 199             ret[len++] = ch;
 200         }
 201         prev = ch;
 202     }
 203     return ret;
 204 }
 205
 206 gchar* recognize_stroke(GList *stroke, GList **out)
 207 {
 208     *out = g_list_copy(stroke);
 209     *out = filter_equal_points(*out);
 210     *out = filter_points_by_angle(*out);
 211     *out = filter_points_by_dist(*out);
 212     return get_stroke_str(*out);
 213 }
 214