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(a >= 7*M_PI/8)
  28         return 'D';
  29     if(y > 0)
  30     {
  31         if((5*M_PI/8 < a) && (a < 7*M_PI/8))
  32             return 'A';
  33         if((3*M_PI/8 <= a) && (a <= 5*M_PI/8))
  34             return 'B';
  35         if((M_PI/8 < a) && (a < 3*M_PI/8))
  36             return 'C';
  37     }
  38     else
  39     {
  40         if((5*M_PI/8 < a) && (a < 7*M_PI/8))
  41             return 'G';
  42         if((3*M_PI/8 <= a) && (a <= 5*M_PI/8))
  43             return 'H';
  44         if((M_PI/8 < a) && (a < 3*M_PI/8))
  45             return 'I';
  46     }
  47     return 0;
  48 }
  49
  50 static float find_largest_angle(GList *s, GList **out)
  51 {
  52     float a = 0, a1;
  53     GList *s0, *s1, *s2;
  54     *out = 0;
  55     if(g_list_length(s) < 3)
  56         return 0;
  57     for(s0 = s; s0 != g_list_last(s0); s0 = g_list_next(s0))
  58     {
  59         for(s1 = g_list_next(s0); s1 && (s1 != g_list_last(s1)); s1 = g_list_next(s1))
  60         {
  61             for(s2 = g_list_next(s1); s2 && (s2 != g_list_last(s2)); s2 = g_list_next(s2))
  62             {
  63                 GdkPoint *pt0 = (GdkPoint*)s0->data;
  64                 GdkPoint *pt = (GdkPoint*)s1->data;
  65                 GdkPoint *pt2 = (GdkPoint*)s2->data;
  66                 a1 = angle(pt0, pt, pt2);
  67                 if(a1 > a)
  68                 {
  69                     a = a1;
  70                     *out = s1;
  71                 }
  72             }
  73         }
  74     }
  75     return a;
  76 }
  77
  78 static GList* filter_equal_points(GList *s)
  79 {
  80     GdkPoint *p, *p2;
  81     for(;s != g_list_last(s); s = g_list_next(s))
  82     {
  83         p = (GdkPoint*)s->data;
  84         p2 = (GdkPoint*)g_list_next(s)->data;
  85         if((p->x == p2->x) && (p->y == p2->y))
  86         {
  87             s = g_list_delete_link(g_list_first(s), s);
  88         }
  89     }
  90     return g_list_first(s);
  91 }
  92
  93 /* let A, B, C be consecutive points
  94  * if angle ABC larger then predefined value
  95  * then remove B */
  96 static GList* filter_points_by_angle(GList *s)
  97 {
  98     if(g_list_length(s) < 3)
  99         return s;
 100     gchar ch0, ch1;
 101     GdkPoint *p0, *p, *p2;
 102     for(s = g_list_next(s); s != g_list_last(s); s = g_list_next(s))
 103     {
 104         if(g_list_length(s) < 3)
 105             break;
 106         p0 = (GdkPoint*)g_list_previous(s)->data;
 107         p = (GdkPoint*)s->data;
 108         p2 = (GdkPoint*)g_list_next(s)->data;
 109         ch0 = get_stroke_char(p0, p);
 110         ch1 = get_stroke_char(p, p2);
 111         if(ch0 == ch1)
 112             s = g_list_delete_link(s, s);
 113     }
 114     return g_list_first(s);
 115 }
 116
 117 static GList* filter_points_by_angle2(GList *s)
 118 {
 119     if(g_list_length(s) < 3)
 120         return s;
 121     const float MIN_MAX_ANGLE = 170*M_PI/180;
 122     while(1)
 123     {
 124         if(g_list_length(s) < 3)
 125             break;
 126         GList *pt = 0;
 127         if(find_largest_angle(s, &pt) > MIN_MAX_ANGLE)
 128             s = g_list_delete_link(s, pt);
 129         else
 130             break;
 131     }
 132     return g_list_first(s);
 133 }
 134
 135 static GList* filter_points_by_angle3(GList *s)
 136 {
 137     if(g_list_length(s) < 4)
 138         return s;
 139
 140     for(;;)
 141     {
 142         GdkPoint *p0 = (GdkPoint*)s->data;
 143         GList *s1 = g_list_next(s);
 144         if(!s1) break;
 145         GdkPoint *p1 = (GdkPoint*)s1->data;
 146         GList *s2 = g_list_next(s1);
 147         if(!s2) break;
 148         GdkPoint *p2 = (GdkPoint*)s2->data;
 149         GList *s3 = g_list_next(s2);
 150         if(!s3) break;
 151         GdkPoint *p3 = (GdkPoint*)s3->data;
 152         gchar ch1 = get_stroke_char(p0, p1);
 153         gchar ch3 = get_stroke_char(p2, p3);
 154         if(ch1 == ch3)
 155         {
 156             if((angle(p0, p1, p2) > 3*M_PI/4) && (angle(p1, p2, p3) > 3*M_PI/4))
 157             {
 158                 s = g_list_delete_link(s, s1);
 159                 s = g_list_delete_link(s, s2);
 160             }
 161         }
 162         s = g_list_next(s);
 163     }
 164     return g_list_first(s);
 165 }
 166
 167 static float find_average_and_smallest_dist(GList *s, GList **pt0, GList **pt1, float *pdmin)
 168 {
 169     float d = 0, dt, dmin = -1;
 170     int i = 0;
 171     for(; s != g_list_last(s); s = g_list_next(s), i++)
 172     {
 173         GdkPoint *p0 = (GdkPoint*)s->data;
 174         GdkPoint *p1 = (GdkPoint*)g_list_next(s)->data;
 175         dt = dist(p0, p1);
 176         if((dmin < 0) || (dmin > dt))
 177         {
 178             dmin = dt;
 179             *pt0 = s;
 180             *pt1 = g_list_next(s);
 181         }
 182         d += dt;
 183     }
 184     *pdmin = dmin;
 185     return d/i;
 186 }
 187
 188 /* let A, B be consecutive points
 189  * if dist(A,B) less than a certain percentage of average dist
 190  * then remove B */
 191 static GList* filter_points_by_dist(GList *s)
 192 {
 193     if(g_list_length(s) < 3)
 194         return s;
 195     const float MAX_MIN_DIST = 0.2;
 196     float d0, dmin;
 197     GList *pt0 = 0, *pt1 = 0;
 198     while(1)
 199     {
 200         if(g_list_length(s) < 3)
 201             break;
 202         d0 = MAX_MIN_DIST*find_average_and_smallest_dist(s, &pt0, &pt1, &dmin);
 203         if(dmin < d0)
 204         {
 205             GList *del;
 206             if(pt0 == s)
 207                 del = pt1;
 208             else if(pt1 == g_list_last(s))
 209                 del = pt0;
 210             else
 211             {
 212                 GdkPoint *p0 = (GdkPoint*)pt0->data;
 213                 GdkPoint *p01 = (GdkPoint*)g_list_previous(pt0)->data;
 214                 GdkPoint *p1 = (GdkPoint*)pt1->data;
 215                 GdkPoint *p11 = (GdkPoint*)g_list_next(pt1)->data;
 216                 float d0 = dist(p0, p01);
 217                 float d1 = dist(p1, p11);
 218                 if(d0 < d1)
 219                     del = pt0;
 220                 else
 221                     del = pt1;
 222             }
 223             s = g_list_delete_link(s, del);
 224         }
 225         else
 226             break;
 227     }
 228     return g_list_first(s);
 229 }
 230
 231 gchar *get_stroke_str(GList *s)
 232 {
 233     gchar *ret = calloc(g_list_length(s), sizeof(gchar));
 234     gchar prev = -1;
 235     gint len = 0;
 236     for(;s != g_list_last(s); s = g_list_next(s))
 237     {
 238         GdkPoint *p0 = (GdkPoint*)s->data;
 239         GdkPoint *p1 = (GdkPoint*)g_list_next(s)->data;
 240         gchar ch = get_stroke_char(p0, p1);
 241         if(!ch)
 242             continue;
 243         if(g_ascii_tolower(ch) != g_ascii_tolower(prev))
 244         {
 245             if(len)
 246                 ch = g_ascii_tolower(ch);
 247             ret[len++] = ch;
 248         }
 249         prev = ch;
 250     }
 251     return ret;
 252 }
 253
 254 gchar* recognize_stroke(GList *stroke, GList **out)
 255 {
 256     *out = g_list_copy(stroke);
 257     int len1, len2;
 258     for(;;)
 259     {
 260         len1 = g_list_length(*out);
 261         //g_printf("len_orig: %d\n", g_list_length(*out));
 262         *out = filter_points_by_angle(*out);
 263         //g_printf("len_angle_filtered: %d\n", g_list_length(*out));
 264         *out = filter_points_by_dist(*out);
 265         //g_printf("len_dist_filtered: %d\n", g_list_length(*out));
 266         len2 = g_list_length(*out);
 267         if(len1 != len2)
 268             continue;
 269         *out = filter_points_by_angle2(*out);
 270         //g_printf("len_angle2_filtered: %d\n", g_list_length(*out));
 271         *out = filter_points_by_angle3(*out);
 272         //g_printf("len_angle3_filtered: %d\n", g_list_length(*out));
 273         len2 = g_list_length(*out);
 274         if(len1 == len2)
 275             break;
 276     }
 277     return get_stroke_str(*out);
 278 }
 279