OSDN Git Service

modified: src/strokes.txt
[kp123/kp123.git] / 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(g_list_first(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